拓冰网站定制 
1. 什么是哈希表哈希表Hash Table是一种通过“键值对”形式存储数据的结构核心思想是把键映射到一个内部数组的下标从而实现接近 O(1) 的平均查找、插入和删除效率。Java 中最常用的实现就是HashMap它是基于哈希表原理设计的集合类。哈希表解决的核心问题是当数据量很大时如何不用逐个比较就能快速定位元素。它借助散列函数把任意键转换为整数索引例如把字符串name映射到数组的第几个位置然后直接访问该位置。小结哈希表 数组 散列函数 冲突处理机制。数组负责快速定位散列函数决定存放位置冲突处理保证不同键映射到同一位置时也能正常工作。2. 为什么需要哈希表对比常见的线性结构哈希表的优势非常明显。顺序表和链表需要遍历比较LinkedList 查找平均时间复杂度为 O(n)而 HashMap 理想情况下查找为 O(1)。当应用需要频繁通过某个唯一标识查询数据时例如根据用户 ID 查用户、根据商品编码查库存哈希表是更合适的选择。不过在追求速度的同时哈希表也带来了一些代价它会占用更多内存、无法保证遍历顺序HashMap不保证顺序、键对象需要正确实现hashCode()和equals()方法。结构查找平均复杂度是否有序典型场景ArrayListO(n)按下标有序顺序访问、随机下标访问LinkedListO(n)按插入顺序频繁插入删除HashMapO(1)不保证顺序按键快速查找TreeMapO(log n)按键自然排序需要范围查询或排序3. Java 哈希表家族Java 中与哈希表相关的类主要有Hashtable、HashMap、LinkedHashMap和ConcurrentHashMap。日常开发优先推荐HashMap需要线程安全时优先考虑ConcurrentHashMap而不是老旧的Hashtable。HashtableJDK 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 MapString, 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.EntryString, 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) { MapPerson, 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 底层是一个NodeK,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) { MapString, 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 对比对比项HashMapHashtable出现版本JDK 1.2JDK 1.0线程安全否是但锁粒度大null 键和 null 值允许不允许会抛 NullPointerException性能较高较差迭代器fail-fastEnumerator部分方法也支持 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 包装 MapString, Integer synchronizedMap Collections.synchronizedMap(new HashMap()); // 方式二ConcurrentHashMap推荐 MapString, 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()、 Java 哈希表完全教程：从 HashMap 原理到源码实战
1. 什么是哈希表哈希表Hash Table是一种通过“键值对”形式存储数据的结构核心思想是把键映射到一个内部数组的下标从而实现接近 O(1) 的平均查找、插入和删除效率。Java 中最常用的实现就是HashMap它是基于哈希表原理设计的集合类。哈希表解决的核心问题是当数据量很大时如何不用逐个比较就能快速定位元素。它借助散列函数把任意键转换为整数索引例如把字符串name映射到数组的第几个位置然后直接访问该位置。小结哈希表 数组 散列函数 冲突处理机制。数组负责快速定位散列函数决定存放位置冲突处理保证不同键映射到同一位置时也能正常工作。2. 为什么需要哈希表对比常见的线性结构哈希表的优势非常明显。顺序表和链表需要遍历比较LinkedList 查找平均时间复杂度为 O(n)而 HashMap 理想情况下查找为 O(1)。当应用需要频繁通过某个唯一标识查询数据时例如根据用户 ID 查用户、根据商品编码查库存哈希表是更合适的选择。不过在追求速度的同时哈希表也带来了一些代价它会占用更多内存、无法保证遍历顺序HashMap不保证顺序、键对象需要正确实现hashCode()和equals()方法。结构查找平均复杂度是否有序典型场景ArrayListO(n)按下标有序顺序访问、随机下标访问LinkedListO(n)按插入顺序频繁插入删除HashMapO(1)不保证顺序按键快速查找TreeMapO(log n)按键自然排序需要范围查询或排序3. Java 哈希表家族Java 中与哈希表相关的类主要有Hashtable、HashMap、LinkedHashMap和ConcurrentHashMap。日常开发优先推荐HashMap需要线程安全时优先考虑ConcurrentHashMap而不是老旧的Hashtable。HashtableJDK 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 MapString, 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.EntryString, 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) { MapPerson, 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 底层是一个NodeK,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) { MapString, 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 对比对比项HashMapHashtable出现版本JDK 1.2JDK 1.0线程安全否是但锁粒度大null 键和 null 值允许不允许会抛 NullPointerException性能较高较差迭代器fail-fastEnumerator部分方法也支持 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 包装 MapString, Integer synchronizedMap Collections.synchronizedMap(new HashMap()); // 方式二ConcurrentHashMap推荐 MapString, 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()、