哈希表基础
核心要点
1. 哈希表 vs Map
- Map 是接口，仅声明操作方法（get/put/remove），未指定实现方式
- HashMap 是 Map 的一种实现，底层使用哈希表，增删查改复杂度 O(1)
- 其他实现如 TreeMap（红黑树，O(logN)）、LinkedHashMap（保持插入顺序）
- 不能假设所有键值对操作都是 O(1)，需看具体实现的数据结构
2. 哈希表基本原理
- 哈希表 = 加强版数组
- 核心机制：通过哈希函数将 key 映射到数组索引，实现 O(1) 访问
- 伪码逻辑：
put(key, value): table[hash(key)] = value get(key): return table[hash(key)] remove(key): table[hash(key)] = null
3. 哈希函数设计
- 作用：将任意类型 key 转化为固定范围的非负整数索引
- 要求：
- 相同 key 必须产生相同哈希值（保证正确性）
- 计算复杂度必须为 O(1)（保证哈希表性能）
- Java 实现示例：
int hash(K key) { int h = key.hashCode(); // 获取对象的哈希码 h = h & 0x7fffffff; // 位运算保证非负（避免取反溢出问题） return h % table.length; // 映射到合法索引 } - 优化：标准库常用位运算替代
%运算提升性能
4. 哈希冲突及解决方法
哈希冲突不可避免：将无限空间映射到有限索引空间，必然发生碰撞。
两种主流解决方法：
| 方法 | 原理 | 特点 |
|---|---|---|
| 拉链法 | 数组每个位置存储链表，冲突元素追加到链表 | 实现简单，负载因子可>1 |
| 线性探查法（开放寻址） | 冲突时往后找空位（index+1, +2, ...） | 缓存友好，负载因子≤1 |
5. 负载因子与扩容
- 负载因子 = size / table.length（已存键值对数 / 数组容量）
- 作用：度量哈希表的装满程度，越大则冲突概率越高
- 默认值：Java HashMap 默认 0.75（经验值）
- 扩容机制：达到负载因子时，扩大 table 数组容量，重新计算所有 key 的索引并搬移数据
- 影响：扩容过程耗时，但保证长期性能
6. 重要注意事项
| 问题 | 原因 | 建议 |
|---|---|---|
| 遍历顺序不确定 | 扩容后 key 的索引可能变化 | 不依赖遍历顺序编程 |
| 不能在 for 循环中增删 key | 扩缩容导致 table 变化，行为不可预测 | 避免遍历时修改 |
| key 必须是不可变类型 | 可变类型的 hashCode 会变，导致键值对"丢失" | 用 String、Integer 等不可变类型 |
可变类型作为 key 的严重问题（以 ArrayList 为例）：
- 每次计算 hashCode 需遍历所有元素，复杂度 O(N)
- 修改元素后 hashCode 变化，原键值对无法被查到（"幽灵键值对"）
- 导致内存泄漏：键值对被 table 引用但无法访问
7. 为什么哈希表操作是 O(1)
- 前提是：哈希函数 O(1) + 合理解决哈希冲突
- 若哈希函数慢（如用可变类型作 key）或冲突严重未扩容，复杂度会退化
相关概念
相关实体
- labuladong：算法学习平台作者