哈希表
哈希表先用哈希值缩小范围，再比较键是否相等。本文负责冲突、负载、扩容和键契约。
1. 面试核心
先记住这几条，再读正文- 查询复杂度。 分布均匀且负载受控时，哈希表查询期望 O(1)。卡 · 复杂度
- 冲突处理。 链地址法保存冲突桶，开放寻址沿探测序列寻找键。
- 开放寻址删除。 线性探测删除需保留探测路径，或重新整理条目。卡 · 开放寻址
- 键的稳定性。 相等键必须有相同哈希值，键字段应在存储期间保持稳定。卡 · 键的相等关系
2. 哈希函数与定位
哈希函数将键转换为整数。容量再参与计算存储位置：
index = compress(hash(key), capacity)
同一个键需要稳定的哈希结果。分布越均匀，桶内比较或探测的次数越少。有限的位置会承载更大的键空间，因此冲突是正常情况。
3. 冲突处理
3.1 链地址法
每个数组位置关联一个桶。冲突条目放在同一桶内，再通过键相等判断区分。
0 → [A]
1 → [B] → [C]
2 → 空
桶可用链表、动态数组或树。链式节点增加链接与对象空间。树化的具体条件属于容器实现，需结合键的比较方式分析。
3.2 开放寻址
所有条目都放在同一个数组内。位置被占用时，沿预定探测序列继续寻找。线性探测每次前进一步，容易形成连续占用区。
假设 A、B 的起始位置相同，B 因冲突放在 A 后面。删除 A 后若直接标空，查询 B 会在原 A 处提前结束。墓碑表示“此处已删除，查询需继续”。另一种方式是重新插入后方受影响的条目。
墓碑也会延长探测路径。扩容或重建时需清理墓碑，并重新定位有效条目。
4. 负载因子与扩容
负载因子为 α=元素数量/槽位数量。链地址法的 α 可以大于 1。开放寻址需保留空位，使探测能够结束。
负载提高会增加冲突或探测长度。扩容后，容量参与的位置计算随之改变。条目需要按新容量重新定位。倍增扩容的累计迁移成本可作摊销分析。
5. 复杂度
哈希分布均匀、负载受控、键操作为常数成本时，查询期望 O(1)。若所有键落入一个线性桶，最坏查询为 O(n)。开放寻址的长探测序列也会产生线性成本。
计算长度 k 的键的哈希，首次扫描需 O(k)。总耗时应包含哈希与相等比较成本。Java 21 HashMap 的遍历成本与容量和元素数之和成正比。
6. 键的相等关系
相等的键必须产生相同的哈希值。哈希值相同的键仍需比较内容。
键入表后，参与哈希或相等判断的字段应保持稳定。若这些字段改变，查询会沿新哈希寻找。条目仍在旧位置，就会发生查找失败。不可变键能避免这类问题。
7. 使用场景
哈希表适合键值查询、去重、计数和分组。哈希映射本身缺少大小顺序。范围查询可用有序树，插入顺序可由额外链表维护。
并发安全与多个操作的原子性还需额外机制。它们属于具体容器与调用协议的保证。
8. 常见问题
8.1 哈希冲突
冲突只表示不同键映射到相同位置。哈希表仍通过相等关系区分条目。稳定性与分布质量共同影响结果和性能。
8.2 范围查询
哈希表按哈希定位，键的大小与槽位顺序无关。查询一个键区间需要扫描条目。有序树可利用键顺序跳过无关范围。
8.3 扩容迁移
新容量改变定位规则，旧条目需要重新分布。迁移可复用缓存的哈希值，具体取决于实现。
9 · 面试题卡片
本页题目与参考回答
9.1 哈希查询为何期望 O(1)，最坏却为 O(n)？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：分布假设、负载与冲突路径。
相关内容：复杂度。
参考回答
均匀分布且负载受控时，期望只需检查常数个候选。
若 n 个键集中在一个线性桶，查询需比较 O(n) 次。键自身的哈希和比较成本还需另算。
9.2 线性探测删除条目为何要保留墓碑或整理条目？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：探测路径与查询终止。
相关内容：开放寻址。
参考回答
直接标空会截断后方冲突键的查找路径。
墓碑让查询继续，重排则恢复从起始位置可达的布局。墓碑积累会增加探测成本，需要重建清理。
9.3 修改已入表键的字段，为何会查找失败？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：哈希值、相等关系与存储位置。
相关内容：键的相等关系。
参考回答
参与哈希的字段改变后，查询会从新位置开始。
条目还在旧位置，因此查找失败。作为键使用期间，应保持哈希与相等字段稳定。