Java高频面试之集合-12
hello啊，各位观众姥爷们！！！本baby今天来报道了！哈哈哈哈哈嗝🐶
面试官：HashMap 的 hash 函数是怎么设计的?
HashMap的hash函数设计核心在于减少碰撞、提高数据分布均匀性，具体实现分为以下步骤：
1. 扰动函数处理
对键的原始hashCode进行高位与低位异或，增加低位随机性：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 作用：将hashCode的高16位右移后与低16位异或，使得高位信息参与低位运算，避免仅依赖低位导致碰撞率升高。
2. 下标计算
通过(n-1) & hash确定数组索引：
- n为2的幂（如默认16），
n-1的二进制全为1（例如15对应1111），位与操作等效于取模运算（但效率更高）。 - 优势：位运算比取模快，且保证下标均匀分布在数组范围内。
3. 碰撞优化
- 链表与红黑树：当链表长度≥8时转为红黑树（查找时间复杂度O(log n)），长度≤6时恢复链表，平衡性能与空间。
- 扩容机制：负载因子默认0.75，当元素数超过阈值时扩容为原数组2倍，重新分配元素位置。
关键设计思想
| 设计要点 | 实现方式 | 作用 |
|---|---|---|
| 高位扰动 | 异或操作（h ^ (h >>> 16)） | 减少低位重复导致的碰撞 |
| 高效取模 | 位运算（(n-1) & hash） | 替代取模运算，提高速度 |
| 动态数据结构 | 链表（O(n)）与红黑树（O(log n)）自动转换 | 避免极端情况下性能退化 |
| 负载因子 | 默认0.75（空间与时间折中） | 控制扩容阈值，平衡内存使用率和查询效率 |
示例说明
假设键的hashCode为0x12345678，数组长度n=16：
- 扰动计算：
0x12345678 ^ (0x12345678 >>> 16) = 0x12345678 ^ 0x00001234 = 0x1234444C。 - 确定下标：
(16-1) & 0x1234444C = 15 & 0x444C = 12（最终存储到数组第12个位置）。
通过这种设计，HashMap在大多数情况下能高效处理数据插入与查询，同时保持较低的碰撞概率。
