哈希表与哈希集 (HashMaps & HashSets)

为什么哈希表很重要

哈希表（HashMap）提供了平均 $O(1)$ 的查找复杂度——这使其成为后端系统中使用最广泛的数据结构：

• 缓存：Redis、Memcached 利用哈希表实现极速的键值存储。
• 会话管理：通过 Session ID 快速检索用户信息。
• 数据库索引：哈希索引用于精准匹配查询。
• 计数与去重：词频统计、数据分析、去除重复项。

实际影响：在包含 100 万条记录的哈希表中查找仅需约 50 纳秒，而在线性搜索（数组）中则需约 5 毫秒——速度相差 10 万倍。

---

核心概念

哈希函数 (Hash Function)

将任意长度的键转换为数组索引的数学映射：

int index = Math.abs(key.hashCode()) % array.length;

优秀哈希函数的特质：

• 确定性：相同的键永远映射到相同的索引。
• 均匀分布：将键均匀散布在桶中，减少冲突。
• 计算高效：计算复杂度必须是 $O(1)$。

冲突解决策略

1. 链地址法 (Chaining - Java 的选择)

每个“桶” (Bucket) 实际上是一个链表头，冲突的元素直接追加到链表中。

• Java 优化 (Java 8+)：当链表长度超过 8 时，会自动转化为红黑树，将最差查找效率从 $O(n)$ 提升至 $O(\log n)$。

2. 开放寻址法 (Open Addressing)

所有元素直接存在数组中。若发生冲突，则寻找下一个空位：

• 线性探测：index, index+1, index+2...。
• 平方探测：index, index+1², index+2²...。

---

深入理解

负载因子与扩容 (Load Factor & Resizing)

• 阈值：Java 默认负载因子为 0.75。
• 逻辑：当 元素数 > 容量 * 0.75 时，触发扩容。
• 过程：创建一个 2 倍大小的新数组，并将所有旧元素重新哈希 (Rehash) 到新桶位。

HashMap vs TreeMap vs LinkedHashMap

特性	HashMap	TreeMap	LinkedHashMap
排序	无序	按键排序	插入顺序
底层实现	哈希表 + 链表/红黑树	红黑树 (自平衡)	哈希表 + 双向链表
查找性能	$O(1)$	$O(\log n)$	$O(1)$
Null 支持	允许一个 null 键	不允许 null 键	允许一个 null 键

---

常见陷阱与规避

1. 使用可变对象作为键：若键对象在存入后被修改导致 hashCode 变化，你将再也找不回这个值。
   • 对策：永远使用 String 或自定义的不可变 (final) 类作为键。
2. 重写 equals 却忘了 hashCode：这会导致逻辑相等的对象散布在不同的桶中，违背哈希表的基本语义。
   • 对策：始终成对重写。
3. 迭代时修改：直接在 for-each 循环中 put 或 remove 会触发 ConcurrentModificationException。
   • 对策：使用 ConcurrentHashMap 或通过 Iterator.remove() 操作。

---

面试高频题

Q1: 两数之和 (简单)

思路：利用 HashMap 存储 (值, 索引)。遍历数组时，查找 target - nums[i] 是否已在 Map 中，从而将 O(n²) 优化为 O(n)。

Q2: 前 K 个高频元素 (中等)

思路：先用 HashMap 统计频率，再配合最小堆或桶排序获取前 K 名。

Q3: 实现 LRU 缓存 (中等)

思路：典型的“哈希表 + 双向链表”组合。哈希表提供 $O(1)$ 查找，双向链表维护访问顺序。Java 中可以直接继承 LinkedHashMap 并重写 removeEldestEntry 方法实现。

---

延伸阅读

• 红黑树原理：理解 TreeMap 与树化 (Treeify) 的核心。
• 并发安全：深入研究 ConcurrentHashMap 的分段锁与 CAS 机制。
• 哈希攻击：了解精心构造的冲突键如何导致 CPU 飙升。
• LeetCode：哈希表标签题目 stone