面试题目

当你调用 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 层面，位运算 & 的效率远高于取模运算 %。

put 的过程 1.hash 的过程进行hash扰动 将key的高位与地位进行异或，高位与低位进行异或 h = key.hashCode(); hash = h ^ (h >>> 16); 这样做的目的，是把高位信息混入低位。 因为数组下标的计算通常只用到低几位，如果只看原始 hashCode 的低位，容易导致分布不均。 2.根据哈希值定位数组下标 定位方式一般是： index = (n - 1) & hash 这里 n 是数组长度。 这样做比取模更高效，但前提是数组长度必须是 2 的幂次方。 这也是为什么 HashMap 的容量总会被维护成 2 的幂。 3.判断该位置是否为空 如果这个桶位置没有元素，那最简单： 直接创建一个 Node 放到这个位置 put 结束 这说明没有哈希冲突。 4.判断需要覆盖还是挂载 这时会分几种情况： 情况一：桶中第一个节点就是同一个 key 判断条件通常是： hash 相同 并且 key 相等，== 或 equals() 如果是同一个 key，就不是新增，而是 替换旧值。 也就是把旧 value 改成新 value，然后返回旧值。 情况二：当前桶是红黑树 如果这个桶里的结构已经不是链表，而是红黑树，那就按红黑树的方式插入或查找。 情况三：当前桶是链表 那就沿着链表往后找： 找到相同 key：替换 value 没找到：挂到链表尾部 ...