HashMap#hash(int)方法说明
有人能给我解释一下静态的HashMap#hash(int)方法吗？
生成均匀分布的散列背后的理由是什么？
/**
* 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);
}举个例子会让它更容易理解。
澄清我知道运算符，真值表和按位运算。我真的不能解码实现，也不能真正解码注释。甚至是它背后的原因。
回答 2
Stack Overflow用户
发布于 2010-03-10 10:33:11
>>>是逻辑右移位(无符号扩展) (JLS 15.19 Shift Operators)，^是按位异或(JLS 15.22.1 Integer Bitwise Operators)。
至于为什么要这样做，文档提供了一个提示：HashMap使用2的幂长度表，并通过屏蔽掉较高的位并只取其哈希码的较低位来散列关键字。
// HashMap.java -- edited for conciseness
static int indexFor(int h, int length) {
return h & (length-1);
}
public V put(K key, V value) {
int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);
// ...
}所以hash()试图给高位带来相关性，否则就会被屏蔽掉(indexFor基本上丢弃了h的高位，只取length == (1 << k)的低位k位)。
与此形成对比的是，Hashtable (不应该有2次方的长度表)使用键的哈希码。
// Hashtable.java -- edited for conciseness
public synchronized V get(Object key) {
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % table.length;
// ...
}通过执行更昂贵的%操作(而不是简单的位掩码)，Hashtable的性能对低位分布较差的哈希码不太敏感(特别是当table.length是质数时)。
Stack Overflow用户
发布于 2010-03-10 11:21:04
我不知道所有的转变是如何工作的，但动机在评论中列出：
HashMap的实现方式依赖于hashCode函数的充分实现。特别是，散列值的低位应该均匀分布。如果在较低的位上有许多冲突，HashMap将无法正常运行。
因为hashCode的实现不受HashMap的控制(每个对象都可以实现它们自己的)，所以它们提供了一个额外的散列函数，该函数会稍微移动对象的hashCode，以确保低位更随机地分布。同样，我不知道这是如何工作的(或者它有多有效)，但我假设它至少取决于高位均匀分布(它似乎将高位网格化到低位中)。
因此，这样做是为了在存在实现不佳的hashCode方法的情况下尽量减少冲突(从而提高性能)。
https://stackoverflow.com/questions/2414117
复制相似问题
腾讯云开发者
