数据结构

当你调用 put(key, value) 时，底层到底发生了什么？ 为什么不直接用 key.hashCode()，而是要进行一次 (h = key.hashCode()) ^ (h >>> 16) 的异或运算？ 扰动函数：为什么要做异或 (^) 和无符号右移 (>>>)？ 如果直接使用 hashCode()，在数组长度 $n$ 较小时（比如默认的 16），只有哈希值的低位参与了 (n-1) & hash 的运算。 问题：如果一堆 Key 的高位差异很大，但低位正好相同，它们就会撞在同一个桶里。 解决：(h = key.hashCode()) ^ (h >>> 16) 实际上是将哈希值的高 16 位与低 16 位进行异或。 面试表达：这叫"扰动函数"。它的目的是混合原始哈希值的高位和低位，以此加大低位的随机性，使得即使数组长度很小，高位特征也能传播到低位，从而显著减少哈希冲突。 如何通过哈希值快速 找到它在数组中的下标？（提示：这和数组长度必须是 2 的幂次方有关）？ 经过一个，当容量 $n$ 是 2 的幂次方时，$hash \pmod n$ 等价于 $hash \ & \ (n-1)$。 在 CPU 层面，位运算 & 的效率远高于取模运算 %。