HashMap#replace的复杂性是什么

Question

我想知道replace(Key , Value)对于HashMap的复杂性是多少。

我最初的想法是O(1)，因为它是O(1)来获得值，并且我可以简单地替换分配给键的值。

我不确定是否应该考虑在用java.util在java中实现的大型hashmap中可能存在的冲突。

Answer 1

tl:dr

HashMap#replace在O(1)中运行摊销；

并且在映射适当平衡的前提下，也不摊销，Java在put和remove调用期间会处理该映射。

未摊销

事实上，它是否也适用于非摊销分析取决于关于实施的自我平衡机制的问题。

基本上，由于replace只更改值，这不会影响哈希和HashMap的一般结构，因此替换值不会触发内部结构的任何重新哈希或重新组织。

因此，我们只支付定位key的成本，这取决于存储桶大小。

如果映射正确地自我平衡，则可以将bucket大小视为常数。导致replace的O(1)也未摊销。

然而，该实现仅基于启发式因素触发自平衡和重新散列。对此进行深入分析要复杂一些。

因此，由于启发式，现实可能介于两者之间

---

实施

可以肯定的是，让我们来看看当前的实现(Java16)：

@Override
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}

方法afterNodeAccess是子类的伪方法，在HashMap中为空。除了getNode之外的所有内容都在O(1)中琐碎地运行。

getNode

getNode是在HashMap中定位条目的规范实现，我们知道它在O(1)中运行以获得适当的自平衡映射，就像Javas实现一样。让我们看看代码：

/**
* Implements Map.get and related methods.
*
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

该方法基本上计算散列hash = hash(key)，然后在tablefirst = tab[(n - 1) & (hash = hash(key))]中查找散列，并开始迭代存储在桶中的数据结构。

关于bucket的数据结构，我们在if (first instanceof TreeNode)处进行了一些分支。

铲斗

bucket要么是简单的隐式链表，要么是红黑树。

链表

对于链表，我们有一个简单的迭代

do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);

其显然在CCD_ 26中运行，其中CCD_。

红黑树

对于红黑树，我们有

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

在红黑树中查找是O(log m)，其中m是树的大小。

铲斗尺寸

Javas实现确保在检测到它失控时通过重新哈希来重新平衡bucket(您可以在put或remove等每个修改方法上为此付费)。

因此，在这两种情况下，我们都可以将存储桶的大小视为常数，或者，由于涉及自平衡的启发式，可以将其视为接近常数。

结论

使bucket大小不变，有效地使getNode在O(1)中运行，从而使replace也在O(1)中运行。

如果没有任何自平衡机制，在最坏的情况下，如果使用链表，它将降级为O(n)，而对于红黑树，它将退化为O(log n)(对于所有密钥都产生哈希冲突的情况)。

可以更深入地研究代码，但它会变得更复杂。

Answer 2

你是对的，主要成本是查找，它是O(1)摊销的。

一旦我们找到了正确的点，用新的值替换相关的值就是O(1)。但查找仅摊销O(1)。

如Zabuzard的错误答案附带的代码所示，Java HashMap使用了一种经典的方法，如果你很幸运(你要查找的条目是bucket中的第一个)，你会得到O(1)。

如果你运气不太好，或者你的哈希函数质量很差(假设最坏的情况是，所有元素都映射到同一个哈希键)，为了避免在bucket中迭代普通链表时遇到可怕的O(n)，Java的实现使用TreeMap来提供O(logn)的复杂性。

因此，如果使用正确，Java的hashmap基本上应该会产生O(1)替换，如果使用不正确，则会优雅地降低到O(logn)复杂性。阈值在TREEIFY中(例如，在现代实现中，值为8)。

请查看来源中的这些实施说明：https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/HashMap.java#L143-L231

Answer 3

基础知识：

• java.util.HashMap将调整自身大小以匹配给定数量的元素
• 所以碰撞非常罕见(与n相比)
• (对于冲突，)现代HashMap实现在bucket中使用Trees(Node和TreeNode)

在一次替换/包含/put/get操作中，桶碰撞，

• 如果n中有k个桶碰撞，那就是k
• 其与树搜索一起被简化为O(log2(k))
• 在O表示法中，k是一个小数字，它等价于O(1)

此外，最坏情况下，哈希冲突：

• 如果你有一个真正的哈希生成器，它总是给出相同的结果
• 所以我们得到散列冲突
• 对于散列冲突，Node实现的功能类似于LinkedList
• 您将具有(使用这种类似LinkedList的搜索)O(n/2)=O(n)复杂性
• 但这必须是故意的，因为
• 只要没有太多相同的hashCode()，主因子分布和主数模得到非常好的分布
• 大多数IDE或简单的id排序(如数据库中的主键)将提供近乎完美的分布
• • 有了id排序的散列函数，就不会有任何(散列或bucket)冲突，所以实际上可以只使用数组索引，而不是散列函数和冲突处理

此外，请自己查看注释和代码：https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

• tableSizeFor(int cap)
• getNode()

具体而言：

• 设置bucket数组的表大小越来越接近于使用素数，基本上是2^n - 1
• 获取bucket为first = tab[(n - 1) & hash])，"first"为bucket
• • ，正如我所说，这不是一个模运算，只是一个逐位AND
• • • 更快
• • • 可以使用更多有效位
• • • 并产生可比较分布的结果

为了说明如何自己研究这一点，我写了一些显示最坏情况(哈希冲突)行为的代码：

import java.util.HashMap;
public class TestHashMapCollisions {
static class C {
private final String mName;
public C(final String pName) {
mName = pName;
}
@Override public int hashCode() {
return 1;
}
@Override public boolean equals(final Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
final C other = (C) obj;
if (mName == null) {
if (other.mName != null) return false;
} else if (!mName.equals(other.mName)) return false;
return true;
}
}

public static void main(final String[] args) {
final HashMap<C, Long> testMap = new HashMap<>();
for (int i = 0; i < 5; i++) {
final String name = "name" + i;
final C c = new C(name);
final Long value = Long.valueOf(i);
testMap.put(c, value);
}
final C c = new C("name2");
System.out.println("Result: " + testMap.get(c));
System.out.println("End.");
}
}

程序：

• 使用IDE
• 将您正在使用的JDR/JRE的源代码链接到IDE
• 为线路System.out.println("Result: " + testMap.get(c));设置断点
• 在调试中运行
• 调试器在断点处停止
• 现在进入HashMap实现
• 在HashMap.getNode()(Node<K,V>[] tab; Node<K,V> first, e; int n; K k;)的第一行设置断点
• 恢复调试；调试器将在HashMap内停止
• 现在，您可以按照调试器的步骤进行操作

提示：(您可以立即在HashMap中设置断点，但这会导致一些混乱，因为HashMap在JVM初始化时经常使用，所以在测试代码之前，您会先遇到很多不需要的停止)