2

为什么容量必须是倍数或2？为什么在 indexFor 函数中使用“&”？为什么要重新计算哈希函数中的哈希而不是直接使用密钥的哈希码？

我认为此实现与“算法简介”中的描述之间存在一些重要差异。

“>>>”是什么意思？

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);
}

谁能给我一些指导？如果有人可以解释哈希算法，我将不胜感激。非常感谢！

4

2 回答 2

5

这是性能优化。将哈希码映射到表索引的常用方法是

table_index = hash_code % table_length;

%运营商很贵。如果table_length是 2 的幂，则计算：

table_index = hash_code & (table_length - 1);

相当于（很多）更昂贵的模运算。

于 2012-04-03T21:34:28.023 回答
0

不要理会窗帘后面的人。

实际的算法无疑是开发人员“感觉良好”的组合，修复了一些奇怪的退化情况，以及简单的传统（用户经常为此开发模糊的依赖项）。

请注意：

 * 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.

网：只要能用，性能好，你无所谓。

于 2012-04-03T21:46:02.647 回答