寻址算法

一、HashMap寻址完整流程

1. 获取原始哈希值：调用key.hashCode()，获取对象的原始哈希码
2. 二次哈希（扰动算法）：调用hash()方法，将原始哈希码的高16位与低16位异或运算，减少哈希冲突

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

3. 计算数组下标：通过(table.length - 1) & hash得到元素在数组中的索引位置

---

二、扰动算法原理：为什么要右移16位再异或？

• 原始哈希码的高16位通常变化较小，而低16位容易出现重复，直接用于寻址会导致大量冲突
• 右移16位将高16位移到低16位，再与原低16位异或，使高16位的信息也参与到低16位的计算中
• 结果：哈希值的分布更均匀，减少低位相同导致的哈希冲突，提升寻址效率

---

三、按位与运算比除法/取模快的底层原因

从CPU执行层面来看：

1. 指令复杂度差异：按位与（&）是单周期指令，而除法/取模（%）需要多周期计算，流水线阻塞时间长
2. 硬件实现差异：CPU的ALU中，按位运算单元比除法器更简单，执行延迟更低
3. 特殊优化支持：当除数是2的幂时，取模运算可被编译器优化为按位与，但HashMap直接使用&运算，避免了编译器优化的不确定性，性能更稳定

---

四、为什么数组长度必须是2的n次幂？

1. 寻址效率优化：当数组长度n是2的幂时，n-1的二进制全为1，hash & (n-1)的结果等价于hash % n，但按位与运算比取模运算快得多
2. 扩容迁移优化：扩容时数组长度翻倍（仍为2的幂），通过hash & oldCap判断元素位置：
   • 结果为0：元素留在原下标位置
   • 结果非0：元素迁移到原下标 + oldCap位置 无需重新计算哈希值，大幅提升扩容效率

---

五、面试高频问题解析

1. 问：HashMap的寻址算法是什么？答： 先通过key.hashCode()获取原始哈希值，再通过hash()方法（高16位与低16位异或）扰动计算，最后用(数组长度-1) & hash得到数组下标。

2. 问：为什么要使用扰动函数？答： 扰动函数将哈希码的高16位与低16位异或，使高16位的信息参与到低16位的计算中，减少低位相同导致的哈希冲突，让哈希值分布更均匀。

3. 问：为什么数组长度必须是2的幂？答： 一是为了让(n-1) & hash能替代取模运算，提升寻址效率；二是为了扩容时能通过hash & oldCap快速判断元素新位置，优化迁移效率。

4. 问：按位与运算为什么比除法快？答： 按位与是单周期指令，硬件实现简单，执行延迟低；除法是多周期指令，需要复杂的硬件电路和流水线阻塞，执行效率远低于按位运算。