HashMap 底层实现原理详解

一、数据结构

HashMap 基于 数组 + 链表 + 红黑树 的数据结构实现：

  • 数组：存储 Node 对象的数组，初始容量为 16
  • 链表：当哈希冲突时，使用链表存储多个 Node
  • 红黑树：链表长度 > 8 时，链表转换为红黑树（JDK 1.8+）

二、关键参数

参数 说明
capacity 容量，默认16，必须是2的幂次方
loadFactor 负载因子，默认0.75
threshold 扩容阈值 = capacity × loadFactor
size 当前存储的键值对个数

三、哈希冲突解决

链地址法：

  1. 计算 hash 值：hash = key.hashCode() ^ (key.hashCode() >>> 16)
  2. 计算桶位置：index = (n - 1) & hash（n为容量）
  3. 相同 index 的元素形成链表

四、常见问题

Q：为什么容量必须是2的幂次方？

  • 使用 & 运算效率高于 % 运算
  • 保证 (n - 1) & hash 的结果均匀分布

Q：为什么负载因子是0.75？

  • 0.75 是时间和空间成本的最优平衡
  • 过小：浪费空间；过大：冲突增加，查询变慢

Q：什么时候链表转红黑树？

  • 链表长度 > 8 且数组容量 >= 64 时转为红黑树
  • 红黑树长度 < 6 时退化为链表

五、重要方法

  • put()：添加或更新元素，触发扩容
  • get()：查询元素，O(1) 平均复杂度
  • resize()：容量扩容至原来的2倍