哈希表查找（Hash Table Search）

哈希表通过哈希函数将关键字映射到表中的位置，实现在接近 O(1) 的时间内完成查找。其核心挑战在于：如何设计好的哈希函数以减少冲突，以及如何高效处理已发生的冲突。

哈希函数

哈希函数 h(key) 将关键字映射到表中的槽位下标（0 到 m-1）。好的哈希函数应满足：

• 均匀性：将关键字均匀分布到各槽位，减少冲突。
• 确定性：相同关键字始终映射到相同位置。
• 高效性：计算速度快。

构造方法	公式	特点
直接定址法	h(key) = a × key + b	无冲突，但需要连续地址空间
除留余数法	h(key) = key % m（m 取质数）	最常用，m 取质数效果好
乘法散列	h(key) = ⌊m × frac(key × A)⌋	对 m 不敏感，A ≈ 0.618

冲突处理

当两个不同关键字映射到同一槽位时，发生哈希冲突。常见的冲突处理方式分为两大类：

插入与查找过程模拟

以表长 11、哈希函数 h(key) = key % 11、线性探测为例，演示插入和查找流程：

步骤图：初始状态，哈希表为空（11 个槽位）

1/4

常见冲突处理策略对比

策略	方法	优点	缺点
线性探测	h(key) + 1, +2, +3, …	实现简单，缓存友好	容易产生"堆积"（primary clustering）
二次探测	h(key) + 1², -1², +2², -2², …	减少堆积	不能保证探测到所有槽位
拉链法	每个槽位维护链表	无需预估数据量，删除简单	额外空间，链表不缓存友好

装填因子（Load Factor）

装填因子 α = 已存关键字数 / 哈希表总槽位数，直接影响查找效率：

• α 越小，冲突越少，查找越快，但空间利用率低。
• α 越大，冲突越多，查找退化。开放地址法一般要求 α ≤ 0.75。
• 拉链法对 α > 1 也能工作，但链表过长影响性能。

平均查找长度 ASL 与装填因子密切相关：

• 线性探测（查找成功）：ASL ≈ ½ × (1 + 1/(1-α))
• 线性探测（查找失败）：ASL ≈ ½ × (1 + 1/(1-α)²)

算法特性

• 时间复杂度：期望 O(1)。在装填因子较低时，查找、插入、删除均接近常数时间。
• 最坏情况：O(n)。所有关键字均哈希到同一槽位时退化。
• 空间复杂度：O(n)。需要额外的哈希表数组及（拉链法中的）链表空间。
• 不支持有序遍历：哈希表本身无序，无法高效执行范围查询。

Baseline 任务：哈希表

任务一：实现哈希函数

完成 hash_table.cpp 中的哈希函数构造：

• DirectHash：直接定址法
• ModHash：除留余数法，表长取质数
• MultiplicationHash：乘法散列

任务二：实现冲突处理

在哈希表基础上实现三种冲突处理策略：

• 线性探测（开放地址）
• 二次探测（开放地址）
• 拉链法（链式存储）

任务三：实现哈希表操作

支持完整的 CRUD 操作：

• 插入 Insert(key)：计算哈希值并处理冲突后存入
• 查找 Search(key)：从哈希位置开始探测，记录命中位置与探测次数
• 删除 Delete(key)：注意开放地址法删除后的标记处理
• 统计装填因子、平均查找长度（ASL）

文件结构

• hash_table.h：接口声明
• hash_table.cpp：哈希表核心实现
• test.cpp：测试程序

验证方式

• 编译：g++ -std=c++17 test.cpp hash_table.cpp -o testHashTable
• 运行：./testHashTable