java中的hash（）实现

Question

我正在研究Java中的HashMap类。我的理解是哈希表的容量是桶数的2次方(容量16表示四个桶)。当调用put(key，value)时，key.hashCode()输出一个整数，这个新添加的(key，value)对基于key . hashcode()%的桶数放置。但是下面是HashMap.class中的实际实现

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

从上面的代码中，我无法理解如何安装钥匙。将hashCode（）值转换为bucket。

Answer 1

该代码不“适合”hashCode到bucket，它“只是”散播哈希代码，使高位更重要。这里是该方法的javadoc。

计算key.hashCode()并将哈希的高位扩展(异或)到低位。因为该表使用2的幂掩码，所以仅在当前掩码之上的位不同的散列集将总是冲突。(已知的例子包括在小表格中保存连续整数的多组浮动键。)所以我们应用了一个向下扩展高位影响的变换。在位扩展的速度、效用和质量之间有一个折衷。因为许多常见的散列集合已经被合理地分布(因此不受益于扩散)，并且因为我们使用树来处理箱中的大量冲突集合，所以我们只是以最便宜的可能方式异或一些移位的位来减少系统损失，以及合并最高位的影响，否则由于表的界限，这些最高位将永远不会在索引计算中使用。

对存储桶的实际拟合是在getNode（int，Object）方法中完成的：

first = tab[(n - 1) & hash]

其中哈希是哈希（对象）的结果，n 是哈希表的大小。

Answer 2

这可能会有所帮助。如果我们要添加十个带有从 1 到 10 的浮动键的项目。

        Map<Float, String> map = new HashMap<>();
        int numOfBuckets = 64; // HashMap will have 64 bins after inserting 10 items

        String format = "|%1$-5s|%2$-35s|%3$-25s|%4$-35s|%5$-25s|%6$-25s|\n";
        System.out.format(format, "i", "raw binary", "right-shifted 16 bits", "rehashed", "bucket before rehashed",
                "bucket after rehashed");

        for (int i = 1; i <= 10; i++) {
            float key = i;
            int rawInt = Float.floatToRawIntBits(key);
            String binaryString = Long.toBinaryString(rawInt);
            String shifted16BitsString = Long.toBinaryString(rawInt >>> 16);

            int rehashed = rawInt ^ rawInt >>> 16;
            String rehashedString = Long.toBinaryString(rehashed);

            // HashMap calculates bin index with (n - 1) & hash
            String bucketBeforeRehashed = Long.toString((numOfBuckets - 1) & Objects.hashCode(key));
            String bucketAfterRehashed = Long.toString((numOfBuckets - 1) & rehashed);

            System.out.format(format, i, binaryString, shifted16BitsString, rehashedString,
                    bucketBeforeRehashed, bucketAfterRehashed);
            map.put(key, Integer.toString(i));
        }

它产生：

|i    |raw binary                         |right-shifted 16 bits    |rehashed                           |bucket before rehashed   |bucket after rehashed    |
|1    |111111100000000000000000000000     |11111110000000           |111111100000000011111110000000     |0                        |0                        |
|2    |1000000000000000000000000000000    |100000000000000          |1000000000000000100000000000000    |0                        |0                        |
|3    |1000000010000000000000000000000    |100000001000000          |1000000010000000100000001000000    |0                        |0                        |
|4    |1000000100000000000000000000000    |100000010000000          |1000000100000000100000010000000    |0                        |0                        |
|5    |1000000101000000000000000000000    |100000010100000          |1000000101000000100000010100000    |0                        |32                       |
|6    |1000000110000000000000000000000    |100000011000000          |1000000110000000100000011000000    |0                        |0                        |
|7    |1000000111000000000000000000000    |100000011100000          |1000000111000000100000011100000    |0                        |32                       |
|8    |1000001000000000000000000000000    |100000100000000          |1000001000000000100000100000000    |0                        |0                        |
|9    |1000001000100000000000000000000    |100000100010000          |1000001000100000100000100010000    |0                        |16                       |
|10   |1000001001000000000000000000000    |100000100100000          |1000001001000000100000100100000    |0                        |32                       |

我们可以从输出中发现，键的下位都是 0，这导致所有项目都被分配到同一个箱子。但是在执行右移和异或后，分布会变得更好。我认为这是 HashMap 的 hash（） 方法中的源代码注释中描述的情况。