Java 概念小课（一）：HashMap 底层到底是怎么工作的

HashMap 大概是 Java 里用得最多的容器，但很多人对它的理解停留在「键值对」三个字。这篇用最短的篇幅把它的核心机制讲清楚。

一句话总结

HashMap = 数组 + 链表 + 红黑树。数组是主体，冲突的元素挂在链表上，链表太长了就升级成红黑树。

put 的完整流程

Map<String, Integer> map = new HashMap<>();
map.put("ant", 1);

这一步内部发生了什么：

1. 算哈希：(h = key.hashCode()) ^ (h >>> 16)，把高 16 位混进低 16 位，减少冲突；
2. 定位桶：用哈希值对数组长度取模（实现上是位运算 (n - 1) & hash，因为数组长度永远是 2 的幂）；
3. 桶为空：直接放入，结束；
4. 桶不空：key 相同（equals 为 true）就覆盖，不同就挂到链表尾部；
5. 树化：链表长度 ≥ 8 且 数组长度 ≥ 64 时，链表转红黑树，查询从 O(n) 变 O(log n)。

几个高频问题

为什么容量必须是 2 的幂？

为了让 (n - 1) & hash 等价于取模。n 是 2 的幂时，n - 1 的二进制全 1，位运算结果和取模一致，但快得多。

什么时候扩容？

负载因子默认 0.75。元素数超过 容量 × 0.75 时扩容为原来的 2 倍，并把所有元素重新分布（rehash）。扩容后元素要么留在原位置，要么移动到「原位置 + 旧容量」，只需看哈希的新增那一位是 0 还是 1。

为什么树化阈值是 8？

理想哈希分布下链表长度服从泊松分布，长度到 8 的概率约千万分之一。树化是防哈希碰撞攻击的兜底，不是常态。

HashMap 线程安全吗？

不安全。多线程场景用 ConcurrentHashMap（JDK 8 后是「数组 + 链表/红黑树 + CAS + synchronized 锁桶头」，锁粒度很小），而不是早已过时的 Hashtable。

小结

• 定位靠哈希，冲突靠链表，链表长了变红黑树；
• 0.75 负载因子触发 2 倍扩容；
• 多线程请直接用 ConcurrentHashMap。