C++再哈希法详解（手把手教你用C++实现哈希冲突的再哈希解决方案）

什么是再哈希法？

再哈希法是开放寻址法的一种变体。当发生哈希冲突时，它不再使用线性探测或二次探测，而是使用第二个哈希函数来计算一个新的位置。这个新位置通常通过以下公式确定：

new_index = (hash2(key) + i * hash2(key)) % table_size

其中：
- hash2(key) 是主哈希函数
- hash2(key) 是再哈希函数
- i 是探测次数（从0开始）
- table_size 是哈希表的大小（建议为质数）

这种方法能有效减少“聚集”现象，提高哈希表的性能。

为什么选择C++实现再哈希法？

C++提供了对内存和底层操作的精细控制，非常适合实现高效的数据结构。通过手动管理数组和指针，我们可以清晰地看到C++哈希表实现的每一个细节，这对学习数据结构原理非常有帮助。

完整C++代码实现

下面是一个完整的、可运行的C++再哈希法实现示例：

#include <iostream>#include <vector>#include <string>class RehashHashTable {private:    std::vector<int> table;    int size;    const int EMPTY = -1; // 标记空槽    // 主哈希函数    int hash2(int key) {        return key % size;    }    // 再哈希函数（必须与表大小互质）    int hash2(int key) {        // 通常选择一个小于size的质数        return 7 - (key % 7);    }public:    RehashHashTable(int tableSize) : size(tableSize) {        table.assign(size, EMPTY);    }    void insert(int key) {        int index = hash2(key);        int step = hash2(key);        int i = 0;        while (i < size) {            if (table[index] == EMPTY) {                table[index] = key;                std::cout << "插入 " << key << " 到位置 " << index << std::endl;                return;            }            // 再哈希：计算下一个探测位置            index = (index + step) % size;            i++;        }        std::cout << "哈希表已满，无法插入 " << key << std::endl;    }    bool search(int key) {        int index = hash2(key);        int step = hash2(key);        int i = 0;        while (i < size && table[index] != EMPTY) {            if (table[index] == key) {                return true;            }            index = (index + step) % size;            i++;        }        return false;    }    void display() {        std::cout << "哈希表内容: ";        for (int i = 0; i < size; ++i) {            if (table[i] == EMPTY)                std::cout << "[ ] ";            else                std::cout << "[" << table[i] << "] ";        }        std::cout << std::endl;    }};int main() {    // 建议表大小为质数，以减少冲突    RehashHashTable ht(13);    // 插入一些测试数据    ht.insert(10);    ht.insert(22);    ht.insert(31);    ht.insert(4);    ht.insert(15);    ht.insert(28);    ht.insert(17);    ht.insert(88);    ht.insert(59);    ht.display();    // 搜索测试    std::cout << "搜索 15: " << (ht.search(15) ? "找到" : "未找到") << std::endl;    std::cout << "搜索 100: " << (ht.search(100) ? "找到" : "未找到") << std::endl;    return 0;}

代码关键点解析

• 主哈希函数：hash2(key) = key % size，这是最常用的哈希方式。
• 再哈希函数：hash2(key) = 7 - (key % 7)，确保结果不为0，并且与表大小互质。
• 表大小选择：建议使用质数（如13、17、19等），这样可以最大化探测序列的覆盖范围。
• 空槽标记：使用-1表示空位置，便于判断是否已占用。

再哈希法的优势与注意事项

✅ 优势：

• 比线性探测更均匀地分布元素，减少聚集。
• 平均查找效率高，尤其在负载因子较高时表现更好。

⚠️ 注意事项：

• 再哈希函数不能返回0，否则会导致无限循环。
• 表大小应为质数，以保证探测序列覆盖所有槽位。
• 当负载因子超过0.7时，建议进行扩容并重新哈希（rehashing）。

总结

通过本教程，你已经掌握了如何使用C++再哈希法来解决哈希冲突问题。再哈希法作为开放寻址再哈希的经典策略，不仅理论清晰，而且实现简单高效。希望你能将所学应用到实际项目中，进一步提升对哈希冲突解决机制的理解。

如果你觉得这篇文章对你有帮助，不妨动手运行一下代码，修改参数，观察不同输入下的哈希分布效果。实践是掌握数据结构的最佳方式！