HashMap#replace 的复杂度是多少？

Question

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

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

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

Answer 1

tl:博士

HashMap#replace runs in O(1) amortized;

并且在地图 适当平衡 的前提下，Java 在您的 put 和 remove 调用期间负责， 也未摊销。

非摊销

它是否也适用于非摊销分析 取决于 关于已实施 自平衡机制的问题 .

基本上，由于replace只改变了值，不影响散列和HashMap的一般结构，替换值不会触发任何重新散列或重新组织内部结构。

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

桶的大小，如果地图适当地自我平衡，可以被认为是一个常数。导致 O(1) replace 也未摊销。

但是，该实现仅基于启发式因素触发自平衡和重新散列。对此的深入分析有点复杂。

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

实施

为了确定，让我们来看看 current implementation (Java 16):

@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 中是空的。 O(1) 中除了 getNode 运行s 之外的所有内容都是微不足道的。

`getNode`

getNode 是在 HashMap 中定位条目的规范实现，我们知道运行s 在 O(1) 中用于适当的自平衡映射，例如Java 的实施。让我们来看看 code:

/**
 * 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)，然后在 table first = tab[(n - 1) & (hash = hash(key))] 中查找散列并开始遍历存储在存储桶中的数据结构。

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

桶

桶是简单的隐式链表或红黑树。

链表

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

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

显然 O(m) 中有运行，其中 m 是链表的大小。

红黑树

对于red-black-tree，我们有

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

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

桶大小

Javas 实现确保在检测到它失控时通过重新散列来重新平衡桶（你为每个修改方法支付，如 put 或 remove).

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

结论

有效地使存储桶大小不变，使 getNode 运行变为 O(1)，导致 replace 运行变为 O(1) ] 还有。

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

随时深入研究代码，但它会变得有点复杂。

Answer 2

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

一旦我们找到正确的位置，用新值替换关联值的时间复杂度为 O(1)。但查找仅摊销 O(1).

如 Zabuzard 的 不正确 答案附带的代码所示，Java HashMap 使用经典方法，如果你幸运的话（你正在寻找的条目是桶中的第一个）你得到 O(1).

如果你不那么幸运或者你的散列函数质量很差（假设最坏的情况，所有元素都映射到同一个散列键），以避免遇到可怕的迭代普通链表的 O(n)在存储桶中，Java 的实现使用 TreeMap 来提供 O(log n) 复杂度。

所以 Java 的 hashmap 如果使用正确，应该基本上产生 O(1) 替换，如果使用不当，将优雅地降级到 O(log n) 复杂度。阈值在 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 实现在桶内使用树（Node 和 TreeNode）

在一次 replace/contains/put/get 操作中， 桶冲突 ，

如果你有 k 个 桶碰撞 ，共 n 个，那就是 k，
树搜索减少到 O(log2(k))
在 O 表示法中，k 是一个小数，相当于 O(1)。

此外，最坏的情况，散列冲突：

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

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

tableSizeFor(int cap)
getNode()

具体来说：

设置桶数组的 table 大小接近于使用质数，基本上是 2^n - 1
得到桶是first = tab[(n - 1) & hash])，'first'是桶
- 正如我所说，这不是模运算，而只是按位与，
- - 哪个更快，
- - 可以使用更多有效位
- - 并产生相对分布的结果

为了说明如何自己研究这个问题，我写了一些代码来展示最坏情况（哈希冲突）的行为：

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
link 您正在使用的 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初始化的时候用的很频繁，所以在你开始测试你的代码之前，你会先遇到很多不需要的停顿)

HashMap#replace 的复杂度是多少？

What is the complexity of HashMap#replace?

java

algorithm

hashmap

time-complexity

tl:博士

非摊销

实施

`getNode`

桶

链表

红黑树

桶大小

结论