哈希表：O(1) 查找的原理
哈希表的核心思想
哈希表 = 数组 + 哈希函数。
key = "apple"
↓
哈希函数
↓
index = hash("apple") & (capacity - 1)
↓
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑
bucket[3] 存储 ("apple", 1)核心思想：用哈希函数把 key「翻译」成数组索引，直接定位。
哈希函数
理想哈希函数
java
index = hash(key) & (capacity - 1)
// 等价于 hash(key) % capacity好的哈希函数：
- 确定性：相同 key → 相同 index
- 均匀分布：不同 key 尽量 → 不同 index
- 高效性：计算成本低
HashMap 的哈希函数
java
static final int hash(Object key) {
int h;
// 混合高低位，减少冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}冲突解决
链地址法（Chaining）
同一个桶有多个元素，用链表串联：
bucket[3]: [Node("world")] → [Node("apple")] → null
↓
冲突了！用链表连接链表 → 红黑树
链表过长（≥ 8）时转为红黑树（JDK 1.8+）：
bucket[3] 链表（≤ 8）：
[Node] → [Node] → [Node] → ...
bucket[3] 红黑树（> 8）：
TreeNode
/ \
TreeNode TreeNode扩容（Rehashing）
容量不足时扩容：
初始：容量 16，负载因子 0.75
元素超过 12（16 × 0.75）→ 扩容
扩容：容量翻倍 16 → 32
所有元素重新分配到新桶
扩容成本：O(n)
需要遍历所有元素重新计算位置这就是为什么预分配容量可以提升性能。
开放地址法（Open Addressing）
链地址法之外，还有另一种方案：找下一个空桶。
线性探测：依次找下一个空桶
hash(key) = 3，3 被占 → 4，4 被占 → 5 ...
二次探测：步长是二次方
hash(key) + 1², hash(key) + 2², hash(key) + 3² ...
双重哈希：用第二个哈希函数计算步长Java 的 HashMap 用的是链地址法，不是开放地址法。
总结
| 要点 | 说明 |
|---|---|
| 核心思想 | 哈希函数 + 数组 |
| 冲突解决 | 链地址法（链表/红黑树） |
| 扩容触发 | 负载因子 0.75 |
| 时间复杂度 | O(1) 均摊，O(n) 最坏（严重冲突） |