哈希表
哈希表使用哈希函数把键映射到有限的存储位置，用额外空间换取接近常数时间的查询、插入和删除。它只定义通用的数据组织方式；具体语言可能采用链地址法、开放寻址或其他冲突处理策略。
1. 键经过哈希后映射到存储位置
哈希函数先把任意键转换为一个整数，再由表容量决定最终位置：
index = compress(hash(key), capacity)
理想的哈希函数应满足两个条件：
- 同一个键在表未改变时得到稳定结果。
- 常见输入尽量均匀分布，避免大量键集中到少数位置。
哈希值不需要唯一。键空间通常远大于存储位置数量，不同键映射到同一位置是正常现象，哈希表必须继续比较键并处理冲突。
2. 冲突处理决定表内结构
2.1 链地址法
链地址法让每个数组位置指向一个桶，发生冲突的条目保存在同一个桶中：
0 → [A]
1 → [B] → [C]
2 → 空
3 → [D]
桶可以使用链表、动态数组或树。查找时先定位桶，再在桶内确认键是否相等。它的删除逻辑直接，但每个条目通常需要额外的节点或引用空间。
2.2 开放寻址
开放寻址把所有条目直接放在同一个数组里。目标位置被占用时，按照探测序列寻找下一个位置，常见方式包括线性探测、二次探测和双重哈希。
开放寻址拥有较好的内存局部性，但删除不能简单地把位置恢复为空，否则会截断其他键的探测路径。实现通常使用墓碑标记，或在删除后重新整理受影响的条目。
3. 负载因子描述空间使用程度
负载因子通常写作：
α = 元素数量 / 存储位置数量
负载因子提高时，空间利用率上升，冲突和探测长度通常也会增加。不同冲突处理策略可以承受的负载不同，因此不存在适合所有哈希表的统一阈值。
实现一般会在达到阈值后申请更大的存储空间，并把现有条目重新分配到新位置。扩容需要 O(n) 工作，但如果容量按倍数增长，连续插入的平均成本仍可以按摊销方式分析。
4. 复杂度依赖分布假设
在哈希分布良好且负载受控时，查询、插入和删除的期望或平均成本接近 O(1)。最坏情况下，大量键集中到相同位置，操作可能退化到 O(n)；使用平衡树管理冲突桶的实现可以限制一部分退化路径。
复杂度分析还必须包含键本身的成本。计算长字符串的哈希需要读取字符，比较复杂对象也可能超过常数时间。所谓 O(1) 描述的是表内定位步骤，不代表处理任意键的总耗时恒定。
遍历哈希表通常还需要检查内部存储空间，因此成本可能同时受元素数量和表容量影响。哈希表也不天然提供稳定顺序；需要排序、范围查询或确定遍历顺序时，应选择有序结构或额外维护顺序。
5. 键需要稳定的相等关系
哈希表使用哈希缩小候选范围，再用相等关系确认是不是同一个键。两个相等的键必须产生一致的哈希结果，否则它们可能进入不同位置。
键写入后，如果参与哈希或相等判断的内容发生变化，后续查询可能从另一个位置开始，无法找到仍保存在原位置的条目。因此键通常应不可变，或者至少在作为键使用期间保持相关字段不变。
6. 使用场景
哈希表适合：
- 根据唯一键快速查找值。
- 集合成员判断和去重。
- 计数、分组和建立反向索引。
- 缓存中由键定位条目。
以下需求通常需要其他结构或额外机制：
- 按键排序或执行范围查询。
- 按插入、访问或业务顺序遍历。
- 在多个操作之间维护事务性不变量。
- 在不可信输入下仅依赖平均复杂度抵御资源耗尽。
7. 常见问题
7.1 哈希冲突是否说明哈希函数错误
不是。有限位置承载更大的键空间时，冲突无法完全避免。哈希函数的目标是让常见输入分布尽量均匀，哈希表则必须保证冲突发生后仍能正确区分键。
7.2 哈希表为什么不能直接提供范围查询
哈希映射保留的是定位关系，不保留键的大小顺序。查找某个键可以快速定位，但查找某个区间通常只能遍历全部条目。范围查询更适合有序树、跳表等结构。
7.3 扩容为什么需要重新分配条目
存储位置由哈希值和容量共同决定。容量改变后，同一个哈希值可能对应不同位置，所以旧条目不能只原样复制到相同下标，必须按照新容量重新定位或等价地完成迁移。
8. 面试题
8.1 哈希表的查询为什么平均接近 O(1)，最坏却可能是 O(n)
出现公司：暂无公开来源记录
考察重点
- 哈希定位、冲突处理与负载因子。
- 平均情况依赖的分布假设。
- 桶内结构如何影响退化路径。
相关内容：第 2 节“冲突处理决定表内结构”至第 4 节“复杂度依赖分布假设”。
参考回答
哈希分布均匀且负载受控时，一次操作只需计算哈希、定位一个位置，再检查很少的候选条目，因此平均成本接近 O(1)。如果大量不同键集中到同一个桶或形成很长的探测序列，就需要比较大量候选，最坏可能退化为 O(n)。
实现可以通过改进哈希分布、控制负载因子、扩容，或改变冲突桶结构限制退化概率和成本，但不能把平均复杂度无条件当作最坏复杂度。