java - 关于Java HashMap的实现

Question

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

我认为这个实现和“算法简介”中的描述有一些重要的区别。

“>>>”是什么意思？

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

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

Answer 1

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

table_index = hash_code % table_length;

% 操作符是昂贵的。如果table_length是2的幂，那么计算:

table_index = hash_code & (table_length - 1);

相当于(多)更昂贵的模运算。