为什么 HashMap 在 index （n - 1） & hash 上插入新节点？

hashcode collections hashmap java hash

2022-09-03 10:07:23

为什么哈希映射在索引上插入新节点：tab[(n - 1) & hash]

其中和的数组。hash = key.hashCode() ^ key.hashCode() >>> 16n = tab.lengthNode<K,V>

为什么HashMap不像那样放置节点：？它只是另一个哈希函数，就像大多数方法中的乘以31一样吗？提前感谢您的解释！tab[hash]hashCode()

答案 1

哈罗德的一个很好的描述，但我觉得没有一个例子是不够的。所以这里有一个 -

每当创建新的 Hasmap 时，内部 Node[] 表的数组大小始终为 2 的幂，以下方法保证它 -

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

因此，假设您提供初始容量为 5

cap = 5
n = cap - 1 =  4 = 0 1 0 0
n |= n >>> 1;    0 1 0 0 | 0 0 1 0 = 0 1 1 0 = 6
n |= n >>> 2;    0 0 1 1 | 0 1 1 0 = 0 1 1 1 = 7
n |= n >>> 4;    0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7
n |= n >>> 8;    0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7
n |= n >>> 16;   0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7
return n + 1     7 + 1 = 8

所以表大小为 8 = 2^3

现在，您可以将元素放入 map 中的可能索引值为 0-7，因为表大小为 8。现在让我们看一下看跌期权方法。它查找存储桶索引，如下所示 -

Node<K,V> p =  tab[i = (n - 1) & hash];

其中 n 是数组大小。所以 n = 8。这和说是一样的

Node<K,V> p =  tab[i = hash % n];

因此，我们现在需要看到的就是如何

hash % n == (n - 1) & hash

让我们再次举个例子。假设值的哈希值为 10。

hash = 10
hash % n = 10 % 8 = 2
(n - 1) & hash = 7 & 10 = 0 1 1 1 & 1 0 1 0 = 0 0 1 0 = 2

希望这有帮助。更多详情

PS：上面的链接转到我的博客，其中有更详细的示例说明。

答案 2

因为可能超出范围。hash

“规范解决方案”是将哈希的（正）模与数组的长度取为一起，此代码使用数组具有二次幂长度的事实，用廉价的按位AND替换昂贵的模（模一常量优化得很好）。