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

• key：是待映射的关键字。
• m：是哈希表的大小。（通常是数组长度，决定了哈希地址的范围）
• H(key)：是计算出的哈希地址。

本质：利用取余运算的'截断'特性，把任意整数 key 映射到 [0, m-1] 区间，让关键字适配哈希表的下标范围。

关键特性与优缺点：

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

优化：m 的选取原则

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

乘法散列法

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

核心公式与基本原理：

h(key) = floor(m * (key * A mod 1))

• key：是要进行哈希计算的关键字。
• A：是一个常数。（取值范围在 (0, 1) 之间，通常取黄金分割数 0.618...）
• m：是哈希表的大小。
• mod 1：表示取小数部分。
• floor：是向下取整符号。

关键特性与优缺点：

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

全域散列法

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

基本概念： 在普通的哈希函数设计中，如果哈希函数选择不当，可能会出现一些极端情况。全域散列的核心思想是从一个哈希函数族中随机选择哈希函数，使得对于任意给定的关键字集合，哈希冲突的概率都被控制在一个较低的水平。

核心原理： 全域散列法基于一个哈希函数族 H，这个函数族包含了多个不同的哈希函数。在使用全域散列时，会从这个函数族中随机选择一个哈希函数 h 来进行哈希操作。

从数学角度来说，对于任意两个不同的关键字 x 和 y，哈希函数族 H 满足：

|{h ∈ H : h(x) = h(y)}| / |H| ≤ 1/m

也就是说，从哈希函数族中随机选取一个哈希函数，使得两个不同关键字哈希值相同（产生冲突）的概率不超过 1/m。

二、负载因子

1. 什么是负载因子？

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

负载因子的定义：哈希表中已存储的元素数量 / 哈希表的总容量（桶的数量）。

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

• n：是哈希表中当前存储的有效元素数量。
• m：是哈希表的总容量。

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

对哈希表性能的影响： 负载因子是哈希冲突概率和内存利用率的'平衡器'，核心影响如下：

1. 负载因子越小 → 哈希冲突概率越低：当 λ → 0（如：哈希表很空），每个桶的平均元素数少，链表/探测链短，插入、查找、删除的时间复杂度接近 O(1)。但内存浪费严重。
2. 负载因子越大 → 哈希冲突概率越高：当 λ → 1（如：哈希表快满），桶的平均元素数多，链表/探测链长，操作时间复杂度会退化到 O(n)。内存利用率高，但性能暴跌。

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

负载因子驱动的扩容流程： 当负载因子超过阈值时，哈希表会触发扩容（Resize），流程如下：

1. 新建更大的桶数组：新容量通常是原容量的 2 倍（或接近的质数，依实现而定）。
2. 重新映射所有元素：遍历旧哈希表的所有元素，用新哈希函数（或新容量重新取模）将元素插入新桶。
3. 释放旧内存：销毁旧桶数组，替换为新桶数组。

三、哈希冲突

哈希冲突（Hash Collision）：是哈希表设计与实现中无法避免的核心问题，指不同的关键字通过哈希函数计算后，得到相同的哈希地址的情况。（即：映射到哈希表的同一个桶或位置）。

定义：对于两个不同的关键字 key1 ≠ key2，若它们的哈希值满足 h(key1) = h(key2)，则称这两个关键字发生了哈希冲突。

本质：哈希函数是'多对一'的映射（输入空间无限，输出空间有限），根据鸽巢原理，冲突必然存在。

产生冲突的因素：

1. 哈希函数的'压缩映射'特性：哈希函数将任意长度的输入映射到固定长度的哈希值，再通过取模等操作映射到哈希表的桶索引，这种'压缩'必然导致不同输入映射到同一输出。
2. 哈希表容量与关键字分布：若哈希表容量 m 过小，或关键字分布集中，冲突概率会急剧上升。

四、冲突处理

方法一：开放定址法

开放定址法（Open Addressing）：开放定址法是处理哈希冲突的一种系统化方法，所有元素都存储在哈希表数组本身中（而不是像链地址法那样使用额外的数据结构），通过探测序列寻找可用的空槽位。它的核心思路是：当发生哈希冲突时，按照预定的探测规则在哈希表中寻找下一个空闲位置来存储冲突的元素。

开放定址法的原理： 假设哈希表的大小为 m，哈希函数为 h(key)，当通过哈希函数计算出的地址 h(key) 已经被占用，即发生冲突时，开放定址法会使用一个探测序列 h_i(key)（i = 0, 1, 2,...）来寻找下一个空闲位置，直到找到可以插入的位置或者确定哈希表已满。探测序列的计算方式决定了开放定址法的具体类型。

线性探测

线性探测（Linear Probing）：

• 探测公式：h_i(key) = (h(key) + i) % m，其中 i = 0, 1, 2,...
• 说明：在发生冲突时，从冲突位置开始，依次探测下一个位置（如果到达表尾则回到表头）。
• 缺点：容易产生'聚集'（或叫'堆积'）现象。即连续的若干个位置被占用，导致后续插入元素时需要探测多个位置，降低插入和查找效率。

二次探测

二次探测（Quadratic Probing）：

• 探测公式：h_i(key) = (h(key) + c1 * i + c2 * i * i) % m。通常取 c1 = 0，c2 = 1，即 h_i(key) = (h(key) + i * i) % m。
• 说明：在发生冲突时，从发生冲突的位置开始，按照二次方的步长，向右进行跳跃式探测，直至找到下一个未存储数据的位置。
• 优点：相较于线性探测，二次探测能减少聚集现象，使元素在哈希表中分布得更均匀。
• 缺点：不能探测到哈希表中的所有位置。当 m 不满足某些条件（如：m 不是 4 的倍数加 1 时），可能会出现有的位置永远无法被探测到的情况。

双重散列

双重哈希（Double Hashing）：

• 探测公式：h_i(key) = (h1(key) + i * h2(key)) % m。其中 h1(key) 是主哈希函数，h2(key) 是辅助哈希函数且 h2(key) 的值不能为 0。
• 说明：在发生冲突时，通过主哈希函数和辅助哈希函数共同计算探测位置。
• 优点：探测序列比较均匀，能有效减少聚集，性能表现较好。

双重哈希的核心逻辑： 当第一个哈希函数计算的位置发生冲突时，通过第二个哈希函数生成一个与 key 相关的偏移量，不断向后探测，直到找到哈希表中未被占用的位置。

偏移量 h2(key) 的约束： 为保证探测能覆盖哈希表的所有位置，h2(key) 需满足两个条件：

1. h2(key) < M（偏移量不能超过哈希表大小）。
2. h2(key) 与 M 互质（即 gcd(h2(key), M) = 1）。

h2(key) 的简单取值方法：

1. 当 M 是 2 的整数次幂时：从 [0, M-1] 中任选一个奇数作为 h2(key)。
2. 当 M 是质数时：直接计算：h2(key) = key % (M - 1) + 1。

互质的必要性（关键原理）： 若 h2(key) 与 M 不互质，探测的位置会无法覆盖整个哈希表，导致部分空闲位置永远无法被找到。

总结：双重哈希的价值 双重哈希通过两个哈希函数和互质约束，让探测序列更均匀地覆盖哈希表，避免了线性探测的'聚集问题'。相比其他探测方法（如：线性探测、二次探测），双重哈希的冲突解决效率更高，适合对性能要求严格的场景。

方法二：链地址法

链地址法（Separate Chaining）（也叫拉链法、哈希桶法）：是哈希表解决哈希冲突的经典方案之一。它的核心思路是：用数组 + 链表（或其他动态结构）的组合，让冲突元素'链'在一起，既简单又高效。

链地址法的原理： 哈希表底层是一个数组（称为'哈希桶数组'），每个数组元素对应一个链表/动态结构（如：链表、红黑树、跳表）。

• 插入元素时：通过哈希函数计算 key 的哈希值，确定要放入数组的哪个'桶'（即：数组索引）。若该桶对应的链表为空，直接插入；若已存在元素（发生冲突），就把新元素追加到链表末尾。
• 查找/删除元素时：先通过哈希函数找到对应桶，再遍历链表逐个匹配 key。

优缺点分析：

• 优点：冲突处理简单；空间灵活（负载因子可大于 1）；无聚集问题。
• 缺点：遍历开销（若某个桶的链表过长，查找/删除会退化为 O(n)）；额外空间（链表节点需要存储指针）。

基本操作

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

通过上面的学习我们知道了使用哈希函数要把关键字映射到数组的对应位置上，通常来说，关键字是整数的话进行映射计算会更方便。

要是关键字本身不是整数，是 string、Date 等类型时，无法直接对 key 进行取模操作的话，我们要怎么做呢？

没错那就得想办法把它转换成整数，但是这要怎么实现呢？

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

• 若 key 本身能较方便地转换为整数，且转换后不易引发哈希冲突，直接使用哈希表默认的仿函数参数即可。
• 若 key 无法直接转换为整数，就需要我们自行实现一个仿函数，并传递给哈希表。

实现这类仿函数的核心要求是：让 key 的每个部分（字符、字段等）都参与计算，尽可能保证不同 key 转换后的整数值互不相同。

由于 string 作为哈希表的 key 十分常见，我们可以针对性地对 string 类型做特化处理（即：专门为 string 设计更适配的哈希转换逻辑）。

/*------------------任务：定义哈希表函数的'结构体模板'------------------*/
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 倍的方式扩容，但同时要保证哈希表的大小始终为质数。

然而，初始大小是质数，扩容 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 的素数
    // 3.1：使用一个指针指向素数表中的'第一个素数'
    const unsigned long* first = _stl_prime_list;
    // 3.1：使用一个指针指向素数表中的'最后一素数的下一位置'
    const unsigned long* last = _stl_prime_list + __stl_num_primes;
    // 3.3：使用 lower_bound() 接口函数求出第一个 >=n 的素数
    const unsigned long* pos = lower_bound(first, last, n);
    // 3.4：适合作为哈希表容量的质数
    return pos == last ? *(last - 1) : *pos;
    /* * 说明遍历完质数表，所有预定义的质数都比 n 小
     * 此时返回最大的质数 *(last - 1)，因为 last 是数组末尾的下一个位置，last - 1 指向最后一个有效质数 */
}

二、链地址法

在开放定址法里，所有元素都会直接存放在哈希表中。

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

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

哈希结构

/*------------------任务：定义'哈希表节点的结构体模板'------------------*/
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) {
    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;

    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);

    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);

    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;

    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);

    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);

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