了解奇怪的Java哈希函数
以下是java.util.HashMap散列函数的源代码。 这些评论足以说明它的成就。 但是如何？ 什么是^和>>>操作符在做什么？ 有人可以解释代码实际上是如何做评论说的吗？
/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
不知道“英文，但这里是一些代码和示例输出：
public static void main ( String[] args ) { int h = 0xffffffff; int h1 = h >>> 20; int h2 = h >>> 12; int h3 = h1 ^ h2; int h4 = h ^ h3; int h5 = h4 >>> 7; int h6 = h4 >>> 4; int h7 = h5 ^ h6; int h8 = h4 ^ h7; printBin ( h ); printBin ( h1 ); printBin ( h2 ); printBin ( h3 ); printBin ( h4 ); printBin ( h5 ); printBin ( h6 ); printBin ( h7 ); printBin ( h8 ); } static void printBin ( int h ) { System.out.println ( String.format ( "%32s", Integer.toBinaryString ( h ) ).replace ( ' ', '0' ) ); }
打印：
11111111111111111111111111111111 00000000000000000000111111111111 00000000000011111111111111111111 00000000000011111111000000000000 11111111111100000000111111111111 00000001111111111110000000011111 00001111111111110000000011111111 00001110000000001110000011100000 11110001111100001110111100011111
所以，代码将散列函数分解成多个步骤，以便您可以看到发生了什么。 第一次移动20个位置与12个位置的第二个移位创build一个掩码，可以翻转整数的最低20位中的0个或更多个。 所以你可以得到一些插入底部位的随机性，使用潜在更好的分布式更高的位。 然后通过xor将其应用到原始值以将该随机性添加到较低位。 7个位置的第二个移位或4个位置的移位创build了一个掩码，它可以翻转底部28位中的0个或更多个位，这通过利用先前的异或函数再次给较低位和一些更重要的位置带来一些随机性已经解决了一些较低位的分布。 最终结果是通过散列值更平滑地分配比特。
由于Java中的散列表通过将散列与散列数组合在一起来计算存储区索引，因此您需要散列值的低位的均匀分布来平均地将条目散布到每个存储区中。
至于certificate这个限制碰撞次数的说法，那个我没有任何意见。 此外，请参阅此处了解有关构build哈希函数的一些较好信息以及关于为什么两个数字的xor趋向于结果中随机分布位的一些细节。
>>>是一个零填充的bitshift。
^是XOR。
XOR也被称为“独占”或 – 它是一个math运算符，结合了两个数字。 见http://en.wikipedia.org/wiki/Exclusive_or
n的正确移位就像是从数字中删除n最低位。 所以如果这个数字是00010111 ，而你把它右移1，你会得到00001011 。
这里有一篇文章讨论了整数哈希函数和它们devise的一些注意事项。 这不是很详细，但重点是：
操作必须使用一连串的计算来实现雪崩。 雪崩意味着input中的一位差异会使得大约1/2的输出位不同。
基本上，目标是补充散列函数删除input中的任何规则，因为这些可能会导致散列表退化。
^是按位XOR ， >>>是位移 。
>>>似乎是一个无符号的右位移， ^是按位XOR
http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
它是按位异或和无符号右移的组合。
看到这里更多的解释： http : //www.roseindia.net/java/master-java/bitwise-bitshift-operators.shtml
