HashMap

6 November 2025   4839 words   ~10 mins
#OOP #HashMap

date_creation: 2025-10-13 17:26

date_modify: 2025-11-16 15:34

HashMap

HashMap 是 Java 中常用的键值对几何结构，通过生成唯一的 Key 查找和存放删除 Value, 通常查找时间复杂度是 O(1).

其中通过 Key 来生成 Hash 值选择位置存放, 因此 HashMap 的 Key 必须是唯一的, 但是 Value 可以重复.

HashMap 底层是如何是实现的?

HashMap 在底层是通过数组+链表+红黑树的形式实现的.

在 JDK 1.7 之前 只由 数组+链表实现.

哈希

JDK 1.7 & 1.8 是如何计算哈希的?

使用 扰动函数 (spreading function) 的目的是为了防止键的 hashCode() 方法实现较差，导致大量哈希冲突，从而提高键值对在数组中的分散性.

特性 JDK 1.7 hash(int h) JDK 1.8 hash(Object key)
函数体 多次位移和异或操作，扰动 4 次。 键的哈希值与自身无符号右移 16 位的值进行异或。
代码 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); (h = key.hashCode()) ^ (h >>> 16);
性能/复杂度 性能稍差一点点，因为扰动了 4 次。 更加简化，但原理不变，通过高位低位异或分散性更好。

高位低位哈希（扰动）的作用：

由于 HashMap 的数组长度 N 总是 2 的幂次方，计算索引时使用的是 位运算：index = (N - 1) & hash。

当 N 较小（例如 16）时，N −1 的二进制只有低 4 位是 1，这意味着只有哈希值的 低位 参与了索引计算。如果键的哈希值只有高位不同，低位相同，它们会映射到同一个桶，造成冲突。

JDK 1.8 的扰动函数 (h = key.hashCode()) ^ (h >>> 16) 解决了这个问题：

• 它将哈希值的高 16 位（即 h »> 16）与原哈希值 h 进行 异或 (^) 运算。

• 这样，哈希值的高位信息也能够影响最终的低位，从而增加了哈希值在低位上的随机性，减少了哈希冲突的概率

为什么容量选择 2 的幂？非 2 的幂会怎样？

HashMap 总是使用 2 的幂 作为哈希表的大小（容量）。

为什么容量总是 2 的幂？

选择 2 的幂的主要原因是为了高效地计算元素在数组中的位置（索引）。

  1. 位运算替代取模： 如果容量 N 是 2 的幂（例如 16 = 24），那么计算索引 index = hash % N 就可以通过效率更高的 位运算 来实现：index = (N - 1) & hash。
  2. 效率高： 位运算比传统的取模运算 (%) 速度快得多。
  3. 掩码有效性： 当 N 是 2 的幂时，N −1 的二进制表示是全 1，作为掩码能够最大限度地利用哈希值的所有低位，减少碰撞。

如果容量不是 2 的幂会怎样？

如果传入的 initialCapacity 不是 2 的幂，它会被立即通过 tableSizeFor 调整为最接近且大于或等于它的 2 的幂

如果容量 N 不是 2 的幂（例如 N = 10），那么 N −1 = 9 (二进制为 1001)。

• 此时，使用 (N - 1) & hash 进行索引计算时，某些哈希位永远不会被使用（例如第 2 位和第 4 位），这会导致哈希值不能均匀地分布在所有桶中，从而 加剧哈希冲突 并降低性能。

树

为什么要 在 1.7 之后加入红黑树?

因为大量元素插入 HashMap 之后可能会出现 Hash 冲突, 而 Java 中解决 Hash 冲突的方式是 链式地址法.

链式地址哈希表

当发生冲突后(即 Hash 值相同时), 会在这个数组位置后加入一个节点, 形成链表.

当形成 长链表之后再去查找某个元素此时时间复杂度就会退化为 O(n), 因此需要新的数据结构引入来缓解这种情况.

为什么要引入树而不是其他?

为什么要引入红黑树, 而不是 B+树或者 AVL 树?

在多种自平衡二叉树中，HashMap 最终选择了 红黑树 (Red-Black Tree)，而非严格平衡的 AVL 树 (AVL Tree) 或常用于磁盘存储的 B+ 树 (B+ Tree)，主要是基于内存操作场景下的 插入/删除成本与查询性能之间的权衡。

  1. 为什么不是 AVL 树?
特性 红黑树 AVL 树
平衡标准 相对宽松。最长路径不超过最短路径的 2 倍。 非常严格。任何节点的左右子树高度差不超过 1。
查找性能 略慢于 AVL 树。因为树可能更高。 理论上更快。因为树更矮，查找路径更短。
插入/删除性能 更快。因为平衡标准宽松，插入/删除后需要进行的旋转操作次数更少。 更慢。因为平衡标准严格，插入/删除后可能需要更多的旋转来维持平衡。

• AVL 树追求“完全平衡”： AVL 树要求任何节点的左右子树高度差不能超过 1。这种严格的平衡状态保证了 极佳的查找性能（最坏情况下也是 O(log n)）。然而，维护这种严格平衡状态的成本很高，每次插入或删除几乎都会破坏平衡规则，需要频繁地通过左旋和右旋进行调整。

• 红黑树追求“弱平衡”： 红黑树牺牲了对“完全平衡”的追求，转而追求“弱平衡”状态，即 整棵树最长路径不会超过最短路径的 2 倍。虽然这略微牺牲了一部分查找性能效率，但它换取了 维持树平衡状态的成本的降低。

• 权衡考量： 在 HashMap 这种动态数据结构中，元素的 插入和删除操作相对频繁。红黑树在插入、删除等操作时，不像 AVL 树那样频繁地破坏规则，因此 不需要频繁地进行调整。这种在维护成本上的优势，使得红黑树在 HashMap 这种读写操作都频繁的场景下成为更优的选择。

2.为什么不是 B+树?

B+ 树（或更广泛的 B 树）通常设计用于 外部存储（如数据库索引）。

特性 红黑树 B+ 树
设计目标 内存中 的数据结构。 磁盘等外部存储 的数据结构。
节点结构 二叉结构，每个节点最多 2 个子节点。 多路平衡查找树，每个节点可以有大量子节点（高扇出）。
数据存储 键和值存储在所有节点上。 所有数据（或指针）都存储在叶子节点，内部节点只存索引。
树的高度 相对较高。 非常矮胖（高度极低）。

• B+ 树的主要设计目标是减少磁盘 I/O 次数。它通过将节点设计为与磁盘页大小匹配的大块，并确保数据只存储在叶子节点，从而优化了数据检索效率。

• HashMap 操作在内存中： HashMap 运行在 Java 虚拟机内存中，不存在磁盘 I/O 瓶颈。在这种场景下，使用 B+ 树这种复杂的、为磁盘操作优化的数据结构是不必要的，并且会带来更大的空间开销（红黑树的节点大小已经是常规节点大小的两倍左右了）。

• 应用场景不匹配：B+树最大的优势是 范围查询 和 顺序遍历（因为叶子节点是链表连接的）。而 HashMap 的核心是 通过 key 进行精确的哈希查找，完全不需要范围查询的功能。

HashMap 的转化

树化

HashMap 什么条件下会从链表变成树?

HashMap 在发生较多哈希冲突且单个桶（数组位置）内元素较多时，会将链表转换为红黑树，以提升查询效率。具体条件为：

  • 单个桶内节点数 ≥ 8（TREEIFY_THRESHOLD = 8）
  • 总元素个数 ≥ 64（MIN_TREEIFY_CAPACITY = 64）

满足以上两个条件时，HashMap 才会执行树化操作。

为什么选择 8 和 64 这两个数字?

这是一个典型的权衡（trade-off）设计：树节点（TreeNode）的大小约为普通链表节点的两倍，且维护红黑树的平衡需要额外资源。因此，不能在冲突较少时就贸然树化，以免浪费内存和性能。阈值的选择基于理想的随机哈希码分布（遵循泊松分布，参数约为 0.5）下的统计概率。

 * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /非线程安全
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

为什么是 8 ?

  • 单个桶内节点数达到 8 的概率仅为 百万分之一（约 0.00000006），这表明已发生严重冲突。
  • 在良好分布的哈希码下，树化极少触发，避免了不必要的资源开销。

为什么是 64？

阈值 8 可能并非纯因冲突严重，还可能源于数组容量过小导致的偶发碰撞。为避免频繁树化（树化后退化回链表的开销较高），HashMap 优先通过扩容解决问题：

  • 当总容量 < 64 时，即使单个桶节点 ≥ 8，也会先扩容（而非树化）。
  • 只有容量 ≥ 64 且桶内节点 ≥ 8 时，才真正树化。

此设计确保树化仅在 “容量充足但局部冲突极端” 时发生，平衡了性能与资源消耗。

链表化

什么时候会退回为链表?

当桶中节点数 ≤ 6 时就会退化为链表.

/**  
 * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */
   static final int UNTREEIFY_THRESHOLD = 6;

为什么选择单个桶内节点数为 6 时退化?

选择节点数为 6 时链表化主要是为了防止频繁地抖动, 如果设置为 7 , 此时桶内有 8 个节点, 删除一个元素, 退化成链表, 再插入一个元素又会树化, 为了避免在不同数据结构之间频繁地转化, 设置为 6.

执行过程

链表扩容

1.7 vs 1.8 扩容时哈希过程

方面 JDK 1.7 JDK 1.8
重新哈希方式 所有节点需完整重算 hash % Nnew 仅检查 (hash & oldCap)，复用原 hash
计算开销 高（O(n) 全扫描 + 模运算） 低（O(1) 位运算 per 节点）
风险 头插法易死循环 尾插法 + 分裂规则，更安全

当 HashMap 容量达到阈值时，会进行扩容（resize），容量扩大为原来的 2 倍。

在 JDK 1.8 中，扩容时的重新分配节点位置被设计得 非常巧妙和高效。

由于新容量 Nnew 是旧容量 Nold 的两倍，这意味着 Nnew 的二进制表示比 Nold 多了一个高位 bit（这个 bit 的值就是 Nold）。

JDK 1.8 利用这个特性来确定节点的新位置：

  1. 判断新增位： 算法只需要判断原始哈希值 hash 在新增的那个 bit 位置上是 0 还是 1。

◦ 通过计算 (e.hash & oldCap) 来判断这个新增的位。

  1. 位置规则：

◦ 如果 (e.hash & oldCap) == 0，则新索引位置 不变（index = 原索引）。这些节点被归类到 loHead 链表/子树中。

◦ 如果 (e.hash & oldCap) != 0，则新索引位置为 原索引 + 旧容量（index = 原索引 + oldCap）。这些节点被归类到 hiHead 链表/子树中。

优势：

• 减少计算： 避免了重新对所有键计算完整的哈希值和索引。

• 均匀分散： 由于新增的 bit 是随机的，它能均匀地将原来冲突的节点分散到新的两个桶中（原索引和原索引 + 旧容量），从而有效地减少了哈希冲突

为什么 1.8 改为了尾插法?

特性 JDK 1.7 (HashMap) JDK 1.8 (HashMap)
插入方法 头插法 (Add to Head)。新元素插入到链表头部，作为新的头节点。 尾插法 (Add to Tail)。新元素插入到链表的尾部。
目的 插入快，但扩容时 顺序反转。 维持链表元素的相对顺序，防止线程安全问题。
多线程问题 不安全。在多线程环境下，扩容时可能导致链表形成 环形链表（死循环），从而使 get 操作陷入无限循环。 安全。解决了环形链表的问题，但在多线程下仍可能存在数据覆盖（非线程安全）。

总结： JDK 1.8 采用尾插法的主要原因是解决了 JDK 1.7 在多线程竞争扩容时，链表节点指针错乱，导致产生 死循环 的严重线程安全问题。

一条 K-V 插入的流程

flowchart TD A["开始: put(K key, V value)"] --> B["计算哈希值: hash = hash(key) 扰动函数"] B --> C["初始化/扩容检查: table == null 或 size == 0?"] C -->|是| D["resize(): 初始化容量 16 或指定容量"] C -->|否| E["计算索引: i = (N-1) & hash"] D --> E E --> F["检查 table[i] == null?"] F -->|是: 空桶| G["创建新 Node 并插入 table[i]"] F -->|否: 非空桶| H["检查头节点 hash & key 相同?"] G --> Z["值覆盖? 无, 新增 size++"] H -->|是| I["找到 e, 准备覆盖值"] H -->|否| J["头节点是 TreeNode?"] J -->|是: 红黑树| K["putTreeVal: 树中插入/更新"] J -->|否: 链表| L["遍历链表: 尾插法"] L --> M["遍历中找到相同 hash & key 的 e?"] M -->|是| I M -->|否| N["插入到链表尾部"] N --> O["检查链表长度 binCount >= 8?"] O -->|是| P["treeifyBin(): 容量 < 64? 先扩容, 否则树化"] O -->|否| Q["无操作"] P --> R["树化完成"] K --> R I --> S["替换 e.value = value, 返回旧值"] S --> Z R --> Z Q --> Z Z["modCount++, size++ 检查阈值"] --> T["size > threshold?"] T -->|是: 负载因子超| U["resize(): 扩容 2倍"] T -->|否| V["结束: 返回 null 或旧值"] U --> V style A fill:#e1f5fe style V fill:#c8e6c9
  1. 计算哈希值： 调用 hash(key) 方法（扰动函数）计算键的哈希值 hash。
  2. 初始化/扩容检查 (Resize)：

◦ 检查哈希表数组 table 是否为 null 或长度为 0。

◦ 如果是，调用 resize() 方法进行 初始化（分配默认容量 16，或使用构造函数指定的初始容量）。

  1. 确定索引位置： 根据哈希值和当前数组长度 N，计算元素在数组中的索引 i = (N - 1) & hash。
  2. 空桶处理 (直接插入)：

◦ 如果 table[i] 处为 null (空桶)，则直接在该位置创建新的 Node 节点并插入。

  1. 非空桶处理 (哈希冲突)：

◦ 快速检查头节点： 检查 table[i] 处的头节点的 hash 值和 key 是否与待插入的键值相同。如果相同，则找到目标节点 e，准备进行值覆盖。

◦ 红黑树处理： 如果头节点是 TreeNode 实例，说明该桶已树化。调用红黑树的 putTreeVal 方法在树中插入/更新元素。

◦ 链表处理： 否则，遍历链表。

​ ▪ 使用 尾插法：遍历到链表末尾，将新节点插入到链表的尾部。

​ ▪ 查找重复键： 在遍历过程中，如果找到相同 hash 和 key 的节点 e，则跳出循环，准备进行值覆盖。

​ ▪ 树化判断： 节点插入后，检查当前链表长度 binCount。如果链表长度达到 TREEIFY_THRESHOLD (默认 8)，会调用 treeifyBin() 方法。该方法会进一步判断：如果数组容量小于 MIN_TREEIFY_CAPACITY (默认 64)，则先进行 扩容，而不是直接树化。

  1. 值覆盖： 如果步骤 5 中找到了相同键的节点 e，则用新值替换旧值，并返回旧值。
  2. 扩容检查 (Load Factor)： 增加 modCount (修改次数)。如果 size 增加后超过了 threshold (容量 × 负载因子)，则调用 resize() 方法进行 扩容。
← prev next →