C++布谷鸟哈希详解（从零实现高效哈希表）

为什么选择布谷鸟哈希？

• 查找操作最坏情况为 O(1)
• 空间效率高（负载因子可达 50% 以上）
• 非常适合缓存、数据库索引等需要快速查找的场景

C++ 实现步骤

我们将使用两个哈希表（用 vector 模拟）和两个简单的哈希函数来实现布谷鸟哈希。以下是完整代码：

#include <iostream>#include <vector>#include <stdexcept>#include <random>class CuckooHash {private:    static const int MAX_LOOP = 500; // 防止无限循环    std::vector<int> table1;    std::vector<int> table2;    int size;    int hash2(int key) {        return key % size;    }    int hash2(int key) {        return (key / size) % size;    }    void rehash() {        // 简化版：实际应用中应重建更大的表        throw std::runtime_error("Rehash needed! Table too full.");    }public:    CuckooHash(int s) : size(s) {        table1.assign(size, -1);        table2.assign(size, -1);    }    bool insert(int key) {        int current = key;        for (int i = 0; i < MAX_LOOP; ++i) {            int idx1 = hash2(current);            if (table1[idx1] == -1) {                table1[idx1] = current;                return true;            } else {                std::swap(table1[idx1], current);            }            int idx2 = hash2(current);            if (table2[idx2] == -1) {                table2[idx2] = current;                return true;            } else {                std::swap(table2[idx2], current);            }        }        // 如果循环太多次，说明表太满，需要扩容        rehash();        return false;    }    bool search(int key) {        return (table1[hash2(key)] == key) || (table2[hash2(key)] == key);    }    void print() {        std::cout << "Table1: ";        for (int x : table1) std::cout << x << " ";        std::cout << "\nTable2: ";        for (int x : table2) std::cout << x << " ";        std::cout << std::endl;    }};int main() {    CuckooHash cuckoo(7);    try {        cuckoo.insert(10);        cuckoo.insert(20);        cuckoo.insert(30);        cuckoo.insert(40);        cuckoo.print();        std::cout << "Search 20: " << (cuckoo.search(20) ? "Found" : "Not Found") << std::endl;        std::cout << "Search 99: " << (cuckoo.search(99) ? "Found" : "Not Found") << std::endl;    } catch (std::exception& e) {        std::cerr << "Error: " << e.what() << std::endl;    }    return 0;}

代码解析

上面的代码实现了基本的布谷鸟哈希功能：

• table1 和 table2 是两个哈希表，初始值为 -1 表示空位。
• hash2 和 hash2 是两个简单的哈希函数。
• insert 函数尝试将元素放入两个表之一；如果位置被占，则“踢出”原元素并继续处理。
• 为了避免无限循环，设置了最大尝试次数（MAX_LOOP），超过则抛出异常（实际项目中应触发 rehash 扩容）。

优化与扩展

本例是教学简化版。在真实应用中，你可以：

• 使用更高质量的哈希函数（如 MurmurHash）
• 实现自动扩容（rehash）机制
• 支持删除操作（需引入“墓碑”标记）
• 使用更多哈希函数（k-ary Cuckoo Hashing）提升负载因子

总结

通过本教程，你已经掌握了 C++布谷鸟哈希 的核心思想和基础实现。这种 高效哈希算法 在现代 C++数据结构 设计中具有重要价值。希望你能在此基础上继续探索，构建更强大的 哈希表实现！

© 2023 C++ 数据结构学习指南 | 专注高效算法教学