C语言再哈希法详解（解决哈希冲突的高效策略）

再哈希法的核心思想

假设我们有两个哈希函数：

• h₁(key) = key % 表大小（主哈希函数）
• h₂(key) = R - (key % R)，其中 R 是小于表大小的最大质数（辅助哈希函数）

当插入或查找时发生冲突，探测序列为：

(h₁(key) + i * h₂(key)) % 表大小
其中 i = 0, 1, 2, ...

C语言实现再哈希法

下面是一个完整的C语言示例，展示如何用再哈希法实现哈希表：

#include <stdio.h>#include <stdlib.h>#define TABLE_SIZE 13  // 哈希表大小，建议为质数#define EMPTY -1       // 空槽标记// 主哈希函数int hash2(int key) {    return key % TABLE_SIZE;}// 辅助哈希函数（再哈希函数）int hash2(int key) {    // R 应为小于 TABLE_SIZE 的最大质数    int R = 11;    return R - (key % R);}// 插入函数void insert(int hashTable[], int key) {    int index = hash2(key);    int step = hash2(key);    int i = 0;    while (i < TABLE_SIZE) {        int pos = (index + i * step) % TABLE_SIZE;        if (hashTable[pos] == EMPTY) {            hashTable[pos] = key;            printf("插入 %d 到位置 %d\n", key, pos);            return;        }        i++;    }    printf("哈希表已满，无法插入 %d\n", key);}// 查找函数int search(int hashTable[], int key) {    int index = hash2(key);    int step = hash2(key);    int i = 0;    while (i < TABLE_SIZE) {        int pos = (index + i * step) % TABLE_SIZE;        if (hashTable[pos] == key) {            return pos;        }        if (hashTable[pos] == EMPTY) {            break; // 后续不可能有该元素        }        i++;    }    return -1; // 未找到}int main() {    int hashTable[TABLE_SIZE];        // 初始化哈希表    for (int i = 0; i < TABLE_SIZE; i++) {        hashTable[i] = EMPTY;    }    // 插入一些数据    insert(hashTable, 10);    insert(hashTable, 23);    insert(hashTable, 36);    insert(hashTable, 49);    insert(hashTable, 62);    // 查找测试    int key = 36;    int pos = search(hashTable, key);    if (pos != -1) {        printf("%d 找到了，位置是 %d\n", key, pos);    } else {        printf("%d 未找到\n", key);    }    return 0;}

为什么选择再哈希法？

相比线性探测，再哈希法能有效避免一次聚集（primary clustering）问题；相比二次探测，它几乎不会产生二次聚集（secondary clustering）。因此，在高性能要求的场景中，再哈希算法是一个非常优秀的选择。

注意事项

• 哈希表大小最好为质数，以保证探测序列覆盖所有槽位。
• 辅助哈希函数 h₂(key) 的结果不能为0，否则会陷入死循环。
• 删除操作在开放定址法中较复杂，通常使用“懒删除”标记。

总结

通过本文，你已经掌握了C语言再哈希法的基本原理和实现方式。再哈希法是解决哈希冲突的高效策略之一，特别适合对性能要求较高的应用。希望你能动手实践，加深理解！

关键词回顾：C语言再哈希法、哈希冲突解决、再哈希算法、C语言哈希表实现