哈希表的核心问题在于高效地将关键字映射到存储位置并妥善处理冲突

哈希表的核心问题在于高效地将关键字映射到存储位置并妥善处理冲突。构造良好的哈希函数能显著减少冲突概率，而合理的冲突处理机制则确保在发生冲突时仍能快速找到可用地址。

一、哈希函数的构造原则

• 压缩性：将大范围的关键字压缩到较小的地址空间（如 0 到 m-1），节省存储空间。
• 散列性：使关键字均匀分布在整个地址空间中，尽可能避免聚集，降低冲突率。

常用构造方法包括：

• 直接定址法：H(key) = key 或 H(key) = a×key + b，适合关键字分布连续的情况。
• 数字分析法：选取关键字中变化较多的数位作为地址，常用于已知关键字分布特征的场景。
• 平方取中法：取关键字平方后的中间几位，适用于关键字长度波动较大的情况。
• 折叠法：将关键字分割为几部分后叠加（移位或边界折叠），适合长数字关键字。
• 随机数法：H(key) = random(key)，用于关键字长度不一的通用场景。
• 除留余数法：H(key) = key % p（p ≤ m 且 p 为质数），最常用的方法之一，简单有效。

二、冲突处理方法——开放定址法
当不同关键字通过哈希函数映射到同一地址时，需使用某种策略探测下一个空闲位置。通用公式为：
Hi=(H(key)+di)mod m H_i = (H(key) + d_i) \mod mHi​=(H(key)+di​)modm
其中 $ H(key) $ 是初始哈希地址，$ m $ 是哈希表长度，$ d_i $ 是第 $ i $ 次探测的增量序列。

常见增量策略有：

1. 线性探测再散列（Linear Probing）
   $ d_i = 1, 2, 3, …, m-1 $
   优点：实现简单；缺点：容易产生“一次聚集”（连续占用块），影响性能。

2. 二次探测再散列（Quadratic Probing）
   $ d_i = 1^2, -1^2, 2^2, -2^2, …, \pm k^2 $，且 $ k \leq m/2 $
   优点：缓解线性聚集；缺点：可能无法覆盖所有地址（尤其当 $ m $ 非质数或非形如 $ 4k+3 $ 时）。

3. 伪随机探测再散列（Random Probing）
   $ d_i $ 来自伪随机数序列，需预先设定种子保证可重现。
   优点：分布更均匀；缺点：需额外维护随机序列生成器。

补充说明：
除了开放定址法，还有链地址法（拉链法）等其他冲突解决方式，它将冲突元素链接成链表，避免了探测过程，在实际应用中（如 Java 的 HashMap）更为常见。
在除留余数法中，哈希函数定义为：
H(key)=keymod p H(key) = key \mod pH(key)=keymodp
其中 $ p $ 的选择对散列效果有重要影响。通常选择质数（素数）作为模数 $ p $，主要原因如下：

1.减少冲突，提升分布均匀性

当 $ p $ 为质数时，能最大限度地打破关键字与模数之间的代数规律性。如果 $ p $ 是合数（非质数），而关键字恰好是其因子的倍数，则会导致大量关键字映射到相同的地址，造成严重冲突。

例如：

• 若 $ p = 10 $（合数），关键字为偶数或以 0、5 结尾的数较多时，余数会集中在少数几个值上。
• 而若 $ p = 11 $（质数），则更可能将不同的关键字“打散”到不同余数上，提高散列均匀性。

2.避免周期性模式放大冲突

许多关键字具有某种结构特征（如身份证号、学号等常含固定前缀或递增序列）。若 $ p $ 与这些关键字的变化步长有公因数，就会产生周期性冲突。

举例说明：
假设关键字是连续整数：$ key = a, a+1, a+2, \dots $，若 $ p $ 和增量 $ d $ 不互质，则余数会出现重复周期。
而质数 $ p $ 与大多数整数互质，因此能有效延长周期，使映射更随机。

3.配合表长设计，提升探测效率

在开放定址法中（尤其是二次探测），要求探测序列尽可能遍历整个表空间。若使用二次探测再散列，只有当表长 $ m $ 为质数且满足 $ m \equiv 3 \pmod{4} $ 时，才能保证在最多 $ m $ 次探测内访问所有位置。

因此，在实际实现中，常将哈希表长度 $ m $ 设为质数，并令 $ p = m $，从而兼顾存储效率与探测完整性。

✅总结：
选择质数作为模数 $ p $，是因为它可以：

• 最大程度减少关键字之间的相关性；
• 提高地址分布的均匀性；
• 避免因公共因子引起的系统性冲突；
• 支持更好的探测序列覆盖能力。

这是理论分析和实践经验共同支持的最佳实践之一。