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

实战举例：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

C++ 算法代码：

class Solution {
public:
    int firstUniqChar(string s) {
        int count[26] = {0};
        for (auto ch : s) {
            count[ch - 'a']++;
        }
        for (int i = 0; i < s.size(); i++) {
            if (count[s[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
};

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 的质数表，后面的代码实现里面有）。

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

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1

3.1.2 完整代码实现

#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;                       // 已存储的数据个数
};

测试代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <unordered_map>
using namespace std;
#include "HashTable.h"

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;
    /*for (size_t i = 0; i < 100; i++) {
        ht.Insert({ rand(), i });
    }*/
}

struct HashFuncString {
    // BKDR
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash += ch;
            hash *= 131;
        }
        return hash;
    }
};

void TestHT2() {
    // HashTable<string, string, HashFuncString> dict;
    HashTable<string, string> dict;
    dict.Insert({ "string", "字符串" });
    dict.Insert({ "string", "字符串 1" });
    dict.Insert({ "left", "左边" });
    dict.Insert({ "right", "右边" });
    cout << dict.Find("string") << endl;
    cout << dict.Find("left") << endl;
    cout << dict.Find("left ") << endl;
    HashFuncString hfs;
    cout << hfs("abcd") << endl;
    cout << hfs("acbd") << endl;
    cout << hfs("aadd") << endl;
    unordered_map<string, string> dictmap;
    dictmap.insert({ "string", "字符串" });
    // 编译报错，需要自己实现 Hash 的仿函数把 key 转成整形
    //unordered_map<pair<string, int>, string> um;
    //um.insert({ {"string", 1}, "字符串" });
}

int main() {
    cout << "测试一：删除 5 后再查找" << endl;
    TestHT1();
    cout << endl;
    cout << "测试二：测试 string 类型" << endl;
    TestHT2();
    return 0;
}

测试结果如下：

关键细节:

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

3.1.3 二次探测

• 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；
• h(key) = hash0 = key%M，hash0 位置冲突了，则二次探测公式为：h(key,i) = hashi = （hash0 +(-) i^2）% M，i = {1，2，3，……，M/2}
• 二次探测当 hashi = (hash0 - i^2) % M 时，当 hashi<0 时，需要 hashi+=M
• 下面演示 {19,30,52,63,11,22} 等这一组值映射到 M=11 的表中

h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0

3.1.4 双重探测（了解）

• 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。
• h1(key) = hash0 = key % M，hash0 位置冲突了，则双重探测公式为：hc(key,i) = hashi = (hash0 + i ∗ h2 (key)) % M，i = {1, 2, 3, ..., M}、
• 要求 h2(key) < M 且 h2(key)和 M 互为质数，有两种简单的取值方法：1. 当 M 为 2 整数幂时，h2(key) 从 [0,M-1] 任选一个奇数；2. 当 M 为质数时，h2(key) = key % (M-1) + 1
• 保证 h2(key)与 M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数 p = gcd(M,h1(key)) > 1，那么所能寻址的位置的个数为 M/P < M，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为 1，偏移量为 3，整个散列表大小为 12，那么所能寻址的位置为 {1，4，7，10}，寻址个数为 12/gcd(12,3) = 4
• 下面演示 {19,30,52,74} 等这⼀组值映射到 M=11 的表中，设 h2 (key) = key%10 + 1

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

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

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

扩容：

完整代码实现：

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

// 质数表 (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>
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;
    }
};

// 链地址法哈希表（哈希桶）
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)。

测试代码：

namespace hash_bucket {
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 });
    ht.Insert({ 44, 44 });
    ht.Erase(58);
    ht.Erase(36);
}

void TestHT2() {
    HashTable<string, string> dict;
    dict.Insert({ "string", "字符串" });
    dict.Insert({ "string", "字符串 1" });
    dict.Insert({ "left", "左边" });
    dict.Insert({ "right", "右边" });
    cout << dict.Find("string") << endl;
    cout << dict.Find("left") << endl;
    cout << dict.Find("left ") << endl;
}
}

int main() {
    cout << "测试 2:" << endl;
    hash_bucket::TestHT1();
    cout << endl;
    cout << "测试 3:" << endl;
    hash_bucket::TestHT2();
}

3.3 两种实现对比

结语

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