Hash()在Java中实现

Question

我正在Java中的Hashmap类。我的理解是，哈希表的容量为2的功率（容量16表示四个桶）。当put（键，值）被调用时，key.hashcode（）输出一个整数编号，并且基于key.hashcode（）％桶数的新添加（key，value）对。但是以下是hashmap.class

中的实际实现

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

从上面的代码中，我无法弄清楚key.hashcode（）值的拟合如何发生。

Answer 1

这可能会有所帮助。如果我们要添加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，这将导致所有项目分配给同一垃圾箱。但是在执行正确的偏移和XOR之后，分布会变得更好。我认为在hashmap的哈希（）方法中的源代码的评论中描述了这种情况。

Answer 2

该代码不"拟合"标记的标签，它"只是"扩展了哈希码，从而使上位更重要。在这里，该方法的Javadoc。

计算key.hashcode（）和扩展（XORS）更高的哈希至较低位。由于该表使用两个掩蔽功率，因此仅在当前掩码上方的位上只会碰撞的一组哈希。（在已知的示例中，有一组浮子键在小桌子中连续保持全数字。）因此，我们应用了一个转换，该转换散布了较高位的影响。速度，公用事业和位分布质量之间的权衡。因为许多常见的哈希集已经分布合理（因此不要从传播中受益），并且由于我们使用树木来处理垃圾箱中的大量碰撞，因此我们只是以最便宜的方式来减少系统性损失，所以以及纳入最高位的影响，否则由于表界限而在索引计算中永远不会使用。

在getNode(int, Object)方法中完成了对存储桶的实际拟合：

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

其中hash是hash(Object)的结果，n是Hashtable的大小。