目录
什么是“好”的哈希函数？
直接定址的延伸 —— 除留余数法 (Modulus Method)
打乱内在规律 —— 平方取中法 (Mid-Square Method)
利用所有信息 —— 折叠法 (Folding Method)
核心应用 —— 如何哈希字符串？
完整代码与总结
我们已经探讨了如何构建哈希表以及如何解决冲突，现在让我们回到这个系统的“心脏”——哈希函数 (Hash Function)。它的设计好坏，直接决定了哈希表的性能。
什么是“好”的哈希函数？
我们先从第一性原理出发，思考一下我们对一个“理想”的哈希函数有什么要求。
它的使命是：将一个 Key（可能是整数、字符串等）转化成一个范围在 [0, TableSize-1] 的数组下标 Index。
为了出色地完成这个使命，它必须具备三个核心品质：
1️⃣ 确定性 (Determinism)：这是最基本的要求。对于同一个 Key，无论何时何地调用哈希函数，都必须返回相同的 Index。
如果 hash("Alice") 第一次返回 3，第二次返回 5，那整个系统就崩溃了，因为你再也找不到存进去的数据了。
2️⃣ 高效性 (Efficiency)：哈希函数的计算过程必须非常快。我们之所以用哈希表，就是为了追求 O(1) 的效率。
如果计算 Index 本身就要花费很长时间（比如，比遍历一半数组还慢），那就本末倒置了。
3️⃣ 均匀性 (Uniformity)：这是“好”与“坏”的分水岭。一个好的哈希函数，应该能将不同的 Key 尽可能均匀地映射到哈希表的每一个槽位上。映射越均匀，冲突就越少，性能就越接近理想的 O(1)。
反之，如果函数设计不佳，导致大量 Key 扎堆映射到少数几个位置，就会造成严重的冲突，使哈希表性能退化。
现在，我们带着这三个评判标准，来审视几种经典的哈希函数设计思想。
直接定址的延伸 —— 除留余数法 (Modulus Method)
这是我们之前一直在使用的方法，也是最常用、最基础的一种。
如何将一个任意大小的整数 key，强制转换到 [0, TableSize-1] 这个范围里？
💡最自然的数学工具：取模运算 (%)。key % TableSize 的结果天然就在 0 到 TableSize-1 之间。
品质验证：
确定性：满足。123 % 11 永远等于 2。
高效性：满足。取模是CPU指令级别的运算，极快。
均匀性：有条件地满足。它的均匀性高度依赖于 TableSize 的选择。如果我们之前所说，如果 TableSize 是一个合数（比如 10），而 Key 又存在某种规律（比如都是 10 的倍数），那么所有 Key 都会哈希到 0，造成严重冲突。
因此，TableSize 通常选择为素数，这能大大减少因 Key 的内在规律性而导致的冲突，让分布更均匀。
代码实现：
#include
// 哈希表大小（一个素数）
const int TABLE_SIZE = 11;
// 方法一：除留余数法
int hash_mod(int key) {
// 直接返回 key 对表大小取模的结果
return key % TABLE_SIZE;
}
这个方法是处理整数 Key 的黄金标准和首选基准。
打乱内在规律 —— 平方取中法 (Mid-Square Method)
除留余数法虽然好，但它直接利用了 Key 的原始值。如果 Key 的分布有很强的规律性（例如，1001, 1002, 1003...），尤其是低位的规律性，可能会导致不够散列。
我们能否找到一种方法，来“放大”和“混合”Key 内部的差异？
一个数字的平方，其结果的中间几位，通常会受到原始数字所有位的影响。比如 1234 和 1235，这两个数很接近，但它们的平方 1522756 和 1525225，中间几位的差异被放大了。相比之下，平方结果的最高位和最低位，更容易预测，包含的“信息熵”较少。
📌方法：
计算 Key 的平方。
抽取平方结果中间的若干位（位数可以根据 TableSize 的大小来定）作为哈希地址。
代码实现：
这个方法的核心思想是：通过相乘来混合信息，通过取中来保留信息最复杂的部分。
实现“取中间几位”有多种方式，可以用字符串，但更底层的方式是位运算或除法。这里我们用除法来模拟。假设我们的哈希表大小是 1000，我们需要一个 3 位的哈希值。
// 方法二：平方取中法
// 假设我们需要一个 0-999 范围的哈希值
int hash_midsquare(int key) {
// 1. 计算平方，为了防止 int 溢出，使用 long long
long long squared = (long long)key * key;
// 2. 抽取中间部分。这是一个模拟方法：
// 例如，对于 1234^2 = 1522756
// 先去掉末尾两位，得到 15227
squared = squared / 100;
// 再取结果对 1000 取模，得到中间的三位 227
int hash_value = squared % 1000;
// 3. 最后再对 TableSize 取模，确保范围合法
return hash_value % TABLE_SIZE;
}
注意：这里的 / 100 和 % 1000 是一个示例，实际应用中会根据 Key 的大致范围和 TableSize 来设计更普适的抽取方案（比如使用位运算右移和掩码）。
利用所有信息 —— 折叠法 (Folding Method)
如果 Key 特别长，比如一个 13 位的手机号码或者 18 位的身份证号，超出了 long long 的范围。我们该怎么办？
hash_mod 和 hash_midsquare 都不适用了。我们希望能有一种方法，让这个长 Key 的每一部分都对最终的哈希值有所贡献。
就像折叠一封长信一样，我们可以把这个长 Key 切成几段，然后把这几段“叠加”在一起。
👉方法：
将 Key 分割成若干个等长的部分。
将这些部分相加（或其他运算，如异或）。
最后将总和对 TableSize 取模。
代码实现：
处理超长数字，最方便的是当成字符串来处理，但这可能违反了“不用高级语法”的初衷。我们这里用纯数学运算来模拟处理一个 long long 范围内的长整数，这个思想可以推广到任意长度。
// 方法三：折叠法 (移位叠加)
// 将一个长整数，每3位为一段进行相加
int hash_folding(long long long_key) {
long long temp_key = long_key;
int sum = 0;
// 只要 key 还有剩余部分，就继续循环
while (temp_key > 0) {
// 取出末尾三位 (一段)
sum += temp_key % 1000;
// 移掉末尾三位
temp_key /= 1000;
}
// 最后对 TableSize 取模
return sum % TABLE_SIZE;
}
折叠法确保了 Key 的每一部分都被纳入了计算，避免了因为只看 Key 的一部分而丢失信息。
核心应用 —— 如何哈希字符串？
到目前为止我们处理的都是数字。但在现实世界中，用字符串作为 Key 的场景非常普遍（用户名、文件名等）。
计算机不认识 "Alice"，只认识它对应的 ASCII 码序列 65, 108, 105, 99, 101。我们需要把这个序列转换成一个整数。
❌错误尝试1：直接把所有字符的 ASCII 码相加。
hash = 65 + 108 + 105 + 99 + 101。
缺陷：这样会导致位置信息丢失。hash("stop") 会和 hash("pots") 得到相同的结果，因为它们的字符集相同，只是顺序不同。这会造成大量不必要的冲突。
✅正确思路：必须让字符的位置也参与到运算中。我们可以把字符串看成是一个P进制的数，其中 P 是一个质数（例如 31 或 37）。
"cat" 可以看作是 c*P^2 + a*P^1 + t*P^0。
这个方法（称为多项式哈希）既考虑了字符本身，也考虑了它的位置。
高效实现：直接计算幂次方效率低下。我们可以用一种迭代的方式（秦九韶算法/Horner's method）来高效计算：
hash = 0
hash = hash * P + 'c'
hash = hash * P + 'a'
hash = hash * P + 't'
每一步都取模，防止中间结果溢出。
代码实现：
#include
// 方法四：字符串哈希 (多项式滚动哈希)
int hash_string(const char* str) {
// 选择一个质数作为乘子
const int P = 31;
long long hash_value = 0;
int len = strlen(str);
for (int i = 0; i < len; i++) {
hash_value = (hash_value * P + str[i]) % TABLE_SIZE;
}
// 确保结果是正数
if (hash_value < 0) {
hash_value += TABLE_SIZE;
}
return hash_value;
}
完整代码与总结
#include
#include
// 全局的表大小
const int TABLE_SIZE = 11;
// 方法一：除留余数法
int hash_mod(int key) {
return key % TABLE_SIZE;
}
// 方法二：平方取中法
int hash_midsquare(int key) {
long long squared = (long long)key * key;
squared = squared / 100;
int hash_value = squared % 1000;
return hash_value % TABLE_SIZE;
}
// 方法三：折叠法
int hash_folding(long long long_key) {
long long temp_key = long_key;
int sum = 0;
while (temp_key > 0) {
sum += temp_key % 1000;
temp_key /= 1000;
}
return sum % TABLE_SIZE;
}
// 方法四：字符串哈希
int hash_string(const char* str) {
const int P = 31;
long long hash_value = 0;
int len = strlen(str);
for (int i = 0; i < len; i++) {
// 在循环内部取模，防止溢出
hash_value = (hash_value * P + str[i]) % TABLE_SIZE;
}
if (hash_value < 0) {
hash_value += TABLE_SIZE;
}
return hash_value;
}
int main() {
std::cout << "Table Size: " << TABLE_SIZE << std::endl << std::endl;
// --- 测试除留余数法 ---
int key1 = 123;
int key2 = 124;
std::cout << "--- 除留余数法 ---" << std::endl;
std::cout << "hash_mod(" << key1 << ") = " << hash_mod(key1) << std::endl;
std::cout << "hash_mod(" << key2 << ") = " << hash_mod(key2) << std::endl;
std::cout << std::endl;
// --- 测试平方取中法 ---
int key3 = 1234;
std::cout << "--- 平方取中法 ---" << std::endl;
std::cout << "hash_midsquare(" << key3 << ") = " << hash_midsquare(key3) << std::endl;
std::cout << std::endl;
// --- 测试折叠法 ---
long long key4 = 81-3123-4567; // 手机号
std::cout << "--- 折叠法 ---" << std::endl;
std::cout << "hash_folding(" << key4 << ") = " << hash_folding(key4) << std::endl;
std::cout << std::endl;
// --- 测试字符串哈希 ---
const char* str1 = "Alice";
const char* str2 = "Bob";
const char* str3 = "stop";
const char* str4 = "pots"; // Anagram of stop
std::cout << "--- 字符串哈希 ---" << std::endl;
std::cout << "hash_string(\"" << str1 << "\") = " << hash_string(str1) << std::endl;
std::cout << "hash_string(\"" << str2 << "\") = " << hash_string(str2) << std::endl;
std::cout << "hash_string(\"" << str3 << "\") = " << hash_string(str3) << std::endl;
std::cout << "hash_string(\"" << str4 << "\") = " << hash_string(str4) << " (与 stop 不同)" << std::endl;
return 0;
}
总结
没有“万能”的哈希函数，选择哪种取决于你的 Key 的特征。
对于普通的整数 Key，除留余数法（表长取素数）通常是最佳选择，简单且高效。
当 Key 的模式可能导致聚集时，可以考虑平方取中法来增加混乱度。
当 Key 非常长时，折叠法可以确保 Key 的所有部分都参与计算。
对于字符串 Key，多项式滚动哈希是业界标准，它兼顾了效率、确定性和均匀性，有效地区分了字符顺序。