HashMap 的底层实现原理？
发布于
一、数据结构
JDK 1.8 后 HashMap = 数组 + 链表 + 红黑树。
- 数组是主体，通过
(n-1) & hash定位桶。 - 哈希冲突时，同桶元素挂成链表。
- 链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转红黑树；节点数 ≤ 6 时转回链表。
二、put 流程
- 计算 key 的 hash（
h ^ (h >>> 16)扰动）。 - 定位桶：
(table.length - 1) & hash。 - 桶为空 → 直接放入；不为空 → 遍历链表/树，key 相同则覆盖，否则尾插。
- 元素数超过阈值（容量 × 负载因子 0.75）→ 扩容为 2 倍，rehash。
三、线程安全
HashMap 非线程安全。并发下可能数据丢失或死循环（JDK 1.7 头插法）。需要线程安全用 ConcurrentHashMap。