我正在阅读一个事实,即 HashMap
究竟如何?在 java
工作.我在 hash
中找到了代码HashMap
中的方法类 hashcode
是 Shift right zero fill operator
的操作数之一.其他operands
就像12
7
4
20
.稍后对结果进行更多处理。我的问题是为什么只选择这四个数字来计算哈希函数中的值,而哈希函数实际上用于计算在桶中的位置
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
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);
}
最佳答案
并不是说“只选择这四个数字来计算哈希函数的值”,关键对象的hashCode
方法返回的哈希码是(非常重要的)输入。 HashMap
实现中的这个方法只是试图改进这一点,因为知道 HashMap
之后将如何使用该值。
典型的实现将只使用哈希码的低位,因为内部表的大小是 2 的幂。因此,改进应确保即使不同 key 的原始哈希码仅在高位不同,低位具有不同值的可能性也是相同的。
以用作键的 Integer
实例为例:它们的散列码与它们的值相同,因为这会将散列码分布在整个 2³² int 范围内。但是,如果将值 0xa0000000
、0xb0000000
、0xc0000000
、0xd0000000
放入 map 中,则 map 仅使用较低的位会产生较差的结果。此改进解决了这个问题。
为这个位操作选择的数字,以及一般的算法是一个持续研究的领域。随着开发永无止境,您将看到 JVM 实现之间的变化。
关于java - 为什么在 `HashMap Class` 中的哈希函数中使用 4,20,12,7 这样的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20263579/