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

Question

我知道HashMap是如何在内部工作的。但是，在检查的HashMap代码树节点实现我没有收到桶的大小增加背后的目标，但不是treeify直到桶大小命中MIN_TREEIFY_CAPACITY = 64。

注意：我考虑过，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，布尔退出）

我从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）; 现在让我们按照method中的代码进行操作treeifyBin。

HashMap＃treeifyBin（Node []选项卡，int哈希）

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 = 64then resize()。内部将tab大小从默认的16增加到32，并将所有元素传输到新选项卡。并再次32至64。我认为这是开销或不必要的。

那么，这背后的目标是什么？用TREEIFY_THRESHOLDin 检查大小，putVal但直到命中时才进行树化MIN_TREEIFY_CAPACITY。

Answer 1

无论是使用树还是使用比平常大的容量，都是处理冲突的措施。当有多个键映射到同一存储桶时，它可以是以下情况之一（或它们的组合）：

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

两种方法都不能处理第三点。只有建造一棵树才能应对第二棵树。当我们遇到第一种情况时，扩展表可能会解决问题，如果可以，则它的优点是仍提供O(1)查找并允许更有效的遍历（仅遍历数组），而树具有O(log n)查找且效率较低的遍历，需要下降树结构。

问题在于分析方案，以找出适用的解决方案以及扩展表是否真正有帮助，这需要花费一些时间。此外，当一个人put以分析为代价而放弃某项策略时，它不会有回报，只是最终导致下一个put发现该策略适用于另一个键（毕竟，扩大表的大小会对整个表产生影响）。表）。

因此，启发式方法用于适应的可能性和典型用例HashMap，而不仅仅是合并单个put操作。请注意，对于较小的表大小，通过扩展解决存储桶冲突的机会更高，表大小为16意味着只使用4位哈希码，而表大小为32意味着使用5位，即多25％。

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