1. 什么是哈希表
哈希表（Hash Table）是一种通过“键值对”形式存储数据的结构，核心思想是把键映射到一个内部数组的下标，从而实现接近 O(1) 的平均查找、插入和删除效率。Java 中最常用的实现就是HashMap，它是基于哈希表原理设计的集合类。
哈希表解决的核心问题是：当数据量很大时，如何不用逐个比较就能快速定位元素。它借助散列函数把任意键转换为整数索引，例如把字符串"name"映射到数组的第几个位置，然后直接访问该位置。
小结：哈希表 = 数组 + 散列函数 + 冲突处理机制。数组负责快速定位，散列函数决定存放位置，冲突处理保证不同键映射到同一位置时也能正常工作。
2. 为什么需要哈希表
对比常见的线性结构，哈希表的优势非常明显。顺序表和链表需要遍历比较，LinkedList 查找平均时间复杂度为 O(n)，而 HashMap 理想情况下查找为 O(1)。当应用需要频繁通过某个唯一标识查询数据时，例如根据用户 ID 查用户、根据商品编码查库存，哈希表是更合适的选择。
不过在追求速度的同时，哈希表也带来了一些代价：它会占用更多内存、无法保证遍历顺序（HashMap不保证顺序）、键对象需要正确实现hashCode()和equals()方法。
| 结构 | 查找平均复杂度 | 是否有序 | 典型场景 |
|---|---|---|---|
| ArrayList | O(n) | 按下标有序 | 顺序访问、随机下标访问 |
| LinkedList | O(n) | 按插入顺序 | 频繁插入删除 |
| HashMap | O(1) | 不保证顺序 | 按键快速查找 |
| TreeMap | O(log n) | 按键自然排序 | 需要范围查询或排序 |
3. Java 哈希表家族
Java 中与哈希表相关的类主要有Hashtable、HashMap、LinkedHashMap和ConcurrentHashMap。日常开发优先推荐HashMap；需要线程安全时优先考虑ConcurrentHashMap，而不是老旧的Hashtable。
- Hashtable：JDK 1.0 时代的老类，方法大多被 synchronized 修饰，不允许 null 键和 null 值，性能较差，基本不推荐使用。
- HashMap：基于哈希表的 Map 实现，允许一个 null 键和多个 null 值，非线程安全，性能最好。
- LinkedHashMap：在 HashMap 基础上增加双向链表，可以保持插入顺序或访问顺序。
- ConcurrentHashMap：线程安全的哈希表，JDK 8 起使用 CAS 和 synchronized 精细化锁，性能远高于 Hashtable。
4. HashMap 的基本使用
下面是一个最基础的示例，演示创建、插入、读取、判断和遍历。
import java.util.HashMap; import java.util.Map; public class HashMapBasic { public static void main(String[] args) { // 创建 HashMap，键为 String，值为 Integer Map<String, Integer> scoreMap = new HashMap<>(); // 插入键值对 scoreMap.put("Alice", 95); scoreMap.put("Bob", 88); scoreMap.put("Cindy", 92); // 根据键获取值 Integer aliceScore = scoreMap.get("Alice"); System.out.println("Alice 的成绩：" + aliceScore); // 判断键是否存在 System.out.println("是否包含 Bob：" + scoreMap.containsKey("Bob")); // 键不存在时返回 null System.out.println("查询不存在的键：" + scoreMap.get("David")); // 获取或提供默认值 int davidScore = scoreMap.getOrDefault("David", 0); System.out.println("David 的默认成绩：" + davidScore); // 遍历键值对 for (Map.Entry<String, Integer> entry : scoreMap.entrySet()) { System.out.println(entry.getKey() + " => " + entry.getValue()); } // 删除元素 scoreMap.remove("Bob"); System.out.println("删除后大小：" + scoreMap.size()); } }注意，get()返回 null 有两种可能：键真的不存在，或者键存在但值为 null。如果业务中需要区分，应优先使用containsKey()判断。
5. hashCode 和 equals：自定义对象的正确姿势
当使用自定义对象作为 HashMap 的键时，必须同时正确重写hashCode()和equals()。两者遵循一个重要约定：如果两个对象 equals 相等，那么它们的 hashCode 必须相等；反之，hashCode 相同不代表 equals 一定相等。
哈希表的查找流程分两步：先通过hashCode()定位到某个桶，再通过equals()在桶内确认是否是同一个键。如果只重写equals()而不重写hashCode()，两个逻辑相同的对象可能会落到不同的桶中，导致无法正确取回数据。
import java.util.HashMap; import java.util.Map; import java.util.Objects; public class PersonKeyDemo { static class Person { private final String id; private final String name; public Person(String id, String name) { this.id = id; this.name = name; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return Objects.equals(id, person.id) && Objects.equals(name, person.name); } @Override public int hashCode() { return Objects.hash(id, name); } } public static void main(String[] args) { Map<Person, String> map = new HashMap<>(); Person person1 = new Person("1001", "Tom"); Person person2 = new Person("1001", "Tom"); map.put(person1, "工程师"); // 两个对象内容相同但引用不同，能命中同一个桶并正确取值 System.out.println(map.get(person2)); } }开发中可以借助Objects.hash()和Objects.equals()快速生成正确实现；如果键是可变对象，放入 HashMap 后修改其参与 hashCode 计算的字段，会导致对象“丢失”，应尽量避免使用可变对象作为键。
6. 哈希冲突与处理机制
哈希冲突是指不同键经过散列函数后得到相同的数组下标。冲突不可避免，关键是如何高效处理。常见的策略有链地址法和开放寻址法。
6.1 链地址法
Java 的 HashMap 主要使用链地址法：数组的每个位置是一个桶，桶里可以挂链表或红黑树。多个键落到同一个桶时，依次链接起来；查找时先定位桶，再遍历桶内结构用 equals 比较。
6.2 开放寻址法
开放寻址法不引入链表，冲突后直接按某种探测序列寻找下一个可用位置。ThreadLocal内部的ThreadLocalMap就采用了线性探测思想。这种方式的优势是连续内存、缓存友好，但需要处理删除标记，装载因子不能太高。
HashMap 选择链地址法的原因之一是开放寻址法对哈希函数质量要求更高，负载率上升后性能下降明显，而链地址法在冲突较重时还能通过红黑树优化。
7. JDK 8 HashMap 的底层结构
JDK 8 中 HashMap 底层是一个Node<K,V>[] table数组。每个Node保存了键、值、hash 值和指向下一个节点的引用。当某个桶的链表长度超过阈值 8 且数组长度达到 64 时，链表会转换为红黑树，降低极端冲突时从 O(n) 到 O(log n) 的退化风险；当节点减少到 6 以下时，又会退回链表。
HashMap 有一个重要字段threshold，等于容量乘以负载因子（默认 0.75）。当元素数量超过该阈值时触发扩容，容量翻倍，所有旧元素需要重新散列到新数组中。
- 默认初始容量：16。
- 默认负载因子：0.75，平衡了空间利用率和冲突概率。
- 树化阈值：单桶链表长度达到 8 时可能转为红黑树。
- 链表化阈值：树节点数降到 6 时退回链表。
8. HashMap 的 put 流程
理解源码可以从put方法入手，整体流程如下。
- 计算键的哈希值：
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)。高 16 位与低 16 位异或，目的是让高位也参与索引计算，减少低位相同时的冲突。 - 计算数组下标：
(n - 1) & hash。因为容量 n 始终是 2 的幂，这一步等价于对 n 取模，但位运算更快。 - 如果数组未初始化，先调用
resize()初始化；如果目标桶为空，直接放入新节点。 - 如果目标桶已有节点，则判断是否同一个键；如果是，直接替换 value。
- 如果桶内是红黑树，走树的插入逻辑；否则遍历链表，找到相同键则更新，找不到则尾插新节点。
- 插入后判断是否超过阈值，超过就扩容；如果链表长度达到树化阈值，执行树化。
下面用代码模拟一次手动定位索引的过程，帮助理解下标计算。
public class HashIndexDemo { public static void main(String[] args) { String key = "hello"; // 模拟 HashMap 计算哈希值的过程 int h = key.hashCode(); int hash = h ^ (h >>> 16); // 容量为 16，下标通过 (n - 1) & hash 得到 int capacity = 16; int index = (capacity - 1) & hash; System.out.println("原始 hashCode：" + h); System.out.println("扰动后的 hash：" + hash); System.out.println("数组下标：" + index); } }9. 扩容机制
扩容发生在元素数量超过threshold时。扩容会创建容量翻倍的新数组，然后遍历旧数组的每个桶，把节点重新分配到新数组中。由于新容量也是 2 的幂，旧索引为 i 的节点只会分布到 i 或 i + oldCap 两个位置之一，这就是源码中hiHead和loHead两个链表优化的基础。
JDK 7 在并发扩容时采用头插法，多线程环境下可能形成环形链表，导致get()死循环；JDK 8 改为尾插法后解决了该问题，但 HashMap 依然不适合多线程写操作，写并发应使用ConcurrentHashMap。
import java.util.HashMap; import java.util.Map; public class HashMapResizeDemo { public static void main(String[] args) { Map<String, Integer> map = new HashMap<>(4); // 初始容量 4，负载因子 0.75，阈值为 3 map.put("a", 1); map.put("b", 2); map.put("c", 3); System.out.println("插入 3 个元素后大小：" + map.size()); // 第 4 个元素会触发扩容 map.put("d", 4); System.out.println("插入第 4 个元素后大小：" + map.size()); } }实际创建 HashMap 时，如果能够预估元素数量，建议在构造器中指定初始容量，避免频繁扩容带来的性能损耗。容量应设置为 2 的幂，例如预期 1000 个元素且负载因子 0.75，可设置初始容量为 2048。
10. HashMap 与 Hashtable 对比
| 对比项 | HashMap | Hashtable |
|---|---|---|
| 出现版本 | JDK 1.2 | JDK 1.0 |
| 线程安全 | 否 | 是，但锁粒度大 |
| null 键和 null 值 | 允许 | 不允许，会抛 NullPointerException |
| 性能 | 较高 | 较差 |
| 迭代器 | fail-fast | Enumerator，部分方法也支持 fail-fast |
如果只是单线程场景，直接使用HashMap；如果短代码块需要同步，可使用Collections.synchronizedMap()或ConcurrentHashMap，两者的锁粒度和并发性能不同，后面章节会具体说明。
11. 线程安全方案
多线程写共享 Map 时，不能使用普通 HashMap。常见解决方案有三种：Hashtable、Collections.synchronizedMap()和ConcurrentHashMap。前两者基本是对整个 Map 加锁，读操作也会被串行化；而ConcurrentHashMap在 JDK 8 中采用分段思想、CAS 和桶级 synchronized，大幅提高了并发度。
import java.util.Collections; import java.util.HashMap; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; public class ThreadSafeMapDemo { public static void main(String[] args) { // 方式一：Collections 包装 Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>()); // 方式二：ConcurrentHashMap，推荐 Map<String, Integer> concurrentMap = new ConcurrentHashMap<>(); concurrentMap.put("task", 1); concurrentMap.computeIfAbsent("counter", key -> 0); System.out.println(concurrentMap.get("counter")); } }ConcurrentHashMap不允许 null 键和 null 值，原因是并发环境下 null 容易和二义性结果混淆；它的putIfAbsent()、computeIfAbsent()、merge()等方法也提供了更原子的复合操作。
12. 性能优化实践
- 合理预估初始容量：减少扩容次数，容量保持为 2 的幂。
- 正确实现 hashCode：让哈希值尽量均匀分布，避免大量对象落到同一桶。
- 使用不可变键：String、Integer 等不可变对象是理想的键类型。
- 按需选择遍历方式：遍历键值对优先用
entrySet()，避免多次 get 造成额外哈希计算。 - 批量操作注意原子性：多线程下涉及“判断后写入”的操作优先使用
computeIfAbsent等方法。 - 避免用 HashMap 做顺序容器：需要插入顺序用
LinkedHashMap，需要排序用TreeMap。
13. 完整实战：单词词频统计
下面用一个完整案例收尾：统计一段文本中每个单词出现的次数。这个案例综合使用了getOrDefault()、
