哈希表

哈希表把大键空间映射为一个可快速计算的“近似地址”，直接跳到键可能所在的有限桶数组，再在碰撞结构中做少量局部工作。期望效率来自“键分布经哈希后近似均匀”，而非数组访问本身神奇地消除搜索。碰撞不可避免，必须由链式、开放寻址等策略解析；负载因子控制每桶竞争和探测长度。哈希值相同只表示候选桶相同，最终仍需比较键以确认相等。

链地址把同槽键放入链表或小容器；开放寻址把所有键留在数组并按探测序列寻找空槽。删除开放寻址元素常需墓碑，否则会截断后续查找路径。扩容并重新哈希可保持负载因子，但单次扩容为线性成本，通常靠摊还分析得到长期常数。密码学哈希强调抗碰撞/抗攻击，普通算法哈希只需分布和速度，目标不同。

容量 $8$、哈希 $h(k)=kmod8$ 时，键 $3,11,19$ 全落入桶 $3$。链式法把它们放在同一链中；线性探测则依次寻找空槽。扩容到更大表后通常需重新哈希，因为桶索引依赖容量。

最坏情况下所有键碰撞，操作退化为 $O(n)$；“平均 $O(1)$”需要随机哈希、独立性或输入假设。删除开放寻址元素不能简单置空，否则会截断后续探测链，通常使用 tombstone 或后移修复。

数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。提供桶，哈希函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。提供定位，二者共同实现字典、映射与集合 ADT公理库字典、映射与集合 ADTDictionary ADT · Map ADT · Set ADT以有限偏函数统一刻画按键查询、更新和删除的字典、映射与集合接口。。面对预先固定的最坏键集，通用哈希公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。把随机性放在选函数上；静态集合可进一步用完美哈希公理库完美哈希Perfect hashing · FKS hashing对预先固定的静态键集消除查询碰撞，并以两层随机构造取得线性空间和最坏常数查询。把碰撞消除。若只需节省空间的近似成员查询，Bloom Filter公理库Bloom FilterBloom filter用多个哈希位置共享位数组实现无假阴性的插入式近似成员查询，并允许可控假阳性。允许假阳性，但它不存储值，也不是哈希表的冲突处理方式。

这些结构的保证属于不同概率空间与更新模型。哈希表页只承担冲突解决、负载因子和期望复杂度框架；密码哈希的计算抗碰撞、完美哈希的静态构建以及 Bloom Filter 的误报率分别由专页定义，不能以“平均 $O(1)$”互相替代。

哈希表主体只承诺字典语义与负载参数，冲突策略应分层阅读：通用哈希公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。给对固定键集的碰撞期望，Perfect Hashing公理库完美哈希Perfect hashing · FKS hashing对预先固定的静态键集消除查询碰撞，并以两层随机构造取得线性空间和最坏常数查询。针对静态集合换最坏常数查询，开放定址公理库开放定址哈希open addressing · closed hashing把所有键直接存入表数组，并沿键相关探测序列处理冲突的哈希模型。把键直接放入数组并依探测链，Cuckoo Hashing公理库Cuckoo Hashingcuckoo hashing · 布谷鸟哈希为每个键提供两个候选槽，以踢出链和必要的重哈希换取常数最坏查找。用两个候选位置和重哈希。Bloom Filter公理库Bloom FilterBloom filter用多个哈希位置共享位数组实现无假阴性的插入式近似成员查询，并允许可控假阳性。允许假阳性，已不再实现精确字典；不能把其节省空间与哈希表查询并列成同一保证。