hashmap哈希值计算先通过扰动函数(h = key.hashcode()) ^ (h >>> 16)将高位信息混入低位，再用(n - 1) & hash定位下标，既提升分布均匀性又适配2的幂数组的高效位运算寻址。
HashMap 的哈希值计算和寻址不是简单调用 hashCode() 就完事，而是经过扰动 + 位运算两步关键处理，目的是让高位参与运算、减少冲突，并适配数组下标定位的高效性。
哈希值怎么算：扰动函数是关键
直接用对象的 hashCode() 值容易导致低位重复、高位闲置，尤其当数组容量较小时，只看低几位会造成大量哈希碰撞。JDK 8 引入了扰动函数：
-
static final int hash(Object key)源码逻辑是：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) - 先取原始 hashCode（32 位整数），再将其无符号右移 16 位，与原值做异或（^）
- 效果是：把高 16 位“混合”进低 16 位，让整个 32 位都参与后续寻址，显著提升散列均匀性
寻址怎么算：(n - 1) & hash 是核心公式
得到扰动后的 hash 值后，要把它映射到数组有效下标（0 到 n-1）。HashMap 不用 hash % n，而是用位运算：
- 公式：
i = (n - 1) & hash，其中n是数组长度（必须是 2 的幂，如 16、32、64…） - 因为
n是 2 的幂，n - 1的二进制全是 1（例如 16 → 15 →1111），所以&运算等价于取 hash 的低 log₂(n) 位 - 比取余快得多，且能保证下标落在 [0, n-1] 范围内，分布更均匀
为什么容量必须是 2 的幂
这是位运算寻址成立的前提：
- 如果 n=16（
10000），n−1=15（01111），hash & 15只保留 hash 最低 4 位，刚好对应 0~15 共 16 个下标 - 如果 n=15（非 2 的幂），n−1=14（
01110），hash & 14会丢失某些下标（比如永远得不到奇数下标 1、3、5…），造成严重不均 - 扩容时也是翻倍（×2），天然维持 2 的幂特性
哈希冲突后怎么处理
即使做了扰动和位运算，不同 key 仍可能算出相同下标（即哈希碰撞）。HashMap 采用链地址法解决：
- 数组每个位置（桶）存一个链表头节点；冲突时，新节点插入链表尾部（JDK 7 是头插，JDK 8 改为尾插）
- 当链表长度 ≥ 8 且数组长度 ≥ 64 时，该链表转为红黑树，把最坏查询从 O(n) 优化到 O(log n)
- 查找时，先通过 (n−1) & hash 定位桶，再遍历链表或树，用
==或equals()判定 key 是否相等
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
