时间戳

首页 > 解决方案 > 为什么 HashMap 在达到不需要的 TREEIFY_THRESHOLD 值时会调整大小？

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

问题描述

我知道 HashMap 如何在内部工作。但是，在使用 TreeNode 实现检查 HashMap 代码时，我没有得到增加存储桶大小的目标，但直到存储桶大小达到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, 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并将所有元素转移到新选项卡。又是 32 到 64。我认为这是开销或不必要的。

那么这背后的目标是什么？TREEIFY_THRESHOLD用in检查大小，putVal但不做treeify直到它命中MIN_TREEIFY_CAPACITY。

标签： javajava-8hashmap

解决方案

两者，使用比平常更大的树或容量，都是处理冲突的措施。当有多个key映射到同一个bucket时，可以是以下场景之一（或它们的组合）：

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

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

问题是，分析场景，找出适用的解决方案以及扩展表格是否真的有帮助，这本身就需要时间。put此外，当一个人花费分析的费用来解雇一个策略时，它不会得到回报，只是为了最终put找到下一个适合另一个键的策略（毕竟，扩大表大小会影响整个桌子）。

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

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

推荐阅读