java - 为什么 HashMap 在达到不需要的 TREEIFY_THRESHOLD 值时会调整大小？

Question

我知道 HashMap 内部是如何工作的。但是，在使用 TreeNode 实现检查 HashMap 代码时，我没有得到存储桶大小增加背后的目标，但直到存储桶大小达到 MIN_TREEIFY_CAPACITY = 64

之前，我没有得到 treeify 的目标。

注意:我考虑过 Map m = new HashMap(); 因此默认大小为 16。

默认值。

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

HashMap#putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

我从 putVal 方法中提取了几行。

else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

因此，每当 binCount 达到 7 时，它就会调用 treeifyBin(tab, hash); 现在让我们按照方法 treeifyBin 中的代码进行操作。

HashMap#treeifyBin(Node[] tab, int hash)

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        ....
    }
}

为什么？ 在此方法中，首先 IF 检查当前 tab 大小是否小于 MIN_TREEIFY_CAPACITY = 64，然后调用 resize().它在内部将 tab 大小从默认的 16 增加到 32 并将所有元素转移到新的 tab。再次32 到 64。我认为这是开销或不必要的。

那么这背后的目标是什么？在 putVal 中使用 TREEIFY_THRESHOLD 检查大小，但在达到 MIN_TREEIFY_CAPACITY 之前不执行 treeify。

Answer 1

无论是使用树还是比平常更大的容量，都是处理冲突的措施。当有多个key映射到同一个bucket时，可能是以下场景之一(或它们的组合):

1. 键具有不同的哈希码，但映射到同一个存储桶
2. 键具有相同的哈希码，但实现 Comparable
3. key 具有相同的哈希码，并且未实现 Comparable

这两种方法都无法解决第三点。只有 build 一棵树才能解决第二个问题。当我们遇到第一种情况时，扩展表可能会解决问题，如果确实如此，它的优点是仍然提供 O(1)查找并允许更有效的遍历(只需迭代数组)，而树有 O(log n)查找和遍历效率较低，需要沿树结构下降。

问题是，分析场景、找出适用的解决方案以及扩展表是否确实有帮助，这本身就需要时间。此外，当单个 put 时，它不会得到返回。花费分析的费用来驳回策略，只是为了得到下一个 put寻找适合另一个key的策略(毕竟扩大表大小对整个表有影响)。

因此，我们使用启发式方法来适应 HashMap 的可能性和典型用例。 ，不仅仅是一个put手术。请注意，对于较小的表大小，通过扩展解决存储桶冲突的机会较高，表大小为 16 意味着仅使用 4 位哈希码，而表大小为 32 意味着使用 5 位，多出 25%。

我想，JDK 团队使用了对现实应用程序和库进行基准测试的常用方法来找到正确的权衡。