什么是哈希表？为什么它能做到平均 O(1) 的增删查？
简化版
哈希表用一个数组存数据，靠哈希函数把「键」直接算成数组下标：存的时候算一次下标放进去，查的时候再算一次下标直接取。因为「键 → 下标」是一步计算而不是逐个比较，所以增删查的平均时间复杂度是 O(1)。代价是需要处理不同键算到同一下标的「哈希冲突」。
详细版
哈希表（Hash Table，也叫散列表）的核心是三样东西：
- 一个底层数组（桶数组 buckets）：真正存放数据的地方。
- 一个哈希函数：
index = hash(key) % capacity，把任意类型的键映射成数组下标。 - 一套冲突解决机制：不同的键可能算出同一个下标，得有办法把它们都放下（拉链法 / 开放寻址法）。
一次 put(key, value)：算出下标 → 放到对应桶。一次 get(key)：算出同一个下标 → 从桶里取。因为下标是算出来的，不用像数组/链表那样从头找，所以平均 O(1)。
注意「平均」二字：一旦冲突严重、大量键挤在一个桶里，退化成在桶里线性查找，最坏会变 O(n)。好的哈希函数 + 及时扩容就是为了避免这种退化。
完整版教学
一、为什么普通数组做不到「按内容快速找」
数组按下标访问是 O(1)，但如果你想按内容找（「值为 5 的元素在哪」），只能从头遍历，O(n)。哈希表的巧妙之处在于：它把「你关心的键」直接变成「数组下标」，于是「按内容找」也变成了「按下标取」，一步到位。
举例：要记录一批单词出现次数。用哈希表，count["apple"]++ 直接定位到 “apple” 对应的桶，不用扫整个表。
二、哈希函数：把键「压」成下标
哈希函数干两件事：
- 把任意键映射成一个整数（哈希值），比如字符串按字符编码算、对象按字段算。
- 把这个大整数收缩到数组范围内，通常
hash % capacity（或hash & (capacity-1)，当容量是 2 的幂时）。
关键要求是尽量均匀：让不同的键尽量散布到不同下标，减少冲突。均匀性差，元素扎堆，性能就退化。
三、冲突不可避免，所以必须有解决机制
键的空间通常远大于数组容量（无穷多字符串 vs 有限个桶），由鸽巢原理，冲突必然发生。两大主流解法：
- 拉链法：每个桶挂一条链表（或红黑树），冲突的元素都串在同一个桶后面。
- 开放寻址法：冲突了就按规则往后找下一个空位。
无论哪种，查找都先定位桶，再在桶内做少量比较。只要冲突控制得好、每个桶里元素很少，比较次数近似常数，整体就是平均 O(1)。
四、复杂度到底是多少
| 情况 | 增 / 删 / 查 |
|---|---|
| 平均（哈希均匀、负载合理） | O(1) |
| 最坏（大量冲突扎堆一个桶） | O(n)，链表退化；Java 8+ 桶内转红黑树后为 O(log n) |
所以哈希表是「平均 O(1)、最坏更慢」的结构——它靠好的哈希函数和扩容来让平均情况成为常态。
五、和其他结构的定位对比
- 要按键快速存取、不关心顺序 → 哈希表（
HashMap）。 - 要有序、能范围查询 → 平衡树 / 跳表（
TreeMap），查为 O(log n) 但有序。 - 哈希表不保证遍历顺序，这是它换来 O(1) 的代价。
六、常见误区与追问
| 操作 | 平均复杂度 | 退化情况 |
|---|---|---|
| put | O(1) | 冲突严重或扩容时变慢 |
| get | O(1) | 桶内链表很长时退化 |
| remove | O(1) | 需要在桶内查找目标 |
| rehash | O(n) | 扩容时批量迁移 |
key -> hash(key) -> index -> bucket -> compare key -> value记忆钩子：哈希表快，不是因为不用比较，而是先用哈希把候选范围缩到一个桶，再在桶内做少量比较。
数字例子：有 10000 个 key，容量 16384，分布均匀时每个桶平均不到 1 个元素，get 通常只检查很少节点。若哈希函数很差，让 10000 个 key 都落到同一桶，查找就接近在链表里顺序找，复杂度会退化到 O(n)。
- 误区：哈希表查找永远是 O(1)。 O(1) 是平均情况，依赖哈希均匀、负载合理和冲突可控。
- 误区：哈希表不需要比较 key。 哈希定位桶后还要比较真实 key，避免哈希碰撞导致误取。
- 误区：数组下标就是 key 本身。 key 会先经过哈希函数转换成整数，再映射到数组下标。
- 追问：为什么需要扩容？ 元素太多会提高负载因子，冲突增多，扩容能降低每个桶的平均压力。
- 追问：哈希表和有序树怎么选？ 只要快速点查用哈希表；需要有序遍历、范围查询、前驱后继时用平衡树。
- 追问：删除为什么也要定位桶？ 删除前必须先找到 key 所在桶和桶内节点，再调整链表、标记或数组槽位。
七、加强记忆
哈希表 = 数组 + 哈希函数 + 冲突处理。它把「键」直接算成「下标」，所以增删查平均 O(1)；冲突不可避免（鸽巢原理），靠拉链法/开放寻址法兜底。哈希函数越均匀、负载因子控制越好，越接近理想的 O(1)；扎堆严重时会退化到 O(n)。