真实面经题目 · 原创解析
HashMap 的核心是“数组定位桶，桶内解决冲突”。JDK 8 及以后主流实现是 Node 数组加链表加红黑树：先用 hash 扰动把 key 的 hashCode 高位混入低位，再用数组长度减一与 hash 做位与定位桶；put 在桶为空时直接插入，桶非空时按 hash 和 equals 查找同 key，存在则覆盖值，不存在则挂到链表或树中；get 走同样的定位和匹配过程。扩容由容量、负载因子和阈值控制，默认负载因子 0.75，超过阈值后容量通常翻倍。单桶冲突达到树化阈值且数组容量足够时会转红黑树，节点减少到退化阈值附近会退回链表。HashMap 不保证顺序，也不是线程安全容器。
可以按 JDK 8 及以后版本来讲。HashMap 底层本质是哈希表，主体是一个 Node 数组，每个数组位置叫一个桶。不同 key 经过 hash 后可能落到同一个桶，JDK 8 以前主要用链表解决冲突；JDK 8 以后，当同一个桶里的节点过多时，会把链表转成红黑树，所以结构可以概括为数组加链表加红黑树。put 的过程是：先计算 key 的 hash。对于非 null key，会取 key.hashCode()，再做一次扰动，也就是把高 16 位混入低 16 位，减少只依赖低位取模时的碰撞；null key 的 hash 视为 0。数组长度始终按 2 的幂维护，所以桶下标可以用 (n - 1) & hash 快速计算。定位到桶后，如果桶为空，直接新建节点放进去；如果桶不为空，先比较第一个节点，再沿链表或红黑树查找 hash 相同且 key 相等的节点。相等判断不是只看 hash，而是先看 hash，再看 key 是否同一个引用，或者 equals 是否返回 true。如果找到已有 key，就覆盖 value 并返回旧值；如果没找到，就插入新节点。插入新节点后 size 增加，超过 threshold 时触发 resize。get 的过程和 put 的前半段一致：计算 hash，定位桶，然后在桶内查找。桶为空直接返回 null；桶非空先检查首节点，再根据桶结构遍历链表或搜索红黑树，找到 hash 和 key 都匹配的节点就返回 value，否则返回 null。因为 HashMap 允许 value 为 null，所以 get 返回 null 不一定代表 key 不存在，需要用 containsKey 区分。resize 的触发条件和负载因子有关。默认初始容量通常是 16，默认负载因子是 0.75，阈值 threshold 等于 capacity 乘 loadFactor，所以默认插入第 13 个元素时会触发扩容。扩容时数组容量通常翻倍。JDK 8 的迁移不需要重新完整计算 hash，而是利用 oldCap 对应的那一位，把原桶里的节点拆成两个方向：hash & oldCap 为 0 的留在原下标，为 1 的移动到原下标加 oldCap 的位置。树化也有边界条件。单个桶中的节点数达到 8 时，并不一定立刻转红黑树；如果当前数组容量小于 64，会优先扩容，因为小数组下冲突可能只是容量不足造成的。只有桶节点数达到 8 且数组容量至少为 64，才会树化。退化阈值通常按 6 理解，节点减少后会从红黑树退回链表，这样用 8 和 6 两个阈值避免频繁来回转换。还要补充 equals 和 hashCode 的契约：两个 equals 相等的对象必须有相同 hashCode，作为 key 的字段最好不要在放入 HashMap 后再变化，否则可能出现 put 进去却 get 不到的问题。HashMap 本身不是线程安全的，并发 put 或 put 与 resize 交织时可能出现数据丢失、结构不一致、可见性问题。JDK 7 中并发扩容还可能出现链表环导致死循环的历史问题；JDK 8 改了迁移方式并引入树化，但仍然不是线程安全容器。并发场景应该使用 ConcurrentHashMap 或外部同步。
HashMap 是基于哈希表的键值存储结构。数组负责快速定位桶，链表负责处理哈希冲突，JDK 8 以后在冲突严重时引入红黑树降低单桶查找成本。平均情况下 put 和 get 接近 O(1)，但这个前提是 hash 分布较均匀。
put 先计算扰动后的 hash，再用 (n - 1) & hash 定位数组桶。桶为空时直接插入；桶非空时比较 hash、引用相等和 equals，相同 key 覆盖 value，不同 key 追加到链表或插入红黑树。get 也是先定位桶，再检查首节点、遍历链表或搜索红黑树，找到匹配 key 返回 value，否则返回 null。
HashMap 通过 capacity、loadFactor、threshold 控制扩容。默认负载因子 0.75 是时间和空间的折中；元素个数超过 threshold 后触发 resize，容量通常翻倍。JDK 8 扩容时利用 hash & oldCap 判断节点留在原桶还是移动到原桶加 oldCap 的位置，减少重新计算成本。
树化不是只看链表长度。桶内节点达到 8 且数组容量至少为 64 时，链表才会转红黑树；如果容量小于 64，会优先扩容。节点数量减少到退化阈值附近，通常按 6 理解，会退回链表。8 和 6 形成滞后区间，避免频繁树化和退化。
HashMap 允许 null key 和 null value，null key 的 hash 为 0，通常落在 0 号桶。get 返回 null 可能是 key 不存在，也可能是 value 本身为 null。HashMap 不保证遍历顺序，也不是线程安全的；多线程写入应使用 ConcurrentHashMap 或外部同步。
JDK 7 及以前主要是数组加链表，链表头插，扩容并发场景存在形成环的历史风险。JDK 8 以后改为数组加链表加红黑树，链表插入和扩容迁移策略也发生变化，但这些优化不改变 HashMap 非线程安全的事实。
因为下标可以用 (n - 1) & hash 代替取模，计算更快；同时当 n 是 2 的幂时，n - 1 的二进制低位全是 1，能更均匀地利用 hash 的低位。
数组下标主要依赖 hash 的低位。如果很多 key 的 hashCode 高位变化明显但低位相似，直接取低位容易冲突。扰动把高位信息混入低位，可以降低碰撞概率。
小容量下单桶过长往往是数组太小导致的，扩容比树化更划算。所以 JDK 8 需要桶节点达到 8 且数组容量至少 64；否则优先 resize。
不会。相同 key 指 hash 相同且 key 引用相同或 equals 返回 true。此时只覆盖 value，并返回旧 value，结构大小不增加。
不一定。HashMap 允许 value 为 null，所以 get 返回 null 可能表示 key 不存在，也可能表示 key 存在但 value 是 null。需要用 containsKey 判断 key 是否存在。
单线程或外部已经同步的场景可以用 HashMap。多线程并发读写同一个 map 时，应使用 ConcurrentHashMap 或明确的同步机制。
