C++ STL 哈希表详解：原理、冲突处理与模拟实现

乘法散列法

先将关键字 key 与一个在 (0, 1) 之间的常数 A 相乘，取小数部分，再乘以哈希表的大小 m，最后向下取整。

• 核心公式：

  • h(key) = floor(m × (key × A mod 1))
  • A：通常取黄金分割数 (√5 - 1) / 2 ≈ 0.6180339887。

• 关键特性：

  • 哈希值分布均匀：乘法运算能充分打乱关键字的二进制位。
  • 对哈希表大小要求灵活：不像除法散列法对 m 的取值有较多限制。

全域散列法

全域散列法是一种随机化哈希技术，通过从精心设计的哈希函数族中随机选择哈希函数，确保即使对于最坏情况下的输入也能获得良好的平均性能。

• 核心原理：
  • 对于任意两个不同的关键字 x 和 y，哈希函数族 H 满足：P(h(x) = h(y)) ≤ 1/m。
  • 实现时通常定义哈希函数族 h_{a,b}(k) = ((ak + b) mod p) mod m，其中 p 是大质数。

二、负载因子

1. 什么是负载因子？

负载因子（Load Factor）是哈希表设计与性能分析中的核心概念，用于衡量哈希表的'填充程度'，直接影响哈希冲突概率和内存利用率。

• 计算公式：λ = n / m
  • n：当前存储的有效元素数量。
  • m：哈希表的总容量。

2. 负载因子对哈希表的性能有什么影响？

• 负载因子越小 → 哈希冲突概率越低，操作接近 O(1)，但内存浪费严重。
• 负载因子越大 → 哈希冲突概率越高，操作可能退化到 O(n)，但内存利用率高。

3. 负载因子超过阈值时会发生什么？

当负载因子超过阈值（通常为 0.7）时，哈希表会触发扩容（Resize）：

1. 新建更大的桶数组（通常是原容量的 2 倍或下一个质数）。
2. 重新映射所有元素到新桶。
3. 释放旧内存。

三、哈希冲突

哈希冲突是指不同的关键字通过哈希函数计算后，得到相同的哈希地址的情况。这是哈希表设计中无法避免的核心问题，本质上是哈希函数'多对一'的映射特性导致的。

四、冲突处理

方法一：开放定址法

开放定址法的所有元素都存储在哈希表数组本身中，通过探测序列寻找可用的空槽位。

线性探测

• 探测公式：h_i(key) = (h(key) + i) % m
• 特点：简单，但容易产生'聚集'现象（连续的若干个位置被占用）。

二次探测

• 探测公式：h_i(key) = (h(key) + c1 * i + c2 * i * i) % m
• 特点：减少聚集现象，但不能探测到哈希表中的所有位置（取决于 m 的取值）。

双重散列

• 探测公式：h_i(key) = (h1(key) + i * h2(key)) % m
• 特点：探测序列比较均匀，能有效减少聚集。需保证 h2(key) 与 M 互质。

方法二：链地址法

链地址法（也叫拉链法）用数组 + 链表的组合，让冲突元素'链'在一起。

• 原理：底层是数组，每个元素对应一个链表。插入时追加到链表末尾，查找时遍历链表。
• 优缺点：
  • 优点：冲突处理简单；空间灵活（负载因子可大于 1）；无聚集问题。
  • 缺点：遍历开销；额外指针空间开销。

基本操作

怎么解决键 key 不能取模的问题？

当关键字不是整数（如 string、Date 等类型）时，需要增加一个仿函数（哈希函数对象），将 key 转换成一个可用于取模的整数。若 key 无法直接转换为整数，需自行实现仿函数。

/*------------------任务：定义哈希表函数的'结构体模板'------------------*/
template<class K>
struct HashFunc {
    // 重载 () 运算符 ---> 作用：将 K 类型转化为 size_t 类型
    size_t operator()(const K& key) {
        return (size_t)key; // 默认为直接转换，适用于 int、long 等
    }
};

/*------------------任务：定义哈希函数的'模板特化'------------------*/
template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        size_t hash = 0;
        // 使用 BKDR 算法计算其哈希值
        for (auto it : s) {
            hash += it;
            hash *= 131; // 131 可有效减少冲突
        }
        return hash;
    }
};

一、开放定址法实现

在实践里，开放定址法的表现不如链地址法，因为各元素的存储始终存在相互影响。这里我们选用线性探测的方式来实现。

哈希结构

enum State {
    EXIST,  // 存在状态
    EMPTY,  // 空状态
    DELETE  // 删除状态
};

template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:
    vector<HashData<K, V>> _tables;
    size_t _n;
public:
    // ... 成员函数实现见下文
};

删除操作

在开放定址法中，删除节点时不能直接清空内存，否则会影响后续冲突值的查找。需要将状态标记为 DELETE，这样查找时遇到 EMPTY 才停止，遇到 DELETE 则继续探测。

扩容操作

我们将负载因子控制在 0.7，达到阈值后扩容。为了保证哈希表大小始终为质数，我们预先提供一个质数表，扩容时从中选取合适的大小。

inline unsigned long _stl_next_prime(unsigned long n) {
    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
    };
    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 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:
    vector<HashNode<K, V>*> _tables;
    size_t _n;
public:
    // ... 成员函数实现见下文
};

扩容操作

链地址法的负载因子没有限制，可大于 1。STL 中的最大负载因子基本控制在 1，一旦大于 1 就会触发扩容。扩容时采用头插法迁移节点，效率较高。

代码实现

头文件：HashTable.h

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

template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto it : s) {
            hash += it;
            hash *= 131;
        }
        return hash;
    }
};

inline unsigned long _stl_next_prime(unsigned long n) {
    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
    };
    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;
}

开放定址法：open_address.h

#pragma once
#include "HashTable.h"
namespace open_address {
    enum State { EXIST, EMPTY, DELETE };

    template<class K, class V>
    struct HashData {
        pair<K, V> _kv;
        State _state = EMPTY;
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
    private:
        vector<HashData<K, V>> _tables;
        size_t _n;
    public:
        HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

        HashData<K, V>* Find(const K& key) {
            Hash hash;
            size_t hash_0 = hash(key) % _tables.size();
            size_t hash_i = hash_0;
            size_t i = 1;
            while (_tables[hash_i]._state != EMPTY) {
                if (_tables[hash_i]._state == EXIST && _tables[hash_i]._kv.first == key) {
                    return &_tables[hash_i];
                }
                hash_i = (hash_0 + i) % _tables.size();
                ++i;
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            HashData<K, V>* ret = Find(key);
            if (ret) {
                ret->_state = DELETE;
                --_n;
                return true;
            }
            return false;
        }

        bool Insert(const pair<K, V>& kv) {
            if (Find(kv.first)) return false;
            if (_n * 10 / _tables.size() >= 7) {
                HashTable<K, V, Hash> newHt;
                newHt._tables.resize(_stl_next_prime(_tables.size() + 1));
                for (auto& htData : _tables) {
                    if (htData._state == EXIST) {
                        newHt.Insert(htData._kv);
                    }
                }
                _tables.swap(newHt._tables);
            }
            Hash hashFunc;
            size_t hash_0 = hashFunc(kv.first) % _tables.size();
            size_t hash_i = hash_0;
            size_t i = 1;
            while (_tables[hash_i]._state == EXIST) {
                hash_i = (hash_0 + i) % _tables.size();
                ++i;
            }
            _tables[hash_i]._kv = kv;
            _tables[hash_i]._state = EXIST;
            ++_n;
            return true;
        }
    };
}

链地址法：hash_bucket.h

#pragma once
#include "HashTable.h"
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:
        vector<HashNode<K, V>*> _tables;
        size_t _n;
        typedef HashNode<K, V> Node;
    public:
        HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

        ~HashTable() {
            for (size_t i = 0; i < _tables.size(); ++i) {
                Node* current = _tables[i];
                while (current) {
                    Node* next = current->_next;
                    delete current;
                    current = next;
                }
                _tables[i] = nullptr;
            }
        }

        Node* Find(const K& key) {
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            Node* current = _tables[hash_i];
            while (current) {
                if (current->_kv.first == key) return current;
                current = current->_next;
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            Node* curr = _tables[hash_i];
            Node* prev = nullptr;
            while (curr) {
                if (curr->_kv.first == key) {
                    if (prev == nullptr) {
                        _tables[hash_i] = curr->_next;
                    } else {
                        prev->_next = curr->_next;
                    }
                    delete curr;
                    --_n;
                    return true;
                }
                prev = curr;
                curr = curr->_next;
            }
            return false;
        }

        bool Insert(const pair<K, V>& kv) {
            if (Find(kv.first)) return false;
            if (_n == _tables.size()) {
                vector<Node*> newVector(_tables.size() * 2);
                for (size_t i = 0; i < _tables.size(); i++) {
                    Node* current = _tables[i];
                    while (current) {
                        Node* next = current->_next;
                        Hash hashFunc;
                        size_t hash_i = hashFunc(current->_kv.first) % newVector.size();
                        current->_next = newVector[hash_i];
                        newVector[hash_i] = current;
                        current = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newVector);
            }
            Node* newNode = new Node(kv);
            Hash hashFunc;
            size_t hash_i = hashFunc(kv.first) % _tables.size();
            newNode->_next = _tables[hash_i];
            _tables[hash_i] = newNode;
            ++_n;
            return true;
        }
    };
}

测试文件：Test.cpp

#include "HashTable.h"
#include "open_address.h"
#include "hash_bucket.h"
#include <string>
#include <iostream>
using namespace std;

void printTestResult(const string& testName, bool result) {
    cout << (result ? "[PASS] " : "[FAIL] ") << testName << endl;
}

void test_open_address() {
    cout << "\n===== 测试开放寻址法哈希表 =====" << endl;
    open_address::HashTable<int, string> ht;
    cout << "创建哈希表成功" << endl;

    cout << "\n--- 插入测试 ---" << endl;
    bool insert1 = ht.Insert({1, "A"});
    printTestResult("插入键 1 值 A", insert1);
    bool insert2 = ht.Insert({1, "B"});
    printTestResult("插入重复键 1 值 B（期望失败）", !insert2);
    bool insert3 = ht.Insert({2, "C"});
    printTestResult("插入键 2 值 C", insert3);

    cout << "\n--- 查找测试 ---" << endl;
    auto node1 = ht.Find(1);
    printTestResult("查找键 1", node1 != nullptr && node1->_kv.second == "A");
    auto node2 = ht.Find(2);
    printTestResult("查找键 2", node2 != nullptr && node2->_kv.second == "C");
    auto node3 = ht.Find(3);
    printTestResult("查找不存在的键 3", node3 == nullptr);

    cout << "\n--- 删除测试 ---" << endl;
    bool erase1 = ht.Erase(1);
    printTestResult("删除键 1", erase1);
    bool erase2 = ht.Erase(1);
    printTestResult("重复删除键 1（期望失败）", !erase2);

    cout << "\n--- 扩容测试 ---" << endl;
    cout << "开始插入大量数据以触发扩容..." << endl;
    for (int i = 3; i < 100; ++i) {
        ht.Insert({i, to_string(i)});
    }
    cout << "插入完成，验证数据访问..." << endl;
    auto node99 = ht.Find(99);
    printTestResult("查找扩容后的键 99", node99 != nullptr && node99->_kv.second == "99");
}

void test_hash_bucket() {
    cout << "\n===== 测试链地址法哈希表 =====" << endl;
    hash_bucket::HashTable<string, int> ht;
    cout << "创建哈希表成功" << endl;

    cout << "\n--- 插入测试 ---" << endl;
    bool insert1 = ht.Insert({"apple", 5});
    printTestResult("插入键 apple 值 5", insert1);
    bool insert2 = ht.Insert({"apple", 10});
    printTestResult("插入重复键 apple 值 10（期望失败）", !insert2);
    bool insert3 = ht.Insert({"banana", 8});
    printTestResult("插入键 banana 值 8", insert3);

    cout << "\n--- 查找测试 ---" << endl;
    auto node1 = ht.Find("apple");
    printTestResult("查找键 apple", node1 != nullptr && node1->_kv.second == 5);
    auto node2 = ht.Find("banana");
    printTestResult("查找键 banana", node2 != nullptr && node2->_kv.second == 8);
    auto node3 = ht.Find("orange");
    printTestResult("查找不存在的 orange", node3 == nullptr);

    cout << "\n--- 删除测试 ---" << endl;
    bool erase1 = ht.Erase("apple");
    printTestResult("删除键 apple", erase1);
    bool erase2 = ht.Erase("apple");
    printTestResult("重复删除键 apple（期望失败）", !erase2);

    cout << "\n--- 扩容测试 ---" << endl;
    cout << "开始插入大量数据以触发扩容..." << endl;
    for (int i = 0; i < 100; ++i) {
        string key = "key_" + to_string(i);
        ht.Insert({key, i});
    }
    cout << "插入完成，验证数据访问..." << endl;
    auto node = ht.Find("key_99");
    printTestResult("查找扩容后的键 key_99", node != nullptr && node->_kv.second == 99);
}

struct Date {
    int _year;
    int _month;
    int _day;
    Date(int year = 1, int month = 1, int day = 1) : _year(year), _month(month), _day(day) {}
    bool operator==(const Date& d) const {
        return _year == d._year && _month == d._month && _day == d._day;
    }
};

struct DateHashFunc {
    size_t operator()(const Date& d) {
        size_t hash = 0;
        hash += d._year; hash *= 131;
        hash += d._month; hash *= 131;
        hash += d._day; hash *= 131;
        return hash;
    }
};

void test01() {
    hash_bucket::HashTable<string, string> ht1;
    const char* a1[] = {"abcd", "sort", "insert"};
    for (auto& it : a1) {
        ht1.Insert({it, it});
    }

    hash_bucket::HashTable<int, int> ht2;
    const int a2[] = {-19, -30, 5, 36, 13, 20, 21, 12};
    for (auto& it : a2) {
        ht2.Insert({it, it});
    }

    hash_bucket::HashTable<Date, int, DateHashFunc> ht3;
    ht3.Insert({{2025, 6, 29}, 1});
    ht3.Insert({{2025, 6, 30}, 1});
}

int main() {
    test_open_address();
    test_hash_bucket();
    test01();
    return 0;
}