C++ 进阶：哈希表原理与实现

关键特性与优缺点：

• 优点：实现简单；适用性广；控制范围。
• 缺点：冲突概率与 m 强相关；依赖 m 的选取；不适用于动态扩容。

优化：m 的选取原则

• 选质数：优先选质数作为 m，能大幅降低冲突概率。
• 避免 m=2^k/10^X：若 M = 2^X，key % M 等价于保留 key 的最后 X 位二进制数，易导致冲突。
• 结合关键字分布调整：若已知关键字的分布，选 m 时尽量让余数覆盖更全。

乘法散列法

乘法散列法：先将关键字 key 与一个在 (0, 1) 之间的常数 A 相乘，得到一个小数。取这个小数的小数部分，再乘以哈希表的大小 m，最后对结果向下取整，就得到了哈希值。

核心公式与基本原理： h(key) = ⌊m × (key × A mod 1)⌋

• key：是要进行哈希计算的关键字。
• A：是一个常数。（取值范围在 (0, 1) 之间，通常是无理数，如黄金分割数）
• m：是哈希表的大小。

关键特性与优缺点：

• 优点：哈希值分布均匀；对哈希表大小要求灵活；计算效率较高。
• 缺点：常数 A 的选择有难度；实现相对复杂。

全域散列法

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

核心原理： 全域散列法基于一个哈希函数族 H，在使用时会从这个函数族中随机选择一个哈希函数 h 来进行哈希操作。对于任意两个不同的关键字 x 和 y，哈希函数族 H 满足： |{h ∈ H : h(x) = h(y)}| / |H| ≤ 1/m 这样就能保证在平均情况下，哈希冲突的数量是比较少的。

二、负载因子

1. 什么是负载因子？

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

负载因子的计算公式： λ = n / m

• n：是哈希表中当前存储的有效元素数量。
• m：是哈希表的总容量（即桶数组的长度）。

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

• 负载因子越小 → 哈希冲突概率越低，但内存浪费严重。
• 负载因子越大 → 哈希冲突概率越高，操作时间复杂度会退化到 O(n)，但内存利用率高。

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

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

1. 新建更大的桶数组。
2. 重新映射所有元素。
3. 释放旧内存。

三、哈希冲突

哈希冲突（Hash Collision）：指不同的关键字通过哈希函数计算后，得到相同的哈希地址的情况。本质是哈希函数是'多对一'的映射，根据鸽巢原理，冲突必然存在。

四、冲突处理

方法一：开放定址法

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

线性探测

探测公式：h_i(key) = (h(key) + i) % m 缺点：容易产生'聚集'现象。

二次探测

探测公式：h_i(key) = (h(key) + c1 * i + c2 * i * i) % m 通常取 c1 = 0，c2 = 1。 优点：相较于线性探测，能减少聚集现象。

双重散列

探测公式：h_i(key) = (h1(key) + i * h2(key)) % m 其中 h1(key) 是主哈希函数，h2(key) 是辅助哈希函数。 优点：探测序列比较均匀，能有效减少聚集。

方法二：链地址法

链地址法（Separate Chaining）：用数组 + 链表（或其他动态结构）的组合，让冲突元素'链'在一起。

原理： 哈希表底层是一个数组（称为'哈希桶数组'），每个数组元素对应一个链表。插入元素时，通过哈希函数计算 key 的哈希值，确定要放入数组的哪个'桶'。若已存在元素，就把新元素追加到链表末尾。

优缺点分析：

• 优点：冲突处理简单；空间灵活；无聚集问题。
• 缺点：遍历开销；额外空间。

基本操作

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

通过上面的学习我们知道了使用哈希函数要把关键字映射到数组的对应位置上，通常来说，关键字是整数的话进行映射计算会更方便。要是关键字本身不是整数，是 string、Date 等类型时，无法直接对 key 进行取模操作的话，我们要想办法把它转换成整数。

这时，我们需要为哈希表增加一个仿函数（也叫哈希函数对象），该仿函数的作用是，把 key 转换成一个可用于取模的整数。

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

/*------------------任务：定义哈希函数的'模板特化'------------------*/
template<>
struct HashFunc<string> {
    // 1.实现：'() 运算符的重载' ---> 作用：将 string 类型的变量转化为哈希值
    size_t operator()(const string& s) {
        // 1.定义 size_t 类型变量记录 string 类型的变量计算的哈希值
        size_t hash = 0;
        // 2.使用范围 for 循环遍历字符串并用 BKDR 算法计算其哈希值
        for (auto it : s) {
            // 2.1：先将字符的 ASCII 值累加到哈希值中
            hash += it;
            // 2.2：再让哈希值乘以质数 131（BKDR 哈希算法认为：131 可有效减少冲突）
            hash *= 131;
        }
        // 3.返回最终计算的哈希值
        return hash;
    }
};

一、开放定址法

在实践里，开放定址法的表现不如接下来要讲的链地址法。原因在于，开放定址法不管采用哪种冲突解决方式，都是占用哈希表自身的空间，这就使得各元素的存储始终存在相互影响的问题。

所以，对于开放定址法，我们简单选用线性探测的方式来实现即可。

哈希结构

/*------------任务：定义哈希表中节点的三种状态的'枚举'------------*/
enum State {
    EXIST, // 存在状态
    EMPTY, // 空状态
    DELETE // 删除状态
};

/*------------任务：定义哈希表存储的数据结构的'结构体模板'------------*/
template<class K, class V>
struct HashData {
    // 1.存储键值对类型的数据
    // 2.记录存储的节点的状态
    pair<K, V> _kv;
    State _state = EMPTY; // 节点的状态默认为空
};

/*------------任务：使用'开放地址法 - 线性探测'实现哈希表------------*/
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:
    /*------------------成员变量------------------*/
    // 1.存储 HashData 类型数据的数组
    // 2.记录哈希表中有效元素的变量
    vector<HashData<K, V>> _tables;
    size_t _n;
public:
    // …………
};

删除操作

要注意的是，这里需要给每个存储值的位置添加一个状态标识，否则删除某些值后，会影响后续冲突值的查找。例如，若删除 30，会导致查找 20 失败。但如果我们给每个位置设置 {EXIST, EMPTY, DELETE} 这样的状态标识，删除 30 时，就不用真正删除对应的值，而是把该位置状态改为 DELETE。如此一来，查找 20 时，只有遇到 EMPTY 状态才停止探测，就能顺利找到 20 了。

扩容操作

我们将哈希表的负载因子控制在 0.7，当负载因子达到 0.7 后，就需要对哈希表进行扩容。扩容时我们依旧按照 2 倍的方式扩容，但同时要保证哈希表的大小始终为质数。

一种方案是 sgi 版本哈希表所用的方式，预先提供一个近似 2 倍递增的质数表，每次扩容时从质数表中选取合适的大小作为扩容后的哈希表大小。

/*------------------任务：实现'获取下一个 >=n 的质数的函数'---> '用于哈希表扩容'------------------*/
inline unsigned long _stl_next_prime(unsigned long n) {
    // 1.指定素数表的大小
    static const int __stl_num_primes = 28;
    // 2.定义素数表覆盖常见哈希表大小
    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
    };
    // 3.使用二分查找找到第一个 >=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);
    // 3.4：适合作为哈希表容量的质数
    return pos == last ? *(last - 1) : *pos;
}

二、链地址法

在开放定址法里，所有元素都会直接存放在哈希表中。而链地址法不同，数据不再直接存储于哈希表，哈希表的每个位置存的是一个指针。当没有数据映射到该位置时，指针为空。若有多个数据映射到同一位置，就把这些冲突数据链成链表，挂在哈希表对应位置下。

链地址法也常被叫做拉链法或者哈希桶。

哈希结构

/*------------------任务：定义'哈希表节点的结构体模板'------------------*/
template<class K, class V>
struct HashNode {
    /*------------------成员变量------------------*/
    // 1.存储的键值对
    // 2.下一个节点的指针
    pair<K, V> _kv;
    HashNode<K, V>* _next;

    /*------------------成员函数------------------*/
    // 1.实现：哈希桶节点的'构造函数'
    HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
};

/*------------------任务：定义'哈希表的类模板'------------------*/
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:
    /*------------------成员变量------------------*/
    // 1.存储 Node* 类型数据的数组
    // 2.记录哈希表中有效元素的变量
    vector<HashNode<K, V>*> _tables;
    size_t _n;
public:
};

扩容操作

开放定址法的负载因子必须小于 1，链地址法的负载因子则没有限制，可大于 1。负载因子越小，哈希冲突的概率越低，空间利用率也越低。负载因子越大，哈希冲突的概率越高，空间利用率也越高。STL 中的最大负载因子基本控制在 1，一旦大于 1 就会触发扩容，我们后续实现也采用这种方式。

代码实现

头文件

哈希表：HashTable.h

#pragma once
// 包含需要使用的头文件
#include <iostream>
#include <vector>
using namespace std;

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

/*------------------任务：定义哈希函数的'模板特化'------------------*/
template<>
struct HashFunc<string> {
    // 1.实现：'() 运算符的重载' ---> 作用：将 string 类型的变量转化为哈希值
    size_t operator()(const string& s) {
        // 1.定义 size_t 类型变量记录 string 类型的变量计算的哈希值
        size_t hash = 0;
        // 2.使用范围 for 循环遍历字符串并用 BKDR 算法计算其哈希值
        for (auto it : s) {
            // 2.1：先将字符的 ASCII 值累加到哈希值中
            hash += it;
            // 2.2：再让哈希值乘以质数 131（BKDR 哈希算法认为：131 可有效减少冲突）
            hash *= 131;
        }
        // 3.返回最终计算的哈希值
        return hash;
    }
};

/*------------------任务：实现'获取下一个 >=n 的质数的函数'---> '用于哈希表扩容'------------------*/
inline unsigned long _stl_next_prime(unsigned long n) {
    // 1.指定素数表的大小
    static const int __stl_num_primes = 28;
    // 2.定义素数表覆盖常见哈希表大小
    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
    };
    // 3.使用二分查找找到第一个 >=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);
    // 3.4：适合作为哈希表容量的质数
    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 {
        // 1.存储键值对类型的数据
        // 2.记录存储的节点的状态
        pair<K, V> _kv;
        State _state = EMPTY; // 节点的状态默认为空
    };

    /*------------任务：使用'开放地址法 - 线性探测'实现哈希表------------*/
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
    private:
        /*------------------成员变量------------------*/
        // 1.存储 HashData 类型数据的数组
        // 2.记录哈希表中有效元素的变量
        vector<HashData<K, V>> _tables;
        size_t _n;

    public:
        /*------------------成员变量（公有）------------------*/
        // 1.实现：'哈希表的构造函数'
        HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

        // 2.实现：'查找操作' ----> 查找键对应的数据，找到返回指针，未找到返回 nullptr
        HashData<K, V>* Find(const K& key) {
            /*--------------第一步：计算初始哈希位置--------------*/
            // 1.实例化哈希函数对象
            Hash hash;
            // 2.计算哈希值 + 对其取模计算初始位置
            size_t hash_0 = hash(key) % _tables.size();
            // 3.定义变量记录当前的探测位置
            size_t hash_i = hash_0;
            // 4.定义探测步长计数器
            size_t i = 1;

            /*--------------第二步：线性探测循环--------------*/
            while (_tables[hash_i]._state != EMPTY) {
                // 1.如果当前位置为 EXIST 且键匹配 ---> 找到了键为 key 的元素，返回该位置的指针
                if (_tables[hash_i]._state == EXIST && _tables[hash_i]._kv.first == key) {
                    return &_tables[hash_i];
                }
                // 2.进行线性探测计算下一个位置
                hash_i = (hash_0 + i) % _tables.size();
                // 3.探测步长自增
                ++i;
            }

            /*--------------第三步：--------------*/
            // '如果这个位置的状态为空 + 遇到 EMPTY 仍未找到' ---> 说明哈希表中并不存在键为 key 的元素
            return nullptr;
        }

        // 3.实现：'删除操作' ---> 删除键对应的数据，成功返回 true，未找到返回 false
        bool Erase(const K& key) {
            // 1.调用 Find 函数查找键 key 对应的目标的元素
            HashData<K, V>* ret = Find(key);
            // 2.判断是否找到的目标元素
            // 情况 1：找到了键为 key 的元素
            if (ret) {
                // 1.将该元素的状态设置为 DELETE（删除状态）
                ret->_state = DELETE;
                // 2.更新有效元素的数量
                --_n;
                // 3.删除成功返回 true 即可
                return true;
            }
            // 情况 2：未找到键未 key 的元素
            else {
                return false;
            }
        }

        // 4.实现：'插入操作'---> 插入键值对，成功返回 true，键已存在返回 false
        bool Insert(const pair<K, V>& kv) {
            /*----------------第一步：查重判断----------------*/
            // 1.使用 Find() 函数先检查键 kv.first 是否已经存在
            if (Find(kv.first)) {
                return false; // 当键 kv.first 已经存在时，插入失败
            }

            // 1.进行扩容的判断：负载因子（_n/_tables.size()）≥0.7 时扩容
            if (_n * 10 / _tables.size() >= 7) {
                /*----------------第二步：扩容操作----------------*/
                // 2.创建新哈希表，容量为大于当前 size 的最小质数（减少哈希冲突）
                HashTable<K, V, Hash> newHt;
                newHt._tables.resize(_stl_next_prime(_tables.size() + 1));

                // 3.遍历旧表，将所有 EXIST 状态的元素重新插入新表
                for (auto& htData : _tables) {
                    if (htData._state == EXIST) {
                        newHt.Insert(htData._kv); // 注意：需重新计算哈希值（因表长改变，取模结果不同）
                    }
                }
                // 4.交换新旧哈希表：旧表.swap(新表)
                _tables.swap(newHt._tables);
            }

            /*----------------第三步：初始位置----------------*/
            // 1.实例化哈希函数对象
            Hash hashFunc;
            // 2.计算哈希值 + 对其取模计算初始位置
            size_t hash_0 = hashFunc(kv.first) % _tables.size();
            // 3.定义变量记录当前的探测位置
            size_t hash_i = hash_0;
            // 4.定义探测步长计数器
            size_t i = 1;

            /*----------------第四步：线性探测----------------*/
            // 1.使用 while 循环第一个非 EXIST 位置（EMPTY 或 DELETE 均可，EXIST 需要继续寻找）
            while (_tables[hash_i]._state == EXIST) {
                // 2.进行线性探测计算下一个位置
                hash_i = (hash_0 + i) % _tables.size();
                // 3.探测步长自增
                ++i;
            }

            /*----------------第五步：插入数据----------------*/
            // 1.将键值对插入该位置
            _tables[hash_i]._kv = kv;
            // 2.将该位置的设置为 EXIST
            _tables[hash_i]._state = EXIST;
            // 3.更新哈希表中有效元素的数量
            ++_n;
            // 4.插入成功返回 true 即可
            return true;
        }
    };
}

链地址法：hash_bucket.h

#pragma once
#include "HashTable.h"
// 任务 8：使用'链地址法'实现哈希表
namespace hash_bucket {
    /*------------------任务：定义'哈希表节点的结构体模板'------------------*/
    template<class K, class V>
    struct HashNode {
        /*------------------成员变量------------------*/
        // 1.存储的键值对
        // 2.下一个节点的指针
        pair<K, V> _kv;
        HashNode<K, V>* _next;

        /*------------------成员函数------------------*/
        // 1.实现：哈希桶节点的'构造函数'
        HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
    };

    /*------------------任务：定义'哈希表的类模板'------------------*/
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
    private:
        /*------------------成员变量------------------*/
        // 1.存储 Node* 类型数据的数组
        // 2.记录哈希表中有效元素的变量
        vector<HashNode<K, V>*> _tables;
        size_t _n;

        /*------------------类型别名------------------*/
        // 1.重命名哈希表节点的类型：HashNode<K,V> ---> Node
        typedef HashNode<K, V> Node;

    public:
        /*------------------成员函数------------------*/
        // 1.实现：'哈希表的构造函数'
        HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

        // 2.实现：'哈希表的析构函数'
        ~HashTable() {
            // 1.遍历哈希表的每个桶
            for (size_t i = 0; i < _tables.size(); ++i) {
                // 2.获取当前桶的头节点指针，从第一个桶开始清理
                Node* current = _tables[i];
                // 3.遍历当前桶对应的链表，逐个释放节点内存
                while (current) {
                    // 3.1：提前保存当前节点的下一个节点指针
                    Node* next = current->_next;
                    // 3.2：释放当前节点的内存
                    delete current;
                    // 3.3：移动到下一个节点
                    current = next;
                }
                // 4.将当前桶的头节点指针置空
                _tables[i] = nullptr;
            }
        }

        // 3.实现：'查找操作'---> 根据键查找对应的节点，找到返回节点指针，未找到返回 nullptr
        Node* Find(const K& key) {
            // 1.实例化哈希函数对象
            Hash hashFunc;
            // 2.计算键的哈希值并取模，得到对应的桶索引
            size_t hash_i = hashFunc(key) % _tables.size();
            // 3.获取对应桶的头节点，开始遍历链表
            Node* current = _tables[hash_i];

            // 4.遍历当前桶对应的链表
            while (current) {
                // 4.1 检查当前节点的键是否匹配目标 key
                if (current->_kv.first == key) {
                    return current;
                }
                // 4.2 若不匹配，移动到链表的下一个节点
                else {
                    current = current->_next;
                }
            }
            // 5.遍历完链表后仍未找到匹配的键，返回 nullptr
            return nullptr;
        }

        // 4.实现：'删除操作'---> 根据键删除哈希表中的节点，成功返回 true，失败返回 false
        bool Erase(const K& key) {
            // 1.计算键的哈希值，确定所在桶
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            // 2.定义一个指向桶的头节点的指针
            Node* curr = _tables[hash_i];
            // 3.定义一个指向当前节点的前驱节点的指针
            Node* prev = nullptr;

            // 3.遍历当前桶的链表
            while (curr) {
                // 4.找到目标节点
                if (curr->_kv.first == key) {
                    // 4.2：处理待删除节点
                    if (prev == nullptr) {
                        // 情况 1：待删除节点是桶的头节点
                        _tables[hash_i] = curr->_next;
                    } else {
                        // 情况 2：待删除节点在链表中间或末尾
                        prev->_next = curr->_next;
                    }
                    // 4.3：释放节点内存
                    delete curr;
                    // 4.4：有效元素数量减一
                    --_n;
                    // 4.5：删除成功
                    return true;
                }
                // 5.未找到目标节点，继续遍历
                prev = curr;
                curr = curr->_next;
            }
            // 6.遍历结束仍未找到目标节点，删除失败
            return false;
        }

        // 5.实现：'插入操作'---> 插入键值对，成功返回 true，键已存在返回 false
        bool Insert(const pair<K, V>& kv) {
            /*----------------第一步：查重判断----------------*/
            // 1.使用 Find() 函数判断键 kv.first 是否已经存在
            if (Find(kv.first)) {
                return false; // 当键 kv.first 已经存在时，插入失败
            }

            /*----------------第二步：扩容操作----------------*/
            // 1.进行扩容判断：负载因子（元素数/桶数）等于 1 时触发扩容
            if (_n == _tables.size()) {
                // 2.创建新数组，容量为大于当前 size 的最小质数
                vector<Node*> newVector(_tables.size() * 2);
                // 3.使用 for 循环变量的旧表中的所有桶
                for (size_t i = 0; i < _tables.size(); i++) {
                    // 4.定义一个指针指向当前节点的指针
                    Node* current = _tables[i];
                    // 5.遍历链表
                    while (current) {
                        // 6.定义一个指针指向当前节点的下一个节点的指针
                        Node* next = current->_next;
                        // 7.实例化哈希函数
                        Hash hashFunc;
                        // 8.重新计算'遍历到节点'在新表中的桶索引
                        size_t hash_i = hashFunc(current->_kv.first) % newVector.size();
                        // 9.使用头插法将当前节点插入新表对应桶的头部
                        current->_next = newVector[hash_i];
                        newVector[hash_i] = current;
                        current = next;
                    }
                    // 10.清空旧表的当前桶
                    _tables[i] = nullptr;
                }
                // 11.交换新旧哈希表
                _tables.swap(newVector);
            }

            /*----------------第三步：插入数据----------------*/
            // 1.创建新节点
            Node* newNode = new Node(kv);
            // 2.实例化哈希函数
            Hash hashFunc;
            // 3.计算'新插入数据'的哈希值/桶索引
            size_t hash_i = hashFunc(kv.first) % _tables.size();
            // 4.1：头插第一步
            newNode->_next = _tables[hash_i];
            // 4.2：头插第二步
            _tables[hash_i] = newNode;
            // 5.更新新表中有效元素的数量
            ++_n;
            // 6.插入成功返回 true 即可
            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);
    bool erase3 = ht.Erase(3); // 删除不存在的键
    printTestResult("删除不存在的键 3", !erase3);

    /*--------------------扩容测试--------------------*/
    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");
    cout << "开放寻址法哈希表测试完毕" << endl;
}

/*-----------------------测试：链地址法哈希表-----------------------*/
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);
    bool erase3 = ht.Erase("orange"); // 删除不存在的键
    printTestResult("删除不存在的 orange", !erase3);

    /*--------------------扩容测试--------------------*/
    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);
    cout << "链地址法哈希表测试完毕" << endl;
}

// 自定义日期结构体 ---> 用于测试复杂类型的哈希
struct Date {
    /*-------------------成员变量-------------------*/
    int _year;
    int _month;
    int _day;

    /*-------------------成员函数-------------------*/
    // 1.实现：日期类的'构造函数'
    Date(int year = 1, int month = 1, int day = 1) : _year(year), _month(month), _day(day) {}

    // 2.实现：'自定义相等比较'（哈希表需要判断键是否相等）
    bool operator==(const Date& d) const {
        return _year == d._year && _month == d._month && _day == d._day;
    }
};

// 自定义日期的哈希函数（模仿 BKDR 算法）
struct DateHashFunc {
    // 1.实现：'运算符 () 的重载' ---> 作用：用于计算日期类对象的哈希值
    size_t operator()(const Date& d) {
        // 1.定义 size_t 类型的变量记录日期类对象计算的哈希值
        size_t hash = 0;
        // 2.分步哈希，减少冲突概率
        hash += d._year; hash *= 131;
        hash += d._month; hash *= 131;
        hash += d._day; hash *= 131;
        // 3.返回最终计算的哈希值
        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;
}

运行结果