这个代码在IdentityHashMap.hash()中的用途是什么

Question

/**
* Returns index for Object x.
*/
private static int hash(Object x, int length) {
int h = System.identityHashCode(x);
// Multiply by -127, and left-shift to use least bit as part of hash
return ((h << 1) - (h << 8)) & (length - 1);
}

来自：jdk/IdentityHashMap.java在jdk8-b120·openjdk/jdk·GitHub

理论上，System.identityHashCode()返回的哈希值已经是均匀分布的，那么为什么会有一个额外的移位运算，而不是与length - 1的直接AND运算呢？

该实现似乎保证最低比特是0，以确保计算结果是偶数，因为该实现要求所有键都在偶数索引上，所有值都在奇数索引上。

当System.identityHashCode((被实现为内存地址或递增值时，h << 8似乎混合了低位和高位来处理这种情况，不清楚为什么这里只移位了8位，而不是像HashMap.hash()这样的东西也移动了16位。

Answer 1

代码中的注释说：

"实现说明：这是一个简单的线性探测哈希表，例如Sedgewick和Knuth在文本中描述的。数组交替持有键和值">

实际上，hash方法返回一个值，该值用作数组的直接索引。例如：

public V get(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
while (true) {
Object item = tab[i];
if (item == k)
return (V) tab[i + 1];
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}

这意味着hash需要返回一个偶数。hash中的计算确保了索引是偶数，而不会丢弃System.identityHashCode(x)值的底部位。

为什么不直接扔掉底部的部分呢？

答案在于System.identityHashCode的实现方式。实际上，有多种算法用于生成哈希，并且(在运行时(使用的算法取决于一个模糊的JVM命令行选项。

• 一些算法(理论上(均匀分布在int的范围内。对于那些人来说，丢弃最底层的比特就可以了。

• 其他算法不是这样的。其中一个算法使用了一个简单的全局计数器。另一个使用对象的内存地址，去掉了底部的3位。如果选择了这些算法，则丢弃LSB将增加IdentityHashMap中哈希冲突的概率。

请参阅https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-code/有关CCD_ 12算法以及如何选择它们的更多信息。请注意，JVM行为的这一方面是未指定的，并且可能是特定于版本的。

Answer 2

我对这里发生的事情的预感是，它旨在解决两个问题。

首先，此函数生成的槽索引必须是偶数。(实现将键存储在偶数表槽中，将值存储在奇数表槽中。(这意味着无论返回什么索引，其最后一位都必须等于零。

其次，使用的身份散列码(可能(基于内存地址，内存地址的低位比高位"更随机"。例如，如果我们分配一个对象列表，并且分配器将它们全部连续地放在内存中，那么它们的地址都将具有相同的高位但不同的低位。(或者可能只有一个对象的全局计数器，在创建对象时会递增。在这种情况下，对象哈希的低位也会比高位具有更宽的离散度。(

因此，为了确保事情在表中展开，我们希望将哈希代码的低位与哈希代码的"高位"混合"。减去h << 8的效果是将身份哈希码的低位向上移动，翻转它们，然后将它们添加回哈希码，在添加过程中引起一堆"涟漪"。我认为(？(这是一种有效的方法，可以将熵更高的低位注入高位，一旦表开始变得越来越大，就可以在插槽阵列上提供更均匀的哈希。