哈希表（Hash Table）
定义
哈希表（Hash Table，也称散列表）是一种基于哈希函数实现的数据结构，能够在平均 O(1) 时间内完成插入、删除和查找操作。
核心思想：通过哈希函数将键（key）映射到数组的某个索引位置，直接访问该位置获取数据。
基本原理
键值对 (key, value)
│
▼
哈希函数 hash(key) → 数组索引 index
│
▼
数组 table[index] = value
伪码表示
put(key, value):
index = hash(key)
table[index] = value
get(key):
index = hash(key)
return table[index]
remove(key):
index = hash(key)
table[index] = null
核心组件
1. 哈希函数（Hash Function）
作用：将任意类型的 key 转换为固定范围的非负整数索引。
要求：
- 确定性：相同的 key 必须产生相同的哈希值
- 高效性：计算复杂度必须为 O(1)
- 均匀性：哈希值应尽可能均匀分布，减少冲突
示例（Java）：
int hash(K key) {
int h = key.hashCode(); // 获取对象的哈希码
h = h & 0x7fffffff; // 保证非负（清除符号位）
return h % table.length; // 映射到合法索引
}
2. 哈希冲突（Hash Collision）
定义：不同的 key 经过哈希函数计算后得到相同的索引。
必然性：将无限空间（所有可能的 key）映射到有限空间（数组索引），必然会发生冲突。
3. 冲突解决方法
| 方法 | 别名 | 原理 | 适用场景 |
|---|---|---|---|
| 拉链法 | 链地址法 | 数组每个位置存储链表，冲突元素追加到链表 | 实现简单，负载因子可>1 |
| 开放寻址法 | 线性探查法 | 冲突时往后找空位（index+1, +2, ...） | 缓存友好，负载因子≤1 |
详细内容参见：
4. 负载因子（Load Factor）
定义：负载因子 = 已存储元素数量 / 数组容量
作用：度量哈希表的装满程度，负载因子越大，冲突概率越高。
扩容机制：
- 当负载因子超过阈值（如 Java HashMap 默认 0.75）时，触发扩容
- 扩大数组容量（通常是 2 倍）
- 重新计算所有 key 的索引并搬移数据（rehash）
时间复杂度
| 操作 | 平均情况 | 最坏情况 | 说明 |
|---|---|---|---|
| 查找 | O(1) | O(n) | 最坏情况为所有 key 都冲突 |
| 插入 | O(1) | O(n) | 可能触发扩容（摊销后仍接近 O(1)） |
| 删除 | O(1) | O(n) | 取决于冲突解决方法 |
为什么平均 O(1)：
- 前提是哈希函数 O(1) + 合理解决哈希冲突 + 适当的负载因子管理
- 若哈希函数慢或冲突严重未扩容，复杂度会退化
重要注意事项
1. 遍历顺序不确定
- 扩容后 key 的索引可能变化
- 不要依赖遍历顺序编程
2. 不能在遍历时增删 key
- 扩缩容导致 table 变化，行为不可预测
- 如需修改，使用迭代器的安全方法
3. key 必须是不可变类型
- 可变类型的
hashCode()会变，导致键值对"丢失" - 修改元素后无法再查到原键值对（"幽灵键值对"）
- 推荐使用：
String、Integer等不可变类型
4. 可变类型作为 key 的严重问题
以 ArrayList 为例：
- 每次计算
hashCode()需遍历所有元素，复杂度 O(N) - 修改元素后
hashCode变化，原键值对无法被查到 - 导致内存泄漏：键值对被 table 引用但无法访问
常见实现
| 实现 | 底层结构 | 特点 |
|---|---|---|
| Java HashMap | 数组 + 链表/红黑树 | 负载因子 0.75，链表>8 转树 |
| Java LinkedHashMap | 哈希表 + 双向链表 | 保持插入顺序，见 哈希链表 |
| Java Hashtable | 数组 + 链表 | 线程安全（方法加锁），已过时 |
| C++ std::unordered_map | 通常为链地址法 | 平均 O(1)，最坏 O(n) |
| Python dict | 开放寻址变体 | 高效，自动扩容 |
保持顺序的变种
- LinkedHashMap（Java）：哈希表 + 双向链表，按插入顺序遍历
- 有序哈希表：部分语言提供，可按插入顺序或访问顺序遍历
与 Map 接口的关系
- Map 是接口：仅声明操作方法（get/put/remove），未指定实现方式
- HashMap 是 Map 的一种实现：底层使用哈希表
- 其他实现：
TreeMap：红黑树实现，O(logN)LinkedHashMap：保持插入顺序
⚠️ 不能假设所有键值对操作都是 O(1)，需看具体实现的数据结构