Java 哈希表详解（以 HashMap 为核心）
在 Java 中，“哈希表”最典型、最常用的实现就是 HashMap（JDK 1.8+ 版本）。它几乎是所有 Java 开发者日常开发中使用频率最高的数据结构之一，也是面试中出现频率极高的考点。
下面从基础 → 原理 → 源码关键点 → 常见面试题 完整梳理。
1. 什么是哈希表（Hash Table / 散列表）？
哈希表是一种根据键（key）直接进行访问的数据结构。
核心思想：通过哈希函数把任意的 key 映射成一个固定范围的整数（数组下标），然后把键值对存储在数组对应位置。
理想情况下，查找/插入/删除的时间复杂度是 O(1)。
但现实中必然存在哈希冲突（不同 key 算出相同下标），所以需要冲突解决策略。
Java 中的 HashMap 采用的经典方案是：
- 链地址法（Separate Chaining） → 数组 + 链表
- JDK 1.8 优化 → 当链表过长时 → 转为红黑树
2. HashMap 的核心数据结构（JDK 1.8+）
HashMap 内部结构 = 数组（Node[] table） + 链表 + 红黑树（可选）- table：Node[] 数组，也叫哈希桶（bucket array）
- 每个桶里可能是一个 Node（单节点），也可能是链表，也可能是红黑树
- Node：静态内部类，包含 hash、key、value、next 指针
关键字段（默认值）：
| 参数 | 默认值 | 含义 |
|---|---|---|
| DEFAULT_INITIAL_CAPACITY | 16 | 初始容量（必须是 2 的幂） |
| DEFAULT_LOAD_FACTOR | 0.75f | 负载因子（扩容阈值 = capacity × loadFactor） |
| TREEIFY_THRESHOLD | 8 | 链表转红黑树阈值 |
| UNTREEIFY_THRESHOLD | 6 | 红黑树退化回链表阈值 |
| MIN_TREEIFY_CAPACITY | 64 | 转为红黑树的最小容量要求（防止过早转树） |
3. HashMap 的核心流程（put / get）
put(K key, V value) 流程
- 计算 key 的 hash 值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 高16位参与扰动
}- 计算数组下标（最关键的一步）
index = (n - 1) & hash // n = table.length，必须是2的幂- 插入逻辑：
- 如果该位置为空 → 直接放入新 Node
- 如果已有元素：
- hash 相同且 key equals → 覆盖 value
- 否则 → 加入链表尾部（JDK 1.8 尾插法）
- 如果链表长度 ≥ 8 且 table 容量 ≥ 64 → 转为红黑树
- 插入后 size++，如果 size > threshold → 扩容
get(K key) 流程
- 计算 hash 和 index
- 在 table[index] 位置查找：
- 如果是普通 Node → 直接比较
- 如果是链表 → 顺序遍历比较 key
- 如果是红黑树 → O(log n) 查找
4. 为什么 JDK 1.8 要引入红黑树？
JDK 1.7：只有数组 + 链表（头插法，扩容时可能死循环）
JDK 1.8 变化：
- 尾插法（避免扩容死循环）
- 链表长度 ≥ 8 + 容量 ≥ 64 → 转为红黑树
- 红黑树节点数 ≤ 6 → 退化为链表
为什么是 8？
（官方 + 统计学依据）
- 泊松分布下，链表长度达到 8 的概率非常低（约百万分之一）
- 当冲突严重到链表长度 8 时，说明 hash 分布已经很差了
- 转为红黑树后，查询从 O(n) → O(log n)，收益明显
- 小于 8 时，链表遍历更快（缓存友好、节点少）
为什么退化阈值是 6？
留出缓冲区间（8 → 7 → 6），避免频繁树化和退化切换（抖动）。
5. 哈希冲突的几种解决方式对比（面试常问）
| 方式 | 原理 | 优点 | 缺点 | Java HashMap 是否使用 |
|---|---|---|---|---|
| 开放地址法 | 冲突时找下一个空位 | 无额外空间 | 容易聚集，删除复杂 | 否 |
| 链地址法 | 冲突时挂链表 | 简单，实现容易 | 链表过长查询慢 | 是（主方案） |
| 再哈希法 | 多个 hash 函数 | 冲突率低 | 计算开销大 | 否 |
| 红黑树优化 | 链表长时转平衡树 | 查询 O(log n) | 维护复杂，节点开销大 | 是（JDK 1.8+） |
6. HashMap 经典面试题速查（2025-2026 高频）
| 题号 | 问题 | 核心答案要点 |
|---|---|---|
| 1 | HashMap 底层数据结构？ | 数组 + 链表 + 红黑树（JDK 1.8+） |
| 2 | hash() 方法为什么要有扰动？ | 让高位也参与运算，减少冲突（低位相同，高位不同也能分散） |
| 3 | 为什么容量必须是 2 的幂？ | (n-1) & hash 运算等价于取模，且位运算更快 |
| 4 | 负载因子为什么是 0.75？ | 时间与空间的折中（太小浪费空间，太大链表长性能差） |
| 5 | put 时扩容机制？ | size > threshold 时扩容为原来的 2 倍，rehash（JDK 1.8 优化为高低位分离） |
| 6 | HashMap 为什么线程不安全？ | put/resize 时多线程竞争会导致数据丢失、死循环（1.7）、覆盖等 |
| 7 | 为什么链表转红黑树阈值是 8？ | 泊松分布 + 性能权衡（链表遍历快 vs 树查找快） |
| 8 | HashMap 可以放 null 键/值吗？ | 可以，null key 的 hash=0，放 table[0] |
| 9 | HashMap 和 Hashtable 的区别？ | Hashtable 线程安全（synchronized 方法）、不允许 null、不建议使用 |
| 10 | ConcurrentHashMap 和 HashMap 区别？ | 线程安全，1.8 后用 CAS + synchronized，细粒度锁 |
总结一句话
HashMap 是“数组 + 链表 + 红黑树”的哈希表实现，通过扰动函数 + 链地址法 + 红黑树优化，追求 O(1) 平均时间复杂度，同时在极端冲突下也能退化到 O(log n)。
你现在最想深入哪一块？
- 扩容时高低位分离的具体代码过程
- 红黑树节点插入/删除的简化讲解
- HashMap 在多线程下的具体不安全表现
- 手写一个简易 HashMap
告诉我，我可以继续展开更细！
