哈希表原理与 C++ 实战实现

无论哈希函数设计得多优秀，冲突都无法完全避免。实战中处理哈希冲突的核心方法主要有两种：开放定址法和链地址法（拉链法）。其中链地址法因实现简单、性能稳定，被广泛应用于 STL 的 unordered_map、Java 的 HashMap 等容器中。

开放定址法：在数组内寻找'空位'

开放定址法的核心逻辑是：所有元素都存储在哈希表的数组中，当某个关键字的哈希位置被占用时，按照某种规则在数组中寻找下一个空位置存储。

它的约束是：负载因子 α 必须小于 1。常用的寻找规则有三种：线性探测、二次探测、双重探测。

1. 线性探测

这是最简单的开放定址法，规则是依次向后寻找。

• 用哈希函数计算初始位置 hash0 = Key % M；
• 如果 hash0 被占用，依次探测 hash0+1、hash0+2…，直到找到空位置；
• 若探测到数组末尾，回绕到数组开头继续探测（循环探测）。

数学表达式为：h_i(Key) = (hash0 + i) % M（i=1,2,...,M-1）

示例演示 假设 M=11（数组下标 0-10），关键字集合 {19,30,5,36,13,20,21,12}：

• 19%11=8 → 下标 8（空，存储 19）；
• 30%11=8 → 下标 8（被占用，探测 9→空，存储 30）；
• 5%11=5 → 下标 5（空，存储 5）；
• 36%11=3 → 下标 3（空，存储 36）；
• 13%11=2 → 下标 2（空，存储 13）；
• 20%11=9 → 下标 9（被占用，探测 10→空，存储 20）；
• 21%11=10 → 下标 10（被占用，探测 0→空，存储 21）；
• 12%11=1 → 下标 1（空，存储 12）。

最终数组存储结果（下标 0-10）：21、12、13、36、空、5、空、空、19、30、20。

线性探测的问题：群集（堆积） 线性探测的缺点很明显：如果某个区域的位置被连续占用，后续冲突的关键字都会往这个区域聚集，形成'群集'。这会导致探测次数增多，查询效率下降。

2. 二次探测

二次探测的核心是通过平方数跳跃探测，避免线性探测的群集问题。

• 初始位置 hash0 = Key % M；
• 若 hash0 被占用，依次探测 hash0+1²、hash0-1²、hash0+2²、hash0-2²…；
• 探测范围限制在 i ≤ M/2（避免重复探测），若探测到负数或超出数组范围，需调整到 [0, M-1] 区间。

数学表达式为：h_i(Key) = (hash0 ± i²) % M（i=1,2,...,M/2）

虽然二次探测能有效减少群集，但无法完全避免 —— 如果关键字的哈希值分布不均匀，仍可能出现局部群集。

3. 双重探测

双重探测（也叫双散列）的核心是用第二个哈希函数计算探测的偏移量，让探测路径更分散。

• 第一个哈希函数计算初始位置 hash0 = h1(Key) = Key % M；
• 第二个哈希函数计算偏移量 step = h2(Key)（要求 step < M 且与 M 互质）；
• 若 hash0 被占用，依次探测 hash0+step、hash0+2×step…，直到找到空位置。

数学表达式为：h_i(Key) = (hash0 + i×h2(Key)) % M（i=1,2,...,M-1）

关键要求：h2(Key) 与 M 互质 h2(Key) 必须与 M 互质（最大公约数为 1），否则探测路径会局限在部分位置，无法遍历整个数组。常用的 h2(Key) 设计：

• 当 M 为 2 的整数次幂时，h2(Key) 取奇数（奇数与 2 的整数次幂互质）；
• 当 M 为质数时，h2(Key) = Key % (M-1) + 1（确保 step 在 [1, M-1] 之间，且与 M 互质）。

双重探测的探测路径最分散，能最大程度避免群集，是开放定址法中性能最优的方案，但实现相对复杂。

开放定址法的删除问题：状态标识 开放定址法的一个关键问题是删除元素不能直接置空。如果直接将某个位置置空，后续探测该位置的关键字会误以为'前面没有冲突元素'，导致查找失败。

解决该问题的方案是给每个位置增加状态标识：

• EMPTY：初始状态，该位置从未存储过元素；
• EXIST：该位置当前存储着元素；
• DELETE：该位置的元素已被删除，可重新存储。

查找时，只有遇到 EMPTY 状态才停止探测；删除时，将状态改为 DELETE 而非置空；插入时，可将元素存储到 DELETE 或 EMPTY 状态的位置。

链地址法（拉链法）：冲突元素'链表化'

链地址法是实战中最常用的冲突解决机制，STL 的 unordered_map、Java 的 HashMap 都采用这种方式。它的核心逻辑是：

• 哈希表的底层是一个指针数组（桶数组），每个元素是一个链表的头指针；
• 用哈希函数计算关键字的桶下标（hash = Key % M）；
• 若该桶为空，直接将元素作为链表头节点插入；
• 若该桶已有关键字（冲突），将元素插入到链表的头部或尾部。

简单说，链地址法是将冲突的关键字'串成链表'，挂在对应的桶下面，因此也叫'哈希桶'。

示例演示 假设 M=11，关键字集合 {19,30,5,36,13,20,21,12,24,96}：

• 19%11=8 → 桶 8 链表：19；
• 30%11=8 → 桶 8 链表：30 → 19；
• 5%11=5 → 桶 5 链表：5；
• 36%11=3 → 桶 3 链表：36；
• 13%11=2 → 桶 2 链表：13；
• 20%11=9 → 桶 9 链表：20；
• 21%11=10 → 桶 10 链表：21；
• 12%11=1 → 桶 1 链表：12；
• 24%11=2 → 桶 2 链表：24 → 13；
• 96%11=8 → 桶 8 链表：96 → 30 → 19。

链地址法的优势 相比开放定址法，链地址法有明显优势：

• 无群集问题：冲突元素只在各自的链表中存储，不影响其他桶；
• 负载因子可大于 1：链表可以无限延长（理论上），无需严格限制负载因子；
• 删除简单：直接删除链表节点即可，无需状态标识；
• 空间利用率高：桶数组可以按需扩容，链表节点只在有冲突时创建。

极端场景优化：链表转红黑树 链地址法的唯一缺点是：如果某个桶的链表过长（比如恶意攻击或关键字分布极端），查询效率会降至 O(n)。为了解决这个问题，Java 8 的 HashMap 引入了优化：当链表长度超过阈值（默认 8）时，将链表转换为红黑树，查询效率提升至 O(log n)。

STL 的 unordered_map 没有这个优化，因为它假设哈希函数足够优秀，链表过长的场景极少发生。实际开发中，只要哈希函数设计合理，无需额外处理。

实现链地址法

下面我们用 C++ 手写一个基于链地址法的哈希表来加深理解。这段代码展示了如何管理节点、处理扩容以及实现基本的增删查操作。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 哈希仿函数：支持整数 Key
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

// 字符串 Key 的特化仿函数（BKDR 哈希）
template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash = hash * 131 + ch;
        }
        return hash;
    }
};

namespace hash_bucket {
    // 哈希链表节点
    template<class K, class V>
    struct HashNode {
        pair<K, V> _kv;         // 键值对
        HashNode<K, V>* _next;  // 下一个节点指针

        // 构造函数
        HashNode(const pair<K, V>& kv)
            : _kv(kv)
            , _next(nullptr) {}
    };

    // 链地址法哈希表（哈希桶）
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
    private:
        typedef HashNode<K, V> Node;
        vector<Node*> _tables; // 桶数组（存储链表头指针）
        size_t _n = 0;         // 存储的元素个数

        // 质数表：用于扩容
        static const unsigned long __stl_prime_list[];
        static const int __stl_num_primes;

        // 获取下一个质数
        unsigned long __stl_next_prime(unsigned long n) {
            const unsigned long* first = __stl_prime_list;
            const unsigned long* last = __stl_prime_list + __stl_num_primes;
            const unsigned long* pos = lower_bound(first, last, n);
            return pos == last ? *(last - 1) : *pos;
        }

    public:
        // 构造函数：初始化桶数组为第一个质数（53），所有桶为空指针
        HashTable() {
            _tables.resize(__stl_next_prime(0), nullptr);
        }

        // 析构函数：释放所有节点和桶数组
        ~HashTable() {
            // 遍历每个桶，释放链表节点
            for (size_t i = 0; i < _tables.size(); ++i) {
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr; // 桶置空
            }
        }

        // 插入键值对：头插法，效率 O(1)
        bool Insert(const pair<K, V>& kv) {
            // 查找是否已存在，避免重复插入
            if (Find(kv.first) != nullptr) {
                return false;
            }

            // 负载因子≥1，扩容
            if (_n == _tables.size()) {
                // 新桶数组大小为下一个质数
                size_t newSize = __stl_next_prime(_tables.size() + 1);
                vector<Node*> newTables(newSize, nullptr);

                Hash hash;
                // 遍历旧桶，将节点重新映射到新桶
                for (size_t i = 0; i < _tables.size(); ++i) {
                    Node* cur = _tables[i];
                    while (cur) {
                        Node* next = cur->_next; // 保存下一个节点

                        // 计算节点在新桶中的位置
                        size_t hashi = hash(cur->_kv.first) % newTables.size();
                        // 头插法插入新桶
                        cur->_next = newTables[hashi];
                        newTables[hashi] = cur;

                        cur = next; // 处理下一个节点
                    }
                    _tables[i] = nullptr; // 旧桶置空
                }

                // 交换新旧桶数组
                _tables.swap(newTables);
            }

            Hash hash;
            size_t hashi = hash(kv.first) % _tables.size(); // 计算桶下标
            // 头插法插入新节点
            Node* newNode = new Node(kv);
            newNode->_next = _tables[hashi];
            _tables[hashi] = newNode;

            ++_n;
            return true;
        }

        // 查找 Key：返回节点指针，不存在返回 nullptr
        Node* Find(const K& key) {
            Hash hash;
            size_t hashi = hash(key) % _tables.size(); // 找到对应的桶
            Node* cur = _tables[hashi];

            // 遍历链表查找
            while (cur) {
                if (cur->_kv.first == key) {
                    return cur;
                }
                cur = cur->_next;
            }

            return nullptr;
        }

        // 删除 Key：成功返回 true，不存在返回 false
        bool Erase(const K& key) {
            Hash hash;
            size_t hashi = hash(key) % _tables.size(); // 找到对应的桶
            Node* prev = nullptr;
            Node* cur = _tables[hashi];

            // 遍历链表查找要删除的节点
            while (cur) {
                if (cur->_kv.first == key) {
                    // 找到节点，删除
                    if (prev == nullptr) {
                        // 要删除的是头节点，更新桶的头指针
                        _tables[hashi] = cur->_next;
                    } else {
                        // 要删除的是中间节点，prev->next 指向 cur->next
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                // 移动指针
                prev = cur;
                cur = cur->_next;
            }

            return false;
        }

        // 获取元素个数
        size_t Size() const {
            return _n;
        }

        // 判空
        bool Empty() const {
            return _n == 0;
        }

        // 打印哈希表（调试用）
        void Print() {
            for (size_t i = 0; i < _tables.size(); ++i) {
                cout << "桶" << i << ": ";
                Node* cur = _tables[i];
                while (cur) {
                    cout << cur->_kv.first << "→" << cur->_kv.second << " ";
                    cur = cur->_next;
                }
                cout << endl;
            }
            cout << "当前元素个数：" << _n << endl;
            cout << "当前负载因子：" << (double)_n / _tables.size() << endl;
        }

        // 禁止拷贝构造和赋值（简化实现，如需支持可自行添加深拷贝）
        HashTable(const HashTable&) = delete;
        HashTable& operator=(const HashTable&) = delete;
    };

    // 初始化质数表
    template<class K, class V, class Hash>
    const unsigned long HashTable<K, V, Hash>::__stl_prime_list[] = {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291
    };

    template<class K, class V, class Hash>
    const int HashTable<K, V, Hash>::__stl_num_primes = sizeof(__stl_prime_list) / sizeof(__stl_prime_list[0]);
}

// 测试代码
int main() {
    hash_bucket::HashTable<string, int> ht;

    // 插入测试
    ht.Insert({"apple", 10});
    ht.Insert({"banana", 20});
    ht.Insert({"orange", 30});
    ht.Insert({"grape", 40});
    ht.Insert({"pear", 50});
    ht.Insert({"watermelon", 60});
    ht.Insert({"pineapple", 70});
    cout << "插入后哈希表：" << endl;
    ht.Print();
    cout << endl;

    // 查找测试
    auto orange = ht.Find("orange");
    if (orange) {
        cout << "查找 orange：" << orange->_kv.first << " → " << orange->_kv.second << endl;
    } else {
        cout << "查找 orange：未找到" << endl;
    }

    auto peach = ht.Find("peach");
    if (peach) {
        cout << "查找 peach：" << peach->_kv.first << " → " << peach->_kv.second << endl;
    } else {
        cout << "查找 peach：未找到" << endl;
    }
    cout << endl;

    // 删除测试
    bool ret = ht.Erase("grape");
    cout << "删除 grape：" << (ret ? "成功" : "失败") << endl;
    cout << "删除后哈希表：" << endl;
    ht.Print();
    cout << endl;

    // 插入重复 Key
    ret = ht.Insert({"apple", 15});
    cout << "插入重复的 apple：" << (ret ? "成功" : "失败") << endl;
    cout << "最终哈希表：" << endl;
    ht.Print();

    return 0;
}

注意：哈希表的冲突和扩容需要结合具体的情况来解决！！！在实际工程中，选择合适的哈希函数和扩容策略往往比算法本身的复杂度更重要。