哈希表实现详解：开放定址法与链地址法

2.2 除法散列法（除留余数法）

最常用的哈希函数，公式：h(key) = key % M（M 为哈希表大小）。

• 关键优化：M 建议取不接近 2 的整数次幂的质数，避免 key 的后几位重复导致冲突（如 M=16 时，63 和 31 的余数都是 15）；
• 例外：Java HashMap 用 2 的整数次幂作为 M，通过位运算优化效率，同时用异或操作让 key 所有位参与计算，保证分布均匀。

2.3 其他方法（了解）

• 乘法散列法：h(key) = floor(M * ((A*key) % 1.0))，A 取黄金分割点 0.618，对 M 无要求；
• 全域散列法：通过随机选取哈希函数避免恶意攻击，公式：h_ab(key) = ((a*key + b) % P) % M（P 为大质数）；
• 字符串哈希：将字符串转为整数（如 BKDR 哈希，hash = hash*131 + 字符 ASCII 码），避免 'abcd' 和 'bcad' 这类字符串冲突。

2.4 字符串哈希实现（特化仿函数）

当 key 为字符串时，需手动实现哈希函数，将其转为整数：

// 哈希函数仿函数
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // 默认直接转换
    }
};

// 特化 string 类型的哈希函数
template<>
struct HashFunc<string> {
    // BKDR 字符串哈希算法
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash += ch;       // 累加字符 ASCII 码
            hash *= 131;      // 乘质数 131，减少冲突
        }
        return hash;
    }
};

三. 哈希冲突解决策略

冲突解决是哈希表实现的核心，主流分为 开放定址法 和 链地址法，其中链地址法更加重要一点，下面分别详解实现。

3.1 实现一：开放定址法（线性探测，二次探测）

开放定址法的核心：所有元素存储在哈希表数组中，冲突时按规则探测下一个空闲位置。

3.1.1 线性探测核心设计

• 状态标识：每个位置需标记 EMPTY（空）、EXIST（已存储）、DELETE（已删除），避免删除元素后影响后续查找；
• 探测规则：线性探测（冲突后依次向后查找空闲位置）；
• 扩容策略：负载因子≥0.7 时扩容，哈希表大小取质数（参考 SGI STL 的质数表）。

从发生哈希冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，就回绕到哈希表头的位置。

3.1.2 完整代码实现

这里我们使用 C++ 模板来实现一个通用的开放定址法哈希表。注意代码中关于质数表和扩容逻辑的处理。

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 状态标识
enum State {
    EMPTY,   // 空位置
    EXIST,   // 已存储元素
    DELETE   // 已删除元素
};

// 质数表 (SGI STL 同款，用于扩容)
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
    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
};

inline 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;
}

// 哈希表结点结构
template<class K, class V>
struct HashData {
    pair<K, V> _kv;     // 存储 key-value 对
    State _state = EMPTY; // 初始状态为空
};

// 哈希函数仿函数
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // 默认直接转换
    }
};

// 特化 string 类型的哈希函数
template<>
struct HashFunc<string> {
    // BKDR 字符串哈希算法
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash += ch;       // 累加字符 ASCII 码
            hash *= 131;      // 乘质数 131，减少冲突
        }
        return hash;
    }
};

// 开放定址法哈希表 (线性探测)
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
    // 构造函数 (初始化哈希表大小为第一个质数)
    HashTable() : _tables(__stl_next_prime(1)) {}

    // 插入 key-value 对 (去重)
    bool Insert(const pair<K, V>& kv) {
        // 1. 先查找，避免重复插入
        if (Find(kv.first)) return false;

        // 2. 负载因子 >= 0.7，扩容
        if ((double)_n / (double)_tables.size() >= 0.7) {
            HashTable<K, V, Hash> newht;
            newht._tables.resize(__stl_next_prime(_tables.size() + 1));

            // 3. 迁移旧表元素到新表
            for (size_t i = 0; i < _tables.size(); i++) {
                // 遍历旧表，旧表数据插入到 newht
                if (_tables[i]._state == EXIST) {
                    newht.Insert(_tables[i]._kv);
                }
            }
            // 4. 交换新旧表
            _tables.swap(newht._tables);
        }

        // 5. 线性探测找空闲位置
        Hash hs;
        size_t hash0 = hs(kv.first) % _tables.size();
        // 线性探测
        size_t i = 1;
        size_t hashi = hash0;
        while (_tables[hashi]._state == EXIST) {
            // 冲突，线性探测下一个位置
            hashi = (hash0 + i) % _tables.size();
            ++i;
        }

        // 6. 插入元素
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = EXIST;
        ++_n;
        return true;
    }

    // 查找 key，返回节点指针 (nullptr 表示未找到)
    HashData<K, V>* Find(const K& key) {
        Hash hs;
        size_t hash0 = hs(key) % _tables.size();
        // 线性探测
        size_t i = 1;
        size_t hashi = hash0;
        // 遇到 EMPTY 才停止查找 (DELETE 继续探测)
        while (_tables[hashi]._state != EMPTY) {
            if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key) {
                return &_tables[hashi];
            }
            // 线性探测下一个位置
            hashi = (hash0 + i) % _tables.size();
            ++i;
        }
        return nullptr;
    }

    // 删除 key(仅修改状态为 DELETE,不实际删除元素)
    bool Erase(const K& key) {
        HashData<K, V>* ret = Find(key);
        if (ret) {
            // 标记为 DELETE,避免影响后续查找
            ret->_state = DELETE;
            --_n;
            return true;
        } else {
            return false;
        }
    }

private:
    std::vector<HashData<K, V>> _tables; // 哈希表数组
    size_t _n = 0;                       // 已存储的数据个数
};

测试代码示例：

void TestHT1() {
    int a[] = { 19, 30, 5, 36, 13, 20, 21, 12, 58 };
    HashTable<int, int> ht;
    for (auto e : a) {
        ht.Insert({ e, e });
    }
    ht.Insert({ -2, 2 });
    ht.Insert({ 22, 22 });
    cout << "删除 5 之前查找 5,58 结果：" << endl;
    cout << ht.Find(5) << endl;
    cout << ht.Find(58) << endl;
    ht.Erase(5);
    cout << "删除 5 之后查找 5,58 结果：" << endl;
    cout << ht.Find(5) << endl;
    cout << ht.Find(58) << endl;
}

关键细节：

• 状态标识：删除元素时不直接清空，而是标记为 DELETE，确保后续查找冲突元素时能继续探测；
• 扩容逻辑：扩容后需重新映射所有元素（因为哈希表大小变化，存储位置改变）；
• 线性探测缺陷：容易出现'群集（堆积）'（连续位置被占用，后续冲突集中争夺同一位置），可通过二次探测、双重探测优化。

3.1.3 二次探测

从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找下一个没有存储数据的位置为止。如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。

• 公式：h(key,i) = hashi = （hash0 + (-) i^2）% M，i = {1, 2, 3, ……, M/2}
• 当 hashi = (hash0 - i^2) % M 时，当 hashi < 0 时，需要 hashi += M。

3.1.4 双重探测（了解）

第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。

• 公式：hc(key,i) = hashi = (hash0 + i ∗ h2(key)) % M，i = {1, 2, 3, ..., M}
• 要求 h2(key) < M 且 h2(key) 和 M 互为质数。

3.2 实现二：链地址法（哈希桶）

链地址法的核心：哈希表数组存储链表头指针，冲突元素链接成链表（哈希桶），不占用其他位置。

• 结构：哈希表是指针数组，每个元素是链表头指针，冲突元素通过链表链接；
• 扩容策略：负载因子≥1 时扩容（链地址法负载因子可大于 1）；
• 优势：无群集问题，空间利用率高，实现简单。

完整代码实现：

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 {
    typedef HashNode<K, V> Node;
public:
    HashTable() : _tables(__stl_next_prime(1), nullptr), _n(0) {}

    ~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;
        }
        _n = 0;
    }

    // 插入 key-value 对（头插法，支持重复插入，去重需先查找）
    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) return false;
        Hash hs;
        // 1. 负载因子≥1，扩容（链地址法负载因子可大于 1）
        if (_n == _tables.size()) {
            std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
            // 2. 迁移旧表节点到新表（直接移动节点，不新建，效率更高）
            for (size_t i = 0; i < _tables.size(); i++) {
                // 遍历旧表，旧表节点重新映射，挪动到新表
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    // 3. 重新计算节点在新表的位置
                    size_t hashi = hs(cur->_kv.first) % newtables.size();
                    // 4. 头插入新表
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
        }
        size_t hashi = hs(kv.first) % _tables.size();
        // 5. 头插入当前节点
        Node* newnode = new Node(kv);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return true;
    }

    // 查找 key，返回节点指针（nullptr 表示未找到）
    Node* Find(const K& key) {
        Hash hs;
        size_t hashi = hs(key) % _tables.size();
        Node* cur = _tables[hashi];
        while (cur) {
            if (cur->_kv.first == key) {
                return cur;
            }
            cur = cur->_next;
        }
        return nullptr;
    }

    // 删除 key（链表节点删除）
    bool Erase(const K& key) {
        Hash hs;
        size_t hashi = hs(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;
                }
                --_n;
                delete cur;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

private:
    std::vector<Node*> _tables; // 指针数组（存储链表头指针）
    size_t _n;
};
}

关键细节：

• 节点迁移：扩容时直接移动旧表节点到新表，不新建节点，减少内存开销；
• 链表操作：插入用头插法（效率高），删除需记录前驱节点；
• 极端优化：Java8 的 HashMap 中，当链表长度超过 8 时，会将链表转为红黑树，避免单桶过长导致效率退化到 O(N)。

3.3 两种实现对比

结尾

哈希表的核心是'哈希函数 + 冲突解决'：好的哈希函数保证 key 均匀分布，合理的冲突策略保证效率稳定。开放定址法适合空间充足的场景，链地址法因实现简单、无群集问题，成为工业级实现的首选（如 C++ 的 unordered_map、Java 的 HashMap）。本文实现的两种哈希表，覆盖了哈希表的核心细节：质数扩容、字符串哈希、元素迁移、状态标识等。掌握这些细节后，不仅能理解 STL 容器的底层实现，更能根据实际场景选择合适的哈希表设计。