我在使用 JDK1.8 的 HashMap 时遇到了一些麻烦

Question

这是部分代码。当节点长度超过7时，它会将Node转为TreeNode，但在函数treeifyBin()中，如果tab长度小于64则只执行resize()。

// binCount is length of Node,  TREEIFY_THRESHOLD is default 8
if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

// tab is Node[],  MIN_TREEIFY_CAPACITY is default 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

我不明白为什么节点长度与 resize() 有关。

Answer 1

如你所知，从java-8 hashmap的内部工作变化随着内部链表达到阈值它被转换为树（具体为RB树）。转换树的逻辑取决于长度桶中的节点，因此在将列表转换为树之前值得检查是否可以仅通过调整链表的大小而不是将列表转换为树来插入节点，这是昂贵的操作。这里还需要考虑一件事，因为频繁从地图中删除可能会导致树再次转换回列表，因此在您的 treeifybin() 方法中，检查调整大小，然后您的当前结构更改为树。

有关更多信息，请查看以下内容： http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

干杯:)

Answer 2

创建HashMap的核心objective是，你想在常数时间O(1)内检索一个值。但是，当您发生碰撞时，它不会保持 O(1)。如果发生冲突，您必须在链表或树中搜索密钥。

这里是函数 treeifyBin()。这意味着你已经遇到了碰撞。但我们讨厌碰撞。一定想避免碰撞。但是创建树需要很多工作。因此，在创建树之前，我们检查数组（或选项卡）是否仍然足够小（< MIN_TREEIFY_CAPACITY）。如果是，我们不创建树，而是增加数组的大小以避免冲突。

现在让我们看看增加数组大小是如何避免冲突的。假设初始数组大小为 16。现在要将哈希码映射到数组索引，您可以执行按位与 (hashCode & (sizeOfArray - 1))。这里，(16-1)的二进制是1111。如果哈希码是 17（二进制 = 10001），在按位与之后，你得到的只是 0001 即 1。现在，如果你调整大小，你的数组大小将是 32。因此 (sizeOfArray - 1) = 11111.现在，如果您使用相同的哈希码 17 执行按位 AND，您将得到 10001，即 17。因此，该元素将从 tab [1] 移动到 tab[17]。如果之前发生冲突的另一个密钥的哈希码早先为 1 或 33，它仍会进入 tab[1]。

我在使用 JDK1.8 的 HashMap 时遇到了一些麻烦

I have some troubles with HashMap from JDK1.8

java

resize

hashmap