有人可以向我解释一下静态 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);
}
举个例子会更容易理解。
澄清 我知道运算符、真值表和按位运算。我真的无法真正解码实现,也无法真正解码评论。甚至是背后的原因。
最佳答案
>>>
是逻辑右移(无符号扩展)( JLS 15.19 Shift Operators )和 ^
是按位异或(JLS 15.22.1 Integer Bitwise Operators)。
至于为什么这样做,文档提供了一个提示:HashMap
使用二次幂长度表,并通过屏蔽较高位并仅获取其哈希码的较低位来对 key 进行哈希处理。
// 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
的高位,并且只占用 k
的低 length == (1 << k)
位)。
将此与 Hashtable
的方式进行对比(不应该是长度表的二次幂)使用 key 的哈希码。
// Hashtable.java -- edited for conciseness
public synchronized V get(Object key) {
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % table.length;
// ...
}
通过做更昂贵的%
操作(而不是简单的位掩码),Hashtable
的性能对低位分布较差的哈希码不太敏感(尤其是如果 table.length
是素数)。
关于java - HashMap#hash(int)方法的解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2414117/