本文围绕 Java 中 HashMap 的底层实现原理展开详细解析，是 Java 面试中的高频考点。内容涵盖 HashMap 的基本概念、底层数据结构（数组、链表、红黑树）及演变过程，深入讲解哈希函数、哈希冲突解决办法、扩容机制等核心原理，还介绍了常见问题与使用场景。通过条理清晰的阐述，帮助读者全面掌握 HashMap 的底层逻辑，为面试和实际开发奠定基础。​

一、HashMap 的基本概念​

在 Java 集合框架中，HashMap 是一种基于哈希表实现的键值对（Key-Value）存储结构，它继承自 AbstractMap 类，实现了 Map 接口。HashMap 的特点是查询、插入、删除操作效率高，在理想情况下，这些操作的时间复杂度可以达到 O (1)。​

与 HashTable 相比，HashMap允许键（Key）和值（Value）为 null，且不是线程安全的；而 HashTable 不允许键或值为 null，且是线程安全的，但效率相对较低。在单线程环境下，HashMap 是更常用的选择；在多线程环境中，若需保证线程安全，可使用 ConcurrentHashMap。​

HashMap 的核心作用是快速存储和检索数据，通过键（Key）来定位值（Value）的存储位置，这一过程依赖于底层的哈希机制。​

二、HashMap 的底层数据结构​

HashMap 的底层数据结构并非一成不变，而是随着 Java 版本的更新不断优化，其演进过程主要经历了 “数组 + 链表” 到 “数组 + 链表 + 红黑树” 的转变。​

1. 数组（哈希桶）​

数组是 HashMap 底层最基础的数据结构，也被称为哈希桶（Hash Bucket）。数组中的每个元素都是一个 Entry（JDK1.7 及之前）或 Node（JDK1.8 及之后）对象，该对象包含键（Key）、值（Value）、哈希值（hash）以及指向下一个元素的引用（next）。​

数组的长度在 HashMap 中被称为容量（Capacity），默认初始容量为 16（1<<4），且容量必须是 2 的幂次方。这一设计是为了在计算元素存储位置时，能通过位运算（与运算）提高效率，后续会详细说明。​

2. 链表（解决哈希冲突）​

当两个或多个不同的键通过哈希函数计算后，得到的存储位置（数组索引）相同时，就会发生哈希冲突（Hash Collision）。在 JDK1.7 及之前，HashMap 通过链表来解决哈希冲突，即当发生冲突时，将新的元素以链表节点的形式挂载到数组对应索引位置的链表尾部，这种方式被称为 “链地址法”。​

在链表中，每个节点都通过 next 引用指向后续节点，形成一个单向链表。此时，数组中的元素既是一个独立的节点，也可能是一个链表的头节点。​

3. 红黑树（优化链表性能）​

当链表的长度过长时（JDK1.8 中默认阈值为 8），链表的查询效率会下降，时间复杂度接近 O (n)。为了优化这一问题，JDK1.8 引入了红黑树（Red-Black Tree）数据结构。当链表长度达到阈值，且数组的容量大于等于 64 时，链表会自动转换为红黑树；反之，若数组容量小于 64，则会先进行扩容操作，而不是直接转为红黑树。​

红黑树是一种自平衡的二叉查找树，它的查询、插入、删除操作的时间复杂度均为 O (log n)，能显著提升长链表场景下的操作效率。当红黑树的节点数量减少到一定程度（默认阈值为 6）时，红黑树会重新转换为链表，以节省存储空间。​

三、HashMap 的核心原理​

1. 哈希函数（计算存储位置）​

哈希函数的作用是将键（Key）转换为数组的索引，以便确定元素的存储位置。HashMap 中哈希函数的计算过程分为两步：​

• 首先，通过键的 hashCode () 方法获取其哈希码（int 类型）。​

• 然后，对哈希码进行二次哈希（扰动处理），目的是减少哈希冲突的概率。在 JDK1.8 中，二次哈希的计算公式为：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)，即通过将哈希码的高 16 位与低 16 位进行异或运算，混合哈希码的高位和低位信息。​

• 最后，通过与运算计算数组索引：index = (n - 1) & hash，其中 n 为数组的容量。由于数组容量是 2 的幂次方，n-1 的二进制表示为全 1，与运算的结果就等价于 hash 对 n 取模，且位运算的效率远高于取模运算。​

经过这样的计算，最终得到的索引值就是元素在数组中的存储位置。​

2. 哈希冲突解决（链地址法）​

如前文所述，HashMap 采用链地址法解决哈希冲突，即当多个键映射到数组同一索引时，这些键值对会以链表或红黑树的形式存储在该索引位置。​

链地址法的优势在于实现简单，且对哈希函数的要求较低。但需要注意的是，若哈希函数设计不合理，可能会导致大量元素聚集在同一个链表或红黑树中，从而降低 HashMap 的性能。​

3. 扩容机制（resize）​

当 HashMap 中的元素数量（size）超过阈值（threshold）时，就会触发扩容操作。阈值的计算公式为：threshold = capacity * loadFactor，其中 loadFactor 为负载因子，默认值为 0.75。负载因子是衡量 HashMap 满程度的指标，0.75 的默认值是时间和空间成本的平衡点：负载因子过高，会增加哈希冲突的概率；负载因子过低，则会浪费存储空间。​

扩容的过程如下：​

• 计算新的容量，默认情况下新容量是原容量的 2 倍（同样保持为 2 的幂次方）。​

• 创建一个新的数组，容量为新容量。​

• 重新计算原数组中所有元素的哈希值和索引，并将它们转移到新的数组中，这一过程被称为 “重哈希（Rehash）”。​

• 更新阈值为新容量乘以负载因子，并将新数组赋值给原数组引用。​

在 JDK1.7 中，扩容时采用头插法转移链表节点，这可能会导致多线程环境下出现链表环的问题，引发死循环；而 JDK1.8 中改为尾插法，避免了这一问题，但 HashMap 仍然不是线程安全的。​

4. put () 方法执行流程​

put () 方法是 HashMap 中用于添加键值对的核心方法，其执行流程如下：​

• 检查键是否为 null，若为 null，则将其存储在数组索引 0 的位置（JDK1.8 中处理方式）。​

• 计算键的哈希值和数组索引。​

• 检查数组对应索引位置是否为空：​

• 若为空，直接创建新节点并存储。​

• 若不为空，判断该位置的节点类型（链表节点或红黑树节点）：​

• 若为链表节点，遍历链表，若存在相同的键（通过 equals () 方法判断），则更新对应的值；若不存在，则在链表尾部添加新节点，添加后检查链表长度是否达到阈值，若达到则转换为红黑树。​

• 若为红黑树节点，按照红黑树的插入规则插入新节点。​

• 添加元素后，检查元素数量是否超过阈值，若超过则执行扩容操作。​

5. get () 方法执行流程​

get () 方法用于根据键获取对应的值，执行流程如下：​

• 计算键的哈希值和数组索引。​

• 检查数组对应索引位置的节点：​

• 若节点为空，返回 null。​

• 若节点不为空，判断头节点的键是否与目标键相同（哈希值相同且 equals () 方法返回 true），若相同则返回对应的值。​

• 若头节点不同，根据节点类型（链表或红黑树）遍历后续节点：​

• 链表节点：遍历链表，逐一比较键，找到匹配的节点后返回值；若遍历结束未找到，返回 null。​

• 红黑树节点：按照红黑树的查找规则查找节点，找到后返回值；若未找到，返回 null。​

四、HashMap 的常见问题​

1. 为什么 HashMap 的容量必须是 2 的幂次方？​

如前文所述，HashMap 的容量设计为 2 的幂次方，主要是为了在计算数组索引时，能通过(n - 1) & hash的位运算替代取模运算，提高计算效率。因为当 n 是 2 的幂次方时，n-1 的二进制表示为全 1，此时与运算的结果和取模运算的结果相同，但位运算的执行速度更快。​

2. 为什么要进行二次哈希（扰动处理）？​

二次哈希的目的是为了让哈希码的高位也参与到索引计算中，减少哈希冲突的概率。如果直接使用键的 hashCode () 作为哈希值，可能会导致高位的差异被忽略（因为数组容量通常较小），通过将哈希码的高 16 位与低 16 位进行异或运算，可以混合高位和低位的信息，使计算出的索引分布更均匀。​

3. HashMap 为什么不是线程安全的？​

HashMap 不是线程安全的，主要原因如下：​

• 多线程环境下，同时进行 put () 操作可能会导致元素丢失。​

• 扩容过程中，若多个线程同时操作，可能会导致链表环的问题（JDK1.7 中）。​

• 读线程可能会读取到未完全初始化的元素。​

在需要线程安全的场景中，应使用 ConcurrentHashMap，而不是通过 Collections.synchronizedMap () 方法包装的 HashMap（后者效率较低）。​

4. JDK1.7 和 JDK1.8 中 HashMap 的区别​

JDK1.7 和 JDK1.8 中 HashMap 的主要区别如下：​

• 底层数据结构：JDK1.7 为 “数组 + 链表”；JDK1.8 为 “数组 + 链表 + 红黑树”。​

• 链表插入方式：JDK1.7 采用头插法；JDK1.8 采用尾插法。​

• 哈希函数：JDK1.7 中进行了多次扰动处理；JDK1.8 中简化了扰动处理，只进行一次异或运算。​

• 扩容时的重哈希：JDK1.7 中需要重新计算所有元素的哈希值；JDK1.8 中通过高位运算确定新索引，优化了重哈希过程。​

• 对 null 键的处理：两者都允许 null 键，但存储位置的计算方式略有差异。​

五、HashMap 的使用场景​

HashMap 适用于以下场景：​

• 需要快速存储和检索键值对数据的场景，如缓存系统。​

• 不需要保证元素顺序的场景（HashMap 是无序的，若需要有序，可使用 LinkedHashMap）。​

• 单线程环境下，或能保证线程安全的场景（如通过外部同步机制）。​

不适用于以下场景：​

• 多线程环境下且需要保证线程安全的场景（应使用 ConcurrentHashMap）。​

• 需要按照插入顺序或访问顺序遍历元素的场景（应使用 LinkedHashMap）。​

• 需要键或值不能为 null 的场景（应使用 HashTable）。​

六、总结​

HashMap 是 Java 中最常用的集合类之一，其底层实现原理是 Java 面试的重点内容。本文详细介绍了 HashMap 的底层数据结构（数组、链表、红黑树）、核心原理（哈希函数、哈希冲突解决、扩容机制、put () 和 get () 方法流程）、常见问题及使用场景。​

通过学习可以知道，HashMap 的设计充分考虑了效率和性能，通过 2 的幂次方容量、二次哈希、红黑树优化等机制，在大多数场景下都能提供高效的操作。但同时也要注意其线程不安全的特性，在合适的场景中正确使用。掌握 HashMap 的底层实现原理，不仅能应对面试，还能在实际开发中更好地理解和使用这一数据结构，避免出现不必要的问题。