HashMap 在 get 和 put 时，底层流程是怎样的？

面试考察点

面试官提出这个问题，主要想考察你对 Java 核心数据结构 HashMap 底层实现机制的掌握深度，而不仅仅是停留在 API 调用层面。具体考察点包括：

1. 对 HashMap 底层数据结构的理解：面试官想知道你是否清楚 JDK 8 之后 HashMap 采用的 “数组+链表/红黑树” 结构。
2. 对哈希函数与冲突解决机制的掌握：你能否清晰说明 key 如何通过哈希函数映射到数组索引，以及当多个 key 哈希冲突时，HashMap 如何处理（链表拉链、树化）。
3. 对核心流程（put/get）细节的洞察：面试官不仅仅是想知道步骤，更是想知道你是否了解其中的关键细节，例如：
   • hash() 方法如何计算（为什么要做异或运算？）。
   • 如何定位桶（(n-1) & hash 的原理）。
   • 什么情况下会触发扩容，扩容时发生了什么（rehash）。
   • 链表何时会转化为红黑树，何时会退化成链表。
4. 对线程安全性和性能影响因素的认知：你是否了解 HashMap 在并发环境下的问题，以及初始容量、负载因子等参数对性能的影响。
5. 将原理应用于实践的能力：能否根据原理，给出在真实开发中正确、高效使用 HashMap 的最佳实践。

核心答案

HashMap 的 get 和 put 操作都围绕其 “数组+链表/红黑树” 的核心数据结构展开。简单来说：

• put(K key, V value) 步骤：计算 key 的哈希值 -> 通过哈希值定位到数组中的桶（bucket）-> 遍历桶内的链表或红黑树 -> 若 key 已存在则更新值，否则插入新节点 -> 检查是否需要树化或扩容。
• get(Object key) 步骤：计算 key 的哈希值 -> 定位到对应桶 -> 遍历桶内的链表或红黑树，通过 equals 方法匹配 key -> 返回找到的值，若未找到则返回 null。

深度解析

接下来，我们结合 JDK 8+ 的源码逻辑进行深入解析。

原理与机制：put 操作详解

put 操作是 HashMap 最复杂的过程，其核心流程如下（简化版源码逻辑）：

1. 计算哈希值 (hash(Object key))： 首先调用 key.hashCode() 获得原始哈希码 h，然后执行 (h ^ (h >>> 16))。这一步扰动函数的目的是将哈希码的高 16 位与低 16 位进行异或，使得低位也蕴含了高位的信息，从而减少后续哈希冲突的概率。

   static final int hash(Object key) {
       int h;
       // 并非简单地 return key == null ? 0 : key.hashCode();
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   

2. 定位桶索引 (index = (n - 1) & hash)： 数组长度 n 总是 2 的幂（如 16， 32）。(n-1) 的二进制形式是低位全 1（例如 15 是 01111）。这个按位与操作实质上是取哈希值的低位有效位作为索引，效率远高于取模运算 hash % n，并且保证了结果在 [0, n-1] 范围内。

3. 处理桶内元素： 定位到数组的 tab[i] 后，判断该位置第一个节点（first）的状态：

   • 情况一：桶为空 (first == null) 直接新建一个 Node 节点放入该位置。
   • 情况二：桶不为空，且第一个节点 key 匹配 (hash 相等且 equals 为 true) 找到目标节点，记录用于后续值更新。
   • 情况三：桶为红黑树 (first instanceof TreeNode) 调用红黑树的 putTreeVal 方法进行插入或查找。
   • 情况四：桶为链表 遍历链表。若找到 key 匹配的节点则记录；若未找到，则在链表尾部插入新节点，并检查链表长度是否达到树化阈值（默认 TREEIFY_THRESHOLD = 8）。若达到且当前数组容量达到最小树化容量（默认 MIN_TREEIFY_CAPACITY = 64），则将该链表转化为红黑树，以提高极端情况下的查询效率。

4. 更新或插入： 如果步骤 3 中找到了已存在的 key，则用新值替换旧值，并返回旧值。 如果是新插入的节点，则执行后续操作。

5. 扩容检查： 增加 size（元素总数），并判断 if (++size > threshold)。threshold 是扩容阈值，等于 capacity * loadFactor（容量 * 负载因子，默认 0.75）。 如果超过阈值，则调用 resize() 方法进行扩容，新建一个两倍大的数组，并重新计算所有元素在新数组中的位置（rehash）。JDK 8 的 rehash 过程优化了：由于新数组长度 newCap 也是 2 的幂，元素的新位置要么是原索引 oldIndex，要么是 oldIndex + oldCap，取决于原哈希值新增的那个比特位是 0 还是 1。

get 操作详解

get 操作是 put 操作查找部分的一个子集，流程相对简单：

1. 计算哈希值：与 put 第一步完全相同。
2. 定位桶索引：与 put 第二步完全相同，即 (n-1) & hash。
3. 查找节点：
   • 如果桶为空，返回 null。
   • 如果桶的第一个节点就是要找的节点（哈希相等且 key 相等），直接返回。
   • 如果第一个节点是 TreeNode，则调用红黑树的 getTreeNode 方法查找。
   • 否则，遍历链表，通过 equals 方法比较 key，找到则返回对应节点。

对比分析与最佳实践

• JDK 7 vs JDK 8+：JDK 7 采用 “头插法” 插入链表，在多线程扩容时可能造成死循环。JDK 8 改为 “尾插法”，并引入了红黑树，极大地优化了哈希冲突严重时的查询性能（从 O(n) 优化到 O(log n)）。
• 最佳实践：
  1. 为自定义 Key 类正确重写 hashCode() 和 equals()：这是 HashMap 正常工作的基石。hashCode 应保证分布均匀，equals 应保证逻辑正确。
  2. 预估容量，避免频繁扩容：如果预先知道要存储的元素数量 N，创建时应指定初始容量为 (N / loadFactor) + 1，例如预计存 1000 个元素，应 new HashMap<>(1337)。这样可以避免插入过程中多次触发耗时的 resize 操作。
  3. 理解非线程安全：HashMap 不是线程安全的。并发 put 可能导致数据覆盖、遍历时 ConcurrentModificationException 或（在 JDK 7 中）死循环。高并发场景请使用 ConcurrentHashMap。
• 常见误区：
  • 认为 HashMap 允许 null 键和 null 值，而 Hashtable 不允许。
  • 混淆 hashCode 和 equals 的作用：hashCode 用于快速定位桶，equals 用于在桶内精确匹配。两个对象 equals 相等，则 hashCode 必须相等；反之则不必然。

总结

HashMap 的 get 和 put 操作，本质是基于哈希值的快速定位与桶内数据结构的精确查找/插入相结合的过程，其高效性依赖于良好的哈希函数、适时的扩容以及（在 JDK 8+ 中）链表向红黑树的动态转化。