考察点
这是 Java 基础里出场率最高的一道题，大数据岗位尤其爱问，因为 Hadoop、Spark 源码里到处是 HashMap 的身影。面试官真正想看的不是你能背出「数组加链表」，而是你是否理解哈希冲突的处理思路、扩容为什么代价高、JDK 8 引入红黑树解决了什么实际问题。追问通常会往 ConcurrentHashMap、哈希函数设计、容量为什么必须是 2 的幂这几个方向走。
参考答案
底层结构
JDK 8 的 HashMap 是一个 Node 数组（哈希桶），每个桶里挂链表；当单个桶的链表长度达到阈值且数组容量足够大时，链表转成红黑树。put 的流程是：先对 key 的 hashCode 做一次扰动（h = key.hashCode(); h ^ (h >>> 16)，把高 16 位混进低 16 位），再用 (n - 1) & hash 定位桶下标。桶为空直接放节点；不为空就遍历链表，key 相等则覆盖 value，否则插到链表尾部（JDK 8 是尾插，JDK 7 是头插），插入后检查是否需要树化；最后 size 加一，超过阈值就扩容。
为什么容量必须是 2 的幂
定位桶用的是 (n - 1) & hash 而不是取模。当 n 是 2 的幂时，n - 1 的二进制全是 1，按位与等价于取模但快得多，而且分布均匀。扩容时这个设计还有个红利：旧桶里的元素要么留在原位，要么移到「原位 + 旧容量」的位置，只需要看 hash 在旧容量那一位是 0 还是 1，不用重新计算所有哈希。这就是为什么 HashMap 的容量永远是 16、32、64 这样翻倍的。
树化的两个条件
很多候选人只记得「链表长度超过 8 转红黑树」，这是不完整的。树化需要同时满足：链表长度达到 TREEIFY_THRESHOLD（8），并且数组容量达到 MIN_TREEIFY_CAPACITY（64）。如果链表长度到了 8 但数组容量小于 64，HashMap 选择先扩容而不是树化——因为小数组下链表长，说明哈希分布太拥挤，扩容把元素摊开比树化更划算。反过来，红黑树节点数降到 UNTREEIFY_THRESHOLD（6）时会退化回链表。8 和 6 之间留了缓冲，避免在边界附近频繁转换。官方注释里写过，在理想哈希下链表长度服从泊松分布，长度到 8 的概率不到千万分之一，红黑树是防恶意构造哈希冲突的兜底手段，不是常态。
扩容的代价和坑
负载因子默认 0.75，是时间和空间的折中：太高冲突多，太低浪费内存。扩容时数组翻倍，所有节点重新分布，是个 O(n) 操作。工程上如果能预估数据量，比如要放 100 万元素，应该直接 new HashMap<>(1 << 20) 附近初始化，避免中途十几次扩容。大数据作业里在 map-side 聚合时，HashMap 初始化大小不合理导致频繁 rehash，是实打实的性能杀手。另外要提一句：HashMap 线程不安全，多线程并发 put 在 JDK 7 下扩容可能形成环形链表导致 CPU 打满，JDK 8 改成尾插后不会有环，但数据覆盖、size 不准的问题依然存在，并发场景必须上 ConcurrentHashMap。
可能的追问
- 哈希扰动为什么要高 16 位异或低 16 位？ 因为数组容量通常不大，定位时只用了 hash 的低位，扰动把高位信息混进来，减少低位相同导致的冲突。
- 为什么用红黑树不用 AVL 树？ 红黑树插入删除的旋转次数更少，牺牲一点查询平衡性换写入效率，HashMap 场景写操作频繁，红黑树更合适。
- HashMap 和 Hashtable、ConcurrentHashMap 怎么选？ Hashtable 全表 synchronized 已淘汰；单线程用 HashMap，并发用 ConcurrentHashMap，它只锁桶级别，吞吐量高一个量级。
- key 为 null 怎么处理？ HashMap 允许一个 null key，固定放在 0 号桶（hash 为 0）；ConcurrentHashMap 不允许 null key 和 null value，因为并发下无法区分「不存在」和「值为 null」。