HashMap在get和put时经过哪些步骤？

面试记录 2026-10-09

题目：HashMap 在 get 和 put 时经过哪些步骤？

难度：medium

标签：java/collections, general/knowledge

评分：⭐⭐⭐☆☆（3/5）

我的回答

Put，Put 先把 Key 转化成 Hash Code，然后去进行确认存储位置，确认存储位置之后进行比对，看当前位置是否已经存储了元素。如果没有存储元素就放进去，如果有存储元素就对比进行链表叠加，或者是转化成红黑树。然后另外 Put 要判定队列的数量，然后一定比例考虑是否扩容等一系列事件。插入的时候选择，当下 JDK 后期版本使用的是尾插法，不是最开始的头插法。头插法虽然更快，但是会有风险安全问题。尾插法的话不会有出现断链以及循环等极端严重的风险。是有对 key value 的判定，key 不能为空，只能有一个空，在 HashMap 中。

在比对 key 的时候，使用，在 get 的时候将 key 也是转化成 hash code，然后先去找到对应位置，位置之后再依次作比，找到对应的是否是同一个，然后从链表中，如果是在对比链表中，当前桶下的链表中的对象，对比到是哪一个，通过 equals，如果有就去除，如果没有就返回 null。

点评

优点：

• put 主线正确：hash → 定位桶 → 空则放/非空则挂链表或转树 → 检查扩容
• 抓到关键区分点：JDK8 从「头插法」改为「尾插法」，并准确说出头插法在并发扩容时会导致环形链表
• get 主线也清晰：hash → 定位 → equals 比对 → 命中或 null
• 能提到 key 空值约束（虽然表述不准）

不足：

• hash 位运算没讲：JDK8 hash() 方法 (h = key.hashCode()) ^ (h >>> 16)——高 16 位异或低 16 位参与计算，减少碰撞；然后 index = (n - 1) & hash 定位桶。整段缺失
• 空键约束说错：应该是「允许 1 个 null key 存到 0 号桶 + 允许多个 null value」，"key 不能为空，只能有一个空" 语义混乱
• 转树条件不完整：应说清"链表长度 ≥ 8 且 数组长度 ≥ 64"才转树；且扩容后树形桶可能退化回链表
• 扩容流程没讲：resize() 时容量翻倍（16→32），元素按新 hash 重新分桶；JDK8 有个关键优化——只判断新 hash 的第 n 位决定元素留在原位还是搬到 index+n
• get 树形分支漏了：树化桶里 get 要走 getTreeNode（红黑树查找），也是 O(log n)
• put 覆盖 vs 新增没说清：桶里 key 已存在时（equals 相等）会覆盖 value，不是"叠到链表里"
• put 与 get 讲混了：最后一段 get 逻辑中"如果有就去除"——那是 remove 逻辑

补充：

• put 四步走：①hash(key) = (h ^ (h >>> 16)) 扰乱 hashCode；②(n - 1) & hash 定位桶下标；③桶为空则新建 Node 放入，桶非空则遍历链表，若 key equals 则覆盖 value 否则尾插新节点；④若链表长度 > 8 且表容量 ≥ 64 → 转红黑树；++size > threshold → 扩容
• JDK8 resize 的巧妙之处：原 index 的元素，新位置在 oldIndex 或 oldIndex + oldCap，用 e.hash & oldCap 判断（0 则原位，非 0 则远端），避免了重新 hash
• 头插法并发翻车：两个线程同时扩容时，A 遍历到 e→f，B 遍历到 f→e，A 完成后 e→f→f，形成死循环；get 命中该桶会 CPU 100%——这就是为什么 JDK8 改尾插法
• 树形退化：扩容后如果树桶 size < 6（TREEIFY_THRESHOLD-1），会退化回链表

完整讲解

第一部分：知识重点剖析

核心考点定位：验证对 HashMap 内部实现的完整掌握——hash 计算、桶定位、冲突处理、扩容机制、以及 JDK7/8 关键差异（头插法 → 尾插法、引入红黑树）。

知识点拆解：

1. 底层原理：HashMap 是「数组 + 链表 + 红黑树」的复合结构。数组是桶，桶内是链表（碰撞时挂接），链表过长转红黑树降低查找成本。JDK8 用尾插法替代头插法，避免并发扩容形成环形链表。
2. put 流程：①hash(key) = key.hashCode() ^ (key.hashCode() >>> 16) 高位参与运算；②(n - 1) & hash 定位桶（容量是 2 的幂，等价于模运算）；③桶为空直接放，桶非空遍历：key.equals() 相同则覆盖 value，不同则尾插；④若链长 > 8 且容量 ≥ 64 → 转红黑树；⑤++size > threshold 触发 resize()。
3. get 流程：①同样算 hash；②定位桶；③桶首个元素 hash+equals 命中返回；④若为红黑树走 getTreeNode 树形查找 O(log n)；⑤否则遍历链表逐一 equals 比对；⑥未命中返回 null。
4. 设计权衡：容量必须 2 的幂——(n-1) & hash 等价于取模，且扩容时判断旧 hash 的第 n 位就能决定新位置；负载因子 0.75 是"空间 vs 时间"的经典折中；链表阈值 8 来自泊松分布，自然碰撞下概率极低，超过就是哈希冲突。
5. 工程实践：预估容量时 new HashMap<>(expectedSize / 0.75f + 1) 避免扩容；自定义 key 类必须同时重写 hashCode 和 equals（违背会让 get 失效）；不要在多线程中用 HashMap 做共享状态。

按「底层原理 → 设计权衡 → 工程实践」递进排列。

第二部分：考察方向与延伸递进

考察方向：

• 深度：是否理解 (n-1) & hash 为什么能替代 %n（容量为 2 的幂时才等价）
• 广度：能否对比 ConcurrentHashMap 的 put 流程（多了 CAS + synchronized）
• 应用：能否根据 put 流程解释"为什么自定义 key 不重写 hashCode 会导致 Map 异常"

延伸递进面试题：

1. 为什么 HashMap 容量必须为 2 的幂？

• 解答要点：容量 2^n 时，n-1 是低位全是 1，(n-1) & hash 等价于 hash % n；扩容时 e.hash & oldCap 一个 bit 就能判断新桶是原位还是 +oldCap；且低位散列均匀。

1. hashCode 和 equals 契约是什么？打破会怎样？

• 解答要点：契约是"equals 相等则 hashCode 必相等"（反过来不成立）。破坏后 put 时 A/B 的 hash 不同，equals 无法触发覆盖，出现"两个 equals 相等的 key 各占一个桶"，get 时可能找不到刚 put 的值。

1. HashMap 为什么默认容量 16、负载因子 0.75？

• 解答要点：16 是内存开销和扩容频率的折中；0.75 是泊松分布下的经验值，冲突概率低但空间利用率合理。

1. JDK7 头插法为什么会导致 CPU 100%？

• 解答要点：并发扩容时两线程同时迁移链表，节点指针互相覆盖形成循环 e→f→e，get 命中该桶会死循环；JDK8 尾插法保留了插入顺序，不会形成环。

第三部分：面试者参考回答（300-600 字口语化）

面试官您好，我以 JDK8 为例说 put 和 get 的完整流程。

put 分四步：第一步算 hash，代码是 hash(key) = key.hashCode() ^ (key.hashCode() >>> 16)，把 hashCode 的高 16 位异或到低 16 位，让高位也参与计算，减少高位碰撞；第二步定位桶，index = (n - 1) & hash，因为容量 n 是 2 的幂，n-1 低位全 1，这一步等价于取模但更快；第三步桶处理，桶为空直接 new 一个 Node 放进去，桶非空就遍历：如果头节点 key 和当前 key 用 == 或 equals() 相等就覆盖 value，否则尾插一个新 Node 到链表末尾——这里请注意是尾插法，JDK7 用头插法在并发扩容时会形成环形链表导致 CPU 100%；第四步检查扩容条件，如果链长 > 8 且表容量 ≥ 64 就转红黑树，如果 size > threshold（默认容量 × 0.75）就调用 resize() 扩容到 2 倍。

扩容有个巧妙设计：对每个旧桶元素判断 e.hash & oldCap，如果结果为 0 就留在原 index，否则搬到 index + oldCap。因为容量翻倍后低位 bit 不变，新位置只会在这两个候选值之间。

get 流程类似：先算 hash 定位桶；桶头命中直接返回；如果桶是红黑树走 getTreeNode 走树形查找 O(log n)；如果是链表就逐一 equals 比对；都没命中返回 null。

几个易踩的坑：容量一定要选 2 的幂；自定义 key 类必须同时重写 hashCode 和 equals，违背契约会导致 get 找不到刚 put 的值；预估容量时用 new HashMap<>(expectedSize / 0.75f + 1) 避免扩容抖动；并发场景直接换 ConcurrentHashMap。