为什么 HashMap(JDK1.8) 中的哈希计算不需要像 ConcurrentHashMap 那样考虑负哈希代码？

Question

InHashMap：(h = key.hashCode()) ^ (h >>> 16);

ConcurrentHashMap：(h ^ (h >>> 16)) & HASH_BITS;

其中HASH_BITS0x7fffffff，& HASH_BITS它总是一个正数。

Answer 1

为什么 HashMap(JDK1.8( 中的哈希计算不需要像 ConcurrentHashMap 那样考虑负哈希代码？

最终，在HashMap情况下，哈希为负(扩散后(的情况也确实需要考虑。 只是这发生在代码的后面。

例如，在getNode(Java 8(中，您可以找到以下内容：

Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {

由于tab.length是 2 的幂，因此tab.length - 1是将数组的hash简化为下标的合适位掩码。

您可以放心，在HashMap或ConcurrentHashMap的每个实现中，都有一些代码将哈希代码减少为适合用作下标的数字。 它会在那里...地方。

但也...不要指望这些类的代码易于阅读。 所有集合类都经过多次返工/调整，在各种测试用例中获得最佳(平均(性能。

Answer 2

实际上，它处理负索引计算。乍一看并不明显，但是在访问元素(键或值(时，某些地方有计算。

int index =(n - 1) & hash，其中n是表的长度

它只是处理负索引。

AFAIK，HashMap总是使用大小为 2 的数组(例如16、32、64等(。

假设我们有256(0x100(的容量，即2^8。 减去 1 后，我们得到256 - 1 = 255即0x100 - 0x1 = 0xFF减法产生在0到length-1之间获得正确的存储桶索引，并具有按位和哈希所需的精确位掩码。

256 - 1 = 255
0x100 - 0x1 = 0xFF

260(0x104( 的哈希与0xFF按位和运算以产生4的桶数。

257(0x101( 的哈希与0xFF按位和运算，以产生一个桶号1。