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 at jdk8-b120 · openjdk/jdk · GitHub

理论上System.identityHashCode()返回的hash值已经是均匀分布的了，那为什么还要多一个移位运算而不是直接和length - 1进行AND运算呢？

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

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

Answer 1

代码中的注释说：

"Implementation note: This is a simple linear-probe hash table, as described for example in texts by Sedgewick and Knuth. The array alternates holding keys and values."

实际上 hash 方法 return 是一个用作数组直接索引的值。例如：

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 需要 return 一个偶数。 hash 中的计算确保索引是均匀的，而不会丢弃 System.identityHashCode(x) 值的底部位。

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

好吧，答案在于 System.identityHashCode 的实现方式。实际上，有多种生成哈希的算法，所使用的算法（在运行时）取决于一个晦涩的 JVM 命令行选项。

一些算法（名义上）均匀分布在 int 的范围内。对于那些，丢弃底部位就可以了。
其他算法不是这样的。其中一种算法使用简单的全局计数器。另一个使用对象的内存地址，删除了低 3 位。如果选择这些算法，丢弃 LSB 会增加 IdentityHashMap.
中哈希冲突的概率

有关 IdentityHashcode 算法及其选择方式的详细信息，请参阅 https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-code/。请注意，JVM 行为的这一方面是未指定的，并且可能是特定于版本的。

Answer 2

我的预感是它旨在解决两个问题。

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

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

为了确保事情在 table 中分散开来，因此我们希望将哈希码的低位与哈希码的高位“混合”。减去 h << 8 的效果是将身份哈希码的低位向上移动，翻转它们，然后将它们添加回哈希码，从而在加法运算时产生一堆“涟漪”。我认为（？）这是一种有效的方法，可以将更高熵的低位注入高位，一旦 table 开始变得越来越大，就可以在插槽数组上提供更均匀的散列。

IdentityHashMap.hash() 中这段代码的用途是什么？

What is the purpose of this code in IdentityHashMap.hash()?

java

hash

java-8

hashmap

bit-shift