JAVA 集合框架- HashMap

HashMap 是 Java 中最常用的键值对存储容器，它的底层数据结构在不同 Java 版本中有核心优化，但核心设计思路是「数组 + 链表 / 红黑树」的组合，目的是平衡查询、插入的效率。作为Java集合框架Map中最重要的 HashMap，在面试中都快被问包浆了。

HashMap的底层数据结构

1. 哈希桶数组（Node [] table）

这是 HashMap 的基础结构，数组的每个元素被称为桶，每个桶的初始类型是Node节点（实现了Map.Entry接口），结构如下：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 键的哈希值（经过扰动处理，减少哈希冲突） final K key; // 键（不可变） V value; // 值 Node<K,V> next; // 指向下一个节点的引用（用于链表） Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } }

• 数组的长度默认是 16（且必须是 2 的幂次），目的是通过hash & (length-1)替代取模运算，提升哈希计算效率。
• 数组的扩容阈值默认是16 * 0.75 = 12（负载因子 0.75），当元素数量超过阈值时，数组会扩容为原来的 2 倍。

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

当多个键经过哈希处理后得到相同的索引时，需要通过链表来解决哈希冲突——将具有相同索引的键值对通过链表存储起来。

• 例如：键 A 和键 B 的哈希值计算后都指向数组下标 3，那么下标 3 的桶会形成A -> B的链表。
• 链表的问题：如果链表过长（比如超过 8 个节点），查询效率会从 O (1) 退化为 O (n)。

3. 红黑树（优化长链表）

Java 8 引入了红黑树来解决长链表的性能问题：

• 当某个桶的链表节点数≥ 8，且数组长度≥ 64时，链表会转为红黑树（TreeNode 类型）；
• 当红黑树的节点数≤ 6时，会重新转回链表（红黑树维护成本高，短链表更高效）；
• 红黑树的查询效率是 O (log n)，远高于长链表的 O (n)。

注意：（我一开始以为这个64是当前数组中元素的个数 实际上是数组的容量 一定要清楚）

树化需要满足两个核心阈值条件：（这俩缺一不可 仅仅满足链表长度是不能转换成红黑树的）

• 链表长度阈值：冲突链表的节点数 ≥TREEIFY_THRESHOLD（源码中固定为 8）；
• 数组容量阈值：哈希桶数组的长度 ≥MIN_TREEIFY_CAPACITY（源码中固定为 64）。

下面是源码中treeifyBin方法的核心逻辑（Java 8），对应树化的判断流程：

final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 第一步：判断数组容量是否 ≥ MIN_TREEIFY_CAPACITY(64) // 若不满足 → 直接扩容（resize），不树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 第二步：若数组容量达标，且桶内有链表 → 真正执行链表转红黑树 else if ((e = tab[index = (n - 1) & hash]) != null) { // 链表转红黑树的具体逻辑（省略） TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

哈希表的寻址过程

哈希表（以 Java HashMap 为例）的寻址过程，本质是通过键的哈希值定位到哈希桶数组中具体位置的过程，核心是哈希计算 → 下标计算 → 冲突处理 三步，而且HashMap 的寻址过程贯穿put/get等核心方法。

1：计算键的哈希值（Hash 扰动）

首先对传入的key计算哈希值，目的是尽可能让不同的 key 生成不同的哈希值，减少后续冲突。

• 如果key == null：HashMap 允许 key 为 null，直接固定哈希值为 0；
• 如果key != null：调用key.hashCode()得到原始哈希值（int 类型，范围 -2³¹ ~ 2³¹-1），然后对这个值做「扰动处理」（哈希扰动）：

static final int hash(Object key) { int h; // 扰动公式：h = key.hashCode() ^ (h >>> 16) return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

为什么要扰动？原始哈希值的高位特征可能被浪费（后续下标计算只用到低位），通过「高 16 位异或低 16 位」，让高位特征参与到后续下标计算中，进一步减少哈希冲突。

2：计算数组下标（定位桶位置）

得到扰动后的哈希值后，需要将其映射到哈希桶数组（Node[] table）的合法下标范围内，核心公式：

int index = hash & (table.length - 1);

• 为什么不用取模（%）？因为 HashMap 规定数组长度必须是 2 的幂次（如 16、32、64...），此时table.length - 1的二进制是全 1（比如 16-1=15 → 0b1111），hash & (length-1)等价于hash % length，但位运算比取模运算快得多。
• 示例：假设数组长度为 16（length-1=15=0b1111），某个 key 的哈希值扰动后为 23（0b10111），则下标 = 23 & 15 = 7（0b00111），该 key 会被定位到数组下标 7 的桶中。

3：处理哈希冲突（桶内寻址）

如果下标对应的桶为空，直接将节点放入即可；如果桶不为空（哈希冲突），则需要在桶内进一步寻址：

1. 桶内是链表：遍历链表，逐个比较节点的hash值和key（用equals()）：
   • 如果找到hash相等且key.equals()为 true 的节点：就是目标节点（get 则返回 value，put 则替换 value）；
   • 如果遍历完链表都没找到：说明是新节点（put 则添加到链表尾部）。
2. 桶内是红黑树：调用红黑树的查找方法（如getTreeNode()），通过红黑树的特性快速定位节点：
   • 红黑树会根据节点的hash和key进行比较，查找效率为 O (log n)，远高于链表的 O (n)。

4：扩容判断

每次插入新元素后，检查是否需要扩容，当前元素的个数是否大于阈值（容量*负载因子），如果大于，数组容量扩招为原来的2倍，并且重新计算每个节点的索引，进行数据重新分布。

哈希寻址示例

假设我们要从 HashMap 中获取key = "Java"的值，完整寻址过程：

1. 计算key.hashCode()→ 得到原始哈希值（比如 3254818）；
2. 扰动处理：3254818 ^ (3254818>>> 16) → 得到最终哈希值（比如 3254820）；
3. 计算下标：3254820 & (16-1) = 4 → 定位到数组下标 4 的桶；
4. 桶内有链表（节点数 < 8），遍历链表：
   • 第一个节点 key 是 "Python" → hash 不等，跳过；
   • 第二个节点 key 是 "Java" → hash 相等且equals()为 true → 找到目标节点，返回其 value。

HashMap put流程示例

现在用一个Java 8 HashMap 插入数据的完整例子，一步步展示数组、链表、红黑树的变化过程。

• 初始化一个空 HashMap，默认参数：数组长度（容量）=16，负载因子 = 0.75，扩容阈值 = 16×0.75=12，树化阈值（链表转红黑树）=8，退链阈值 = 6。
• 为了简化，我们假设插入的 key 计算后得到的哈希值对应的数组下标全部为 3（模拟极端哈希冲突场景，方便看链表 / 红黑树变化）。

步骤 1：插入第 1~7 个元素（key=A~G，value=1~7）

寻址过程（以 key=A 为例，B~G 逻辑一致）

1. 计算 hash 值：调用key.hashCode()得到原始哈希值，执行扰动运算hash = A.hashCode() ^ (A.hashCode() >>> 16)；
2. 计算数组下标：当前数组容量 = 16 → 下标 = hash & (16-1) = hash & 15 = 3；
3. 桶内操作：检查 table [3] 为空 → 新建 Node 节点（hash = 计算出的 hash 值，key=A，value=1，next=null）放入 table [3]。（key=B~G 依次执行上述步骤，因下标均为 3，且 key 不重复，尾插到链表尾部）

原有状态补充

• 数组：下标 3 的桶指向链表头（A），链表长度 = 7；
• 状态：无扩容、无树化，size=7 < threshold=12；
• 结构：table[3] = A→B→C→D→E→F→G。

---

步骤 2：插入第 8 个元素（key=H，value=8）→ 触发扩容检查

寻址过程

1. 计算 hash 值：执行hash = H.hashCode() ^ (H.hashCode() >>> 16)；
2. 计算数组下标：当前数组容量 = 16 → 下标 = hash & 15 = 3；
3. 桶内操作：
   • 检查 table [3] 不为空 → 遍历链表（A→G），对比每个节点的 hash 值和 key.equals ()，确认无重复 key；
   • 尾插法将 H 节点添加到链表尾部，链表长度变为 8；
4. 触发树化检查：链表长度 = 8 → 调用treeifyBin(tab, hash)；
   • 检查数组容量 = 16 < 64 → 放弃树化，触发resize()扩容。

扩容后的寻址（所有节点重新哈希）

1. 数组扩容至 32，重新计算每个节点的下标：hash & (32-1) = hash & 31 = 3（仍为 3）；
2. 所有节点（A~H）按原链表顺序迁移到新数组的 table [3] 桶中。

原有状态补充

• 扩容后：数组容量 = 32，threshold=24，size=8 < 24；
• 结构：table[3] = A→B→C→D→E→F→G→H。

---

步骤 3：插入第 9~24 个元素（key=I~X，value=9~24）

寻址过程（以 key=I 为例，J~X 逻辑一致）

1. 计算 hash 值：执行hash = I.hashCode() ^ (I.hashCode() >>> 16)；
2. 计算数组下标：当前数组容量 = 32 → 下标 = hash & 31 = 3；
3. 桶内操作：
   • 遍历 table [3] 的链表（A→H），确认 key=I 无重复；
   • 尾插法添加到链表尾部，size 从 9 逐步增长到 24。

关键节点（key=X，第 24 个元素）的寻址补充

• 插入 X 后，size=24 = threshold=24 → 因源码中扩容条件是size > threshold，故暂不扩容；
• 链表长度 = 24，数组容量 = 32 < 64 → 仍不树化；
• 结构：table[3] = A→B→…→X。

---

步骤 4：插入第 25 个元素（key=Y，value=25）→ 再次扩容

寻址过程

1. 计算 hash 值：执行hash = Y.hashCode() ^ (Y.hashCode() >>> 16)；
2. 计算数组下标：当前数组容量 = 32 → 下标 = hash & 31 = 3；
3. 桶内操作：
   • 遍历链表（A→X），确认 key=Y 无重复 → 尾插法添加，size=25；
   • size=25 > threshold=24 → 触发resize()扩容。

扩容后的寻址（所有节点重新哈希）

1. 数组扩容至 64，重新计算下标：hash & (64-1) = hash & 63 = 3（仍为 3）；
2. 所有节点（A~Y）迁移到新数组的 table [3] 桶中，链表长度 = 25；
3. 扩容后：数组容量 = 64，threshold=48，满足树化的容量条件。

---

步骤 5：触发链表转红黑树

寻址 & 树化过程

插入 Y 后，HashMap 在完成插入操作后，立即对 table [3] 的链表执行树化检查：

1. 寻址验证：确认 table [3] 的链表长度 = 25 ≥ 8，且数组容量 = 64 ≥ 64；
2. 执行树化：调用treeifyBin(tab, hash)→ 将链表节点（Node）逐个转为树节点（TreeNode），按红黑树规则排列；
3. 最终寻址结果：table [3] 指向红黑树根节点，后续对该桶的寻址将走红黑树的查找逻辑（O (log n)）。

原有状态补充

• 最终状态：table [3] 指向红黑树根节点，size=25，无链表。

---

步骤 6：删除元素至红黑树节点数 = 6（key=Y、X 删除）

寻址过程（以删除 key=Y 为例）

1. 计算 hash 值：执行hash = Y.hashCode() ^ (Y.hashCode() >>> 16)；
2. 计算数组下标：当前数组容量 = 64 → 下标 = hash & 63 = 3；
3. 桶内操作：
   • 遍历红黑树，通过 hash 值和 key.equals () 定位到 Y 节点；
   • 删除 Y 节点，红黑树自动调整结构以满足红黑树特性；
   • 重复上述步骤删除 X 节点，红黑树节点数降至 6 → 触发退链逻辑；
   • 红黑树转回链表，table [3] 重新指向链表头节点。

原有状态补充

• 状态：链表长度 = 6，数组容量 = 64，无红黑树。

---

步骤 7：插入重复 key（key=A，value=99）

寻址过程

1. 计算 hash 值：执行hash = A.hashCode() ^ (A.hashCode() >>> 16)；
2. 计算数组下标：当前数组容量 = 64 → 下标 = hash & 63 = 3；
3. 桶内操作：
   • 遍历 table [3] 的链表（A→W），对比每个节点的 hash 值（相等）+ key.equals (A)（true）；
   • 找到目标节点后，仅将 value 从 1 更新为 99，不新增节点、不改变链表结构。

原有状态补充

• 结构：table[3] = A(99)→B→C→D→E→F→G→…→W。

手搓HashMap源码

/** * @Author * @Date 2021/11/21 * @Description 自己实现HashMap（修复版） */ public class ThirdHashMap<K, V> { /** * 节点类 */ class Node<K, V> { //键值对 private K key; private V value; //链表，后继 private Node<K, V> next; public Node(K key, V value) { this.key = key; this.value = value; } public Node(K key, V value, Node<K, V> next) { this.key = key; this.value = value; this.next = next; } } //默认容量（2的幂） final int DEFAULT_CAPACITY = 16; //负载因子 final float LOAD_FACTOR = 0.75f; //HashMap的大小 private int size; //桶数组 Node<K, V>[] buckets; /** * 无参构造器，设置桶数组默认容量 */ public ThirdHashMap() { buckets = new Node[DEFAULT_CAPACITY]; size = 0; } /** * 有参构造器，指定桶数组容量（自动向上取整为2的幂） */ public ThirdHashMap(int capacity) { int cap = tableSizeFor(capacity); buckets = new Node[cap]; size = 0; } /** * 计算大于等于cap的最小2的幂 */ private int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : n + 1; } /** * 哈希函数，获取地址（修复版：哈希扰动+位运算） */ private int getIndex(K key, int length) { if (key == null) { return 0; // 支持null key，哈希值为0 } int h = key.hashCode(); // 哈希扰动：高低16位异或，减少冲突 h ^= (h >>> 16); // 位运算替代取模，仅当length为2的幂时生效 return h & (length - 1); } /** * put方法 */ public void put(K key, V value) { putVal(key, value, buckets); // 先插入再判断扩容，避免size超过阈值 if (size >= buckets.length * LOAD_FACTOR) { resize(); } } /** * 将元素存入指定的node数组（修复版：尾插法） */ private void putVal(K key, V value, Node<K, V>[] table) { int index = getIndex(key, table.length); Node node = table[index]; // 插入位置为空，直接插入 if (node == null) { table[index] = new Node<>(key, value); size++; return; } // 插入位置不为空，遍历链表 while (node != null) { // key相同，覆盖value if ((node.key == key || (node.key != null && node.key.equals(key)))) { node.value = value; return; } // 到达链表尾部，尾插法插入 if (node.next == null) { node.next = new Node<>(key, value); size++; return; } node = node.next; } } /** * 扩容 */ private void resize() { // 创建两倍容量的桶数组（保证2的幂） int newCapacity = buckets.length << 1; Node<K, V>[] newBuckets = new Node[newCapacity]; // 重新散列 rehash(newBuckets); buckets = newBuckets; } /** * 重新散列当前元素（修复版：避免size重复累加） */ private void rehash(Node<K, V>[] newBuckets) { // 遍历旧桶数组，迁移节点 for (int i = 0; i < buckets.length; i++) { Node<K,V> node = buckets[i]; while (node != null) { Node<K,V> next = node.next; // 保存next，避免链表断裂 int index = getIndex(node.key, newBuckets.length); // 尾插法迁移 if (newBuckets[index] == null) { newBuckets[index] = new Node<>(node.key, node.value); } else { Node<K,V> tail = newBuckets[index]; while (tail.next != null) { tail = tail.next; } tail.next = new Node<>(node.key, node.value); } node = next; } } } /** * 获取元素 */ public V get(K key) { int index = getIndex(key, buckets.length); Node node = buckets[index]; while (node != null) { if ((node.key == key || (node.key != null && node.key.equals(key)))) { return (V) node.value; } node = node.next; } return null; } /** * 返回HashMap大小 */ public int size() { return size; } }

HashMap扩容机制：

⏰ 一、 扩容的触发条件

扩容并非随意发生，主要在put元素时进行判断。当满足以下任一条件时，就会触发扩容：

1. 元素数量超过阈值：这是最常见的情况。当 HashMap 中的元素数量 (size) 大于扩容阈值 (threshold) 时触发。

   • 扩容阈值计算公式：threshold = capacity * loadFactor
   • 默认初始容量 (capacity) 为 16，默认负载因子 (loadFactor) 为 0.75，所以初始阈值为16 * 0.75 = 12。当放入第 13 个元素时，就会触发扩容。

2. 链表树化前的检查：当一个桶中的链表长度达到树化阈值（默认为 8）时，HashMap 会先检查当前数组的容量。如果容量小于最小树化容量（默认为 64），则会优先触发扩容，而不是立即转换为红黑树。

   • 设计思想：在数组容量较小时，通过扩容增加桶的数量，可以有效分散冲突的元素，可能使链表长度降低，从而避免了过早地转换为占用更多内存的红黑树。

🚀 二、 核心扩容流程 (resize)

JDK 1.8 对扩容过程进行了重大优化，核心在于高效地迁移元素，避免了重新计算哈希值。整个过程可以概括为三步：

1. 计算新容量
   创建一个新数组，其容量是旧数组的 2 倍。例如，从 16 扩容到 32。这保证了容量始终是 2 的幂次方，为后续的位运算优化打下基础。

2. 创建新数组
   根据计算出的新容量，创建一个新的Node[]数组。

3. 迁移旧数据 (Rehash)
   这是最关键、最耗时的步骤。JDK 1.8 利用容量翻倍的特性，通过一个巧妙的位运算，将旧数组中的元素直接拆分到新数组的两个可能位置上，而无需重新计算哈希。

💡 三、 关键细节：JDK 1.8 的高效迁移

在 JDK 1.7 中，迁移元素需要重新计算每个元素的哈希值和新索引，并且在多线程环境下，使用头插法可能导致链表形成环，引发死循环。

JDK 1.8 对此进行了优化：

• 核心优化：由于新容量是旧容量的 2 倍，一个元素在新数组中的位置只有两种可能：

  1. 保持在原索引位置。
  2. 移动到原索引 + 旧容量的位置。

• 判断方法：通过(e.hash & oldCap) == 0这个简单的位运算来判断。

  • 如果为true：说明该元素的哈希值在“新增的那一位”上是 0，它在新数组中的位置不变。
  • 如果为false：说明该元素的哈希值在“新增的那一位”上是 1，它需要被移动到原索引 + oldCap的位置。

• 迁移方式：

  • 链表：JDK 1.8 使用尾插法来迁移链表。在迁移过程中，会将旧链表拆分成两条新链表（低位链表loHead和高位链表hiHead），分别放到新数组的对应位置。尾插法保证了链表元素的原有顺序，彻底解决了 JDK 1.7 中多线程扩容可能导致的死循环问题。
  • 红黑树：如果桶中是红黑树，会调用split()方法，按照同样的逻辑将树节点拆分成两个子树或链表，再放入新数组。