Java HashMap treeify() 为什么要比较同一个桶中节点的哈希值？

Question

我目前正在研究 Java 中 HashMap 实现的内部结构。我注意到在 treeify() 方法中有些我无法完全理解的东西。 这是我所指的 treeify() 方法的部分：

if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;

我的理解是，HashMap 中同一存储桶中的项目往往具有相同的内部哈希代码，因为这是首先用于将它们分配到该存储桶的内容。如果是这样的话，那么这些比较同一桶内节点的内部哈希码的代码永远不会计算为 true。

所以我的问题是：为什么treeify()需要比较这些哈希码？是否存在同一存储桶中的项目可以具有不同内部哈希码的情况？换句话说，是否存在上述条件成立的情况？如果不是，那不是就没有必要比较内部哈希码了吗？

最后，treeify()方法主要使用Comparable接口和tieBreakOrder()方法来对树中的项目进行排序，因此使用几行代码来比较看起来相同的哈希值似乎很奇怪。 任何对此的见解将不胜感激。预先感谢！

Answer 1

不使用哈希码（*）本身，而是使用哈希码对存储桶数取模来选择存储桶。例如，在

putVal()

中，桶号

i

计算为

(n - 1) & hash

:

    if ((p = tab[i = (n - 1) & hash]) == null)
       tab[i] = newNode(hash, key, value, null);

对于 16 个键的存储桶的默认起始数量，哈希码为 0、16、32 等，所有最终都在同一个存储桶 0 中。

由于树化是在同一存储桶中有许多条目并且这些条目可以具有不同的哈希码时开始的，因此在开始比较之前首先按哈希码排序来构建树是有意义的（这可能需要更长的时间，例如对于长字符串）。

---

*）实际上它并没有直接使用调用

key.hashCode()

的结果，而是使用以下函数：

 static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在此函数中，对于非空键

h

分配键哈希码，然后将高 16 位异或到低 16 位，这会修改结果的低 16 位，但保持高 16 位不变。

因此第一个代码片段中

hash

的值仍然包含2^32个不同的值，这仍然大于桶数组的大小，这仍然意味着多个哈希码值映射到同一个桶。