HashMap#replace的时间复杂度是多少？

Question

HashMap#replace的时间复杂度是多少？

javaalgorithmhashmaptime-complexity

7

我想知道对于 HashMap 中的 replace(Key, Value)方法，其时间复杂度是多少。

我的初步想法是它的时间复杂度为 O(1)，因为获取值的时间复杂度为 O(1)，而且我可以简单地替换与键相关联的值。

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

- a_confused_student

6

它的时间复杂度是O（1）摊销，就像containsKey、put或remove一样。如果不进行摊销分析，它可能是O（n），因为任何更改都可能触发重新哈希，潜在地涉及所有条目。但是没有人关心非摊销分析。 - Zabuzard

我想进一步阐述“但是谁关心非摊销分析。”：非摊销分析只在实时使用情况下有意义，其中必须强制执行每个项目的最大时间。几乎所有用例都更关心吞吐量和平均运行时间，然后非摊销用例就变得无关紧要了。 - Joachim Sauer

2

实际上，replace 只改变值，而值并不受哈希的影响。因此，它实际上与 get 或 contains 具有相同的复杂度。 - Zabuzard

1

@Zabuzard，这正是我想的，但是你第一条评论上的投票数让我觉得我可能错了:P。 - Yousaf

如果我使用一个相对较大的哈希表，你是说有可能出现所有内容都需要重新哈希的情况吗？ - a_confused_student

显示剩余3条评论

3个回答

3

你是对的，主要成本是查找，这是摊销 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 中（例如现代实现中的 value 是 8）。

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

- Yann TM

2

基础知识：

java.util.HashMap 会自动调整大小以匹配给定数量的元素
因此碰撞相对较少（与n相比）
（对于碰撞，）现代 HashMap 实现在桶内使用树形结构（Node 和 TreeNode）

在一次替换/包含/放置/获取操作中，桶碰撞，

如果您有 k 个 桶碰撞 中的 n 个，则为 k，
这将通过树搜索减少到 O(log2(k))，
在 O 表示法中，k 是一个小数，等同于 O(1)。

此外，最坏情况下，哈希碰撞：

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

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

tableSizeFor(int cap)
getNode()

具体来说：

为哈希桶数组设置表格大小已经接近使用质数，即基本上是 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
将您正在使用的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内设置断点，但这会导致一些混乱，因为当JVM初始化时经常使用HashMap，所以您会先遇到很多不需要的停止，然后才能测试您的代码)

- JayC667

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zabuzard · Accepted Answer

简述

HashMap#replace 的时间复杂度为 O(1)平均；

在映射表平衡的前提下，Java在您的put和remove调用期间会进行处理，这也是非平均的。

非平均

是否也适用于非平均分析的事实取决于所实现的自平衡机制。

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

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

如果地图自我平衡，则可以将桶大小视为常量，从而导致replace的时间复杂度为O(1)，也不是摊销的。

但是，实现仅基于启发式因素触发自平衡和重新哈希。对此进行深入分析有点更加复杂。

因此，由于这些启发式因素的存在，实际情况可能介于两者之间。

实现

为确保准确性，让我们来看看当前的实现（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中为空。除了getNode方法外，其他所有方法都可以轻松地运行在O(1)时间复杂度。

`getNode`

getNode是在HashMap中查找条目的规范实现，对于像Java实现的适当自平衡映射，我们知道它运行在O(1)时间复杂度。让我们来看一下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);

这显然在链表大小为 m 时运行时间为 O(m)。

红黑树

对于红黑树，我们有：

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

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

桶大小

Java的实现确保通过重新哈希来重新平衡桶，如果检测到它失控了（您需要在每个修改方法（例如put或remove）上付出代价）。

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

结论

有效地将存储桶大小设置为恒定值，使得getNode以O(1)运行，从而replace也以O(1)运行。

没有任何自我平衡机制，在最坏情况下，如果使用链接列表，则会降级为O(n)，对于红黑树的情况，则为O(log n)（如果所有键产生哈希碰撞）。

请随意深入研究代码，但代码稍微复杂一些。