哈希表

哈希表先把搜索范围缩到一个桶，再用键相等判断识别真正目标。数组访问解决的是“去哪一桶”，碰撞策略解决的是“桶里不止一项怎么办”。期望常数时间来自负载和随机性条件，两者都不是使用数组后自动获得的性质。

这也解释为何哈希表通常不提供键的排序次序。两个相近键可能进入很远的槽，两个无关键也可能碰撞；桶下标不是业务上的大小关系。需要前驱、后继或范围查询时，应比较有序搜索结构的接口。

同一组碰撞，不同处理方法 ​

取容量 $8$、$h(k)=kmod8$，键 $3,11,19$ 都映到槽 $3$。链地址法将三项保存在同一桶；线性探测可以把它们放进槽 $3,4,5$。查询 $19$ 时，前者沿桶内记录比较，后者按探测序列依次检查。

若在线性探测中删除槽 $4$ 的 $11$ 后直接把该槽标为“从未使用”，查询 $19$ 会过早停止。墓碑或与探测规则相配套的后移修复可以保留查找依据。链地址删除则通过改接桶内结构处理，不需沿用同一停止规则。

期望界怎样得到 ​

对固定查询键 $x$，令 $I_y$ 表示另一个已存键 $y$ 与它碰撞。通用哈希理路通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。给出

再加定位桶和检查目标的常数工作，就得到链地址法的 $O(1+\alpha )$ 期望界。线性期望不要求各碰撞事件相互独立；但键集若在看到种子后被对手自适应选择，就不再是这段固定键集论证。

开放定址的探测长度依赖整个探测序列，不能仅凭首页碰撞概率沿用上述证明。装载率接近 $1$、墓碑累积、哈希求值昂贵，都可能让操作变慢。

扩容、重哈希与字典语义 ​

扩容后桶下标通常改变，必须把有效键重新放置。对链地址表，若保持常数负载、采用几何容量变化及分离的扩缩阈值，并能在线性时间内搬迁记录，摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。把偶发重建分散到一串更新上；普通按键查找的随机成本仍需另计，合起来常得到期望摊还常数更新。某次重建依然可能是线性的。

跨服务器选择负责位置时，一致性哈希环理路一致性哈希环Consistent hashing · Consistent hash ring · 一致性散列用固定环坐标的顺时针后继选择负责节点，证明成员增删的局部迁移，复算虚拟节点、随机期望与热点边界。固定token边界，使加入只切分一段、删除只移交原负责段；Rendezvous哈希理路Rendezvous哈希放置Rendezvous hashing · Highest random weight hashing · HRW hashing按键与稳定节点身份评分形成全序，在成员变化中保持幸存节点相对顺序，并区分概率份额、容量权重和复制资格。则为每把键给节点稳定排名，成员变化不改变幸存节点之间的相对次序。两者解决跨节点放置，不替代本页的节点内碰撞解析，也不证明新目标已经收到数据。

页式动态哈希可避免每次增长都搬整张记录表：可扩展哈希理路可扩展哈希目录与局部分裂Extendible hashing · Extensible hashing用全局和局部深度追踪目录别名、逐位分裂与同伴合并，区分目录翻倍、物理桶数和完整哈希碰撞。用目录别名及局部深度拆热点桶，目录翻倍的指针复制仍需单独计费；线性哈希理路线性哈希：分裂指针与溢出链Linear hashing · Linear virtual hashing用阶段基数和分裂指针计算桶地址，逐次搬迁一个桶并追踪尚未消失的溢出链。按固定分裂指针逐桶扩展，但发生溢出的桶可能暂时继续保留长链。两者维持精确字典语义，不因此获得与分布无关的最坏常数访问。

哈希表、搜索树和 trie 可以在不同键域条件下实现字典、映射与集合 ADT理路字典、映射与集合 ADTDictionary ADT · Map ADT · Set ADT以有限偏函数统一刻画按键查询、更新和删除的字典、映射与集合接口。。选择结构时，应先固定精确查询、覆盖更新、删除和迭代契约，再分别比较最坏、期望与摊还成本。

开放定址理路开放定址哈希open addressing · closed hashing把键直接存放在表数组槽位中的哈希表示；经典探测序列法与允许重定位的变体使用不同的查找不变量。把记录放在表槽内；Cuckoo Hashing理路Cuckoo Hashingcuckoo hashing · 布谷鸟哈希为每个键提供两个候选槽，以踢出链和必要的重哈希换取常数最坏查找。再限制每键的候选位置，并允许插入时搬走旧键；完美哈希理路完美哈希Perfect hashing · FKS hashing对预先固定的静态键集消除查询碰撞，并以两层随机构造取得线性空间和最坏常数查询。则针对静态集合构造无冲突的查询表示。它们使用不同的冲突约束和构造保证。

Bloom Filter理路Bloom FilterBloom filter用多个哈希位置共享位数组实现无假阴性的插入式近似成员查询，并允许可控假阳性。只提供可能带假阳性的成员测试，不保存值，也不实现这里的精确字典。密码学哈希的抗碰撞目标同样不同于桶分布和查询时间，不能把这些保证统称为“哈希性能”。

配套实验 ​

字典契约实验把同一条含碰撞、更新和删除的历史交给链地址表与线性探测表，逐步比较抽象映射，并分别记录键比较、探测和重建工作。其固定取模哈希用于复算正确性，不是上述随机期望界的性能实验。