HashMap 的底层原理

HashMap 的底层原理（Java 8 版本）

HashMap 是 Java 中最常用的基于哈希表的Map实现，它存储键值对（key-value），具有 O(1) 平均时间复杂度 的查询、插入和删除性能。其底层实现涉及 数组 + 链表 + 红黑树 的结构，并在 Java 8 中进行了优化（链表转红黑树）。下面详细分析其核心机制：

---

核心数据结构

HashMap 的底层是一个 Node<K,V>[] table 数组（默认大小 16），每个元素是一个链表或红黑树的节点：

transient Node<K,V>[] table; // 存储键值对的数组

• Node 类（链表节点）：

  static class Node<K,V> implements Map.Entry<K,V> {final int hash;      // key 的哈希值final K key;         // 键V value;             // 值Node<K,V> next;      // 下一个节点（链表结构）
  }
  

• TreeNode 类（红黑树节点，Java 8 新增）：

  • 当链表长度超过阈值（默认 8）时，链表会转换为红黑树，提升查询效率（从 O(n) → O(log n)）。

---

核心参数

参数	默认值	作用
initialCapacity	16	初始数组大小（必须是 2 的幂次方）。
loadFactor	0.75	负载因子，决定扩容时机（容量 * loadFactor 触发扩容）。
threshold	12	扩容阈值 = 容量 * loadFactor（默认 16 * 0.75 = 12）。
TREEIFY_THRESHOLD	8	链表长度超过此值时，转换为红黑树。
UNTREEIFY_THRESHOLD	6	红黑树节点数减少到此值时，退化为链表。

---

核心操作原理

哈希计算与数组索引

• 计算 key 的哈希值：

  • 先调用key.hashCode()，再通过hash()方法扰动哈希值（减少哈希冲突）：

    static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 高16位与低16位异或
    }
    

  • 扰动函数的作用：将高位哈希值参与低位运算，避免哈希冲突（如 key1.hashCode() 和 key2.hashCode()的高位不同但低位相同的情况）。

• 计算数组索引：

  • 使用(n - 1) & hash计算索引（n是数组长度，必须是 2 的幂次方）：

    int index = (table.length - 1) & hash; // 等价于 index = hash % n（但位运算更快）
    

  • 为什么用 & 而不是 %？

    • n 是 2 的幂次方时，(n - 1) & hash 等价于 hash % n，但位运算效率更高。

插入（put）操作

1. 计算 key 的哈希值和数组索引。
2. 检查数组是否为空或长度为 0：
   • 如果是，先调用 resize()扩容（默认初始容量 16）。
3. 检查当前索引位置是否有节点：
   • 无节点：直接插入新 Node。
   • 有节点：
     • 如果 key 已存在：更新 value（equals() 比较 key）。
     • 如果 key 不存在：
       • 链表结构：插入到链表末尾。
       • 链表长度 ≥ 8：转换为红黑树（TREEIFY_THRESHOLD=8）。
4. 检查是否需要扩容：
   • 如果当前元素数量 ≥ threshold，调用 resize()`扩容（容量翻倍）。

查询（get）操作

1. 计算 key 的哈希值和数组索引。
2. 检查当前索引位置是否有节点：
   • 无节点：返回 null。
   • 有节点：
     • 链表结构：遍历链表，用 equals() 比较 key。
     • 红黑树结构：调用红黑树的查找方法（O(log n)）。

扩容（resize）操作

• 触发条件：元素数量 ≥ threshold（默认 16 * 0.75 = 12）。
• 扩容过程：
  1. 新容量 = 旧容量 × 2（必须是 2 的幂次方）。
  2. 遍历旧数组的所有节点，重新计算哈希值和索引：
     • 旧容量为 2 的幂次方时，节点的新索引要么不变，要么是 旧索引 + 旧容量（利用哈希值的高位信息减少重新计算）。
  3. 如果链表长度 ≥ 8，转换为红黑树。

链表转红黑树（treeifyBin）

• 条件：链表长度 ≥ TREEIFY_THRESHOLD=8 且 数组长度 ≥ MIN_TREEIFY_CAPACITY=64。
• 作用：提升查询效率（从 O(n) → O(log n)）。

红黑树退化为链表（untreeify）

• 条件：红黑树节点数 ≤ UNTREEIFY_THRESHOLD=6。
• 作用：减少内存占用（红黑树比链表占用更多空间）。

---

关键特性

1. 哈希冲突处理：
   • 链地址法：相同哈希值的 key 存储在同一个链表或红黑树中。
   • 扰动函数：减少哈希冲突的概率。
2. 扩容机制：
   • 容量翻倍，重新计算所有节点的索引（利用(n - 1) & hash的特性减少计算量）。
3. 红黑树优化：
   • 链表过长时转换为红黑树，提升查询效率（Java 8 新增）。
4. 线程不安全：
   • 多线程环境下可能导致死循环或数据丢失（需用 ConcurrentHashMap 或 Collections.synchronizedMap）。

---

总结

HashMap 的底层是基于数组 + 链表 + 红黑树的哈希表实现，其核心原理包括：

1. 哈希计算：通过 key.hashCode() 和扰动函数计算哈希值，再用 (n - 1) & hash计算数组索引。
2. 插入操作：先检查数组是否为空，再检查当前索引是否有节点，若无则插入；若有则更新或插入链表/红黑树。
3. 扩容机制：当元素数量超过 容量 * loadFactor 时，容量翻倍并重新计算所有节点的索引。
4. 链表转红黑树：当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转换为红黑树以提升查询效率。
5. 线程不安全：多线程环境下需用 ConcurrentHashMap 替代。
   其设计目标是平衡查询效率、内存占用和扩容成本。