哈希表

哈希表（Hash Table）用哈希函数把 key 映射到有限个桶或槽位，目标是以接近 O(1) 的期望时间完成按 key 查找、插入和删除。它适合“按精确 key 查找”，不维护键的全局顺序，因此不适合范围查询、前驱或后继查询。

hash(key) → hash value → index = hash value % bucket_count

正确性契约与基本操作

哈希函数不需要做到“一键一值”，但必须满足：若 equal(a, b) 为真，则 hash(a) == hash(b) 必须为真。反过来，哈希值相同不代表 key 相等；落到同一位置后仍要用相等比较确认。

查找、插入和删除的共同起点都是计算 key 的桶下标，再在该桶或探测序列中寻找 key。哈希质量决定平均性能：键分布均匀时，操作期望为 O(1)；大量键集中到少数位置时，最坏可退化为 O(n)。

操作	平均 / 期望	最坏	说明
查找	O(1)	O(n)	冲突集中时需扫描长链或长探测序列
插入 / 更新	O(1)（摊还）	O(n)	扩容 rehash 单次为 O(n)
删除	O(1)	O(n)	开放寻址还要维护墓碑
范围查询、前驱后继	不适合	—	使用平衡搜索树更合适

冲突处理

冲突不可完全避免：桶数量有限，且不同 key 可能得到相同哈希值。常见处理分为拉链法和开放寻址法。

拉链法（separate chaining）

每个桶关联链表、节点序列或小型容器；冲突元素保存在同一桶中：

bucket[3] → (key=A, value=...) → (key=B, value=...) → nullptr

• 查找：定位桶并遍历桶内元素；
• 插入：桶内存在同键则更新，否则挂入一个新节点；
• 删除：只从对应桶摘除节点，不影响其他桶。

设装载因子 α = size / bucket_count。若哈希均匀，桶长期望长度为 α，操作期望复杂度为 O(1 + α)。拉链法允许 α > 1，删除直接；代价是节点指针、单独分配和较差的缓存局部性。

开放寻址法（open addressing）

所有元素都直接存入桶数组的槽位中。发生冲突后，沿探测序列继续寻找：

slot(i) = (hash(key) + probe(i)) % bucket_count,  i = 0, 1, 2, ...

• 线性探测：probe(i) = i，实现简单、局部性好，但连续已占槽会形成主聚集；
• 二次探测：例如 probe(i) = i²，可缓解主聚集，但同一初始哈希值仍会走同一序列；
• 双重哈希：probe(i) = i × hash2(key)，第二步长应非零且与桶数互素，分布通常更好。

槽位至少需区分 empty、occupied 和 deleted（墓碑）。删除不能简单置为 empty：这会让查找过早停止，漏掉该槽位之后的冲突元素。墓碑过多会拉长探测，通常要在扩容或专门 rehash 时清理。

开放寻址没有节点指针，通常缓存友好；但装载因子接近 1 时探测长度会急剧上升，需要预留更多空槽，删除和扩容也更复杂。

维度	拉链法	开放寻址法
冲突后位置	同一桶的链 / 小容器	同数组中的后续探测槽位
删除	摘除节点即可	墓碑或重排 / rehash
高装载因子	可工作，但链变长	性能明显下降，不能接近满表
缓存局部性	节点分散时较差	通常较好
额外内存	节点和链接开销	槽位状态与空槽余量

装载因子、扩容与工程选择

装载因子过高会增加冲突。扩容时创建更多桶，并按新桶数重新计算位置，这个过程称为 rehash，单次 O(n)，但不在每次插入中发生，所以插入通常是摊还 O(1)。已知元素数量时应预留容量，减少中途 rehash。

• 需要精确 key 查找且不要求顺序：哈希表；
• 需要范围查询、按序遍历或最坏 O(log n) 保证：平衡二叉搜索树与红黑树；
• 需要同时按 key O(1) 查找和维护访问顺序：LRU 缓存。

不可信外部 key 可能构造大量碰撞。延迟敏感服务应使用高质量、可随机化的哈希或限制输入；不要假设任意平台的默认哈希都具备抗碰撞攻击保证。

C++ 使用边界

std::unordered_map / std::unordered_set 是标准库哈希容器。标准不规定其具体桶节点或探测实现；实际编程应依赖接口和复杂度保证，而不是依赖内部布局。

std::unordered_map<std::string, int> counts;
counts.reserve(expected_count);
counts.max_load_factor(0.7F); // 更少冲突，更多桶和内存

自定义 key 时，所有参与相等比较的字段都必须参与哈希。rehash 会使 unordered_map 的迭代器失效。容器 API、迭代器和自定义 hash 的细节见 STL 容器。

关联笔记

• LRU 缓存
• 平衡二叉搜索树与红黑树
• STL 容器：unordered_map 的接口与使用