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在大多数情况下能高效处理数据插入与查询,同时保持较低的碰撞概率。