哈希表

1. 哈希表

哈希表（Hash Table）是一种高效的数据结构，用于存储键值对（Key-Value Pair）。它通过哈希函数将键映射到数组中的特定位置，从而实现快速的插入、删除和查找操作。在 C++ 的标准模板库（STL）中，有多个容器基于哈希表实现，它们为开发者提供了高效的数据存储和查找方式：

  1. std::unordered_map和std::unordered_set
  2. std::unordered_multimap 和 std::unordered_multiset

作为一名专业的 C++ 程序员，我们不应仅仅满足于表面的认知，而要深入探寻事物背后的原理。就如同我们即将研究哈希表的底层实现一样，在开启这段深入探究之旅前，我们很有必要先了解一些关于哈希表的基础概念。这样一来，我们就能搭建起一个扎实的知识框架，为后续更深入地剖析哈希表的底层奥秘做好充分准备。

1.1 哈希函数

哈希函数是哈希表的核心所在，它具备强大的功能，能够把任意大小的数据（即键）精准地映射为固定大小的数据，而这种固定大小的数据通常表现为整数。在理想的情形下，哈希函数理应满足以下几个至关重要的条件：

  1. 均匀分布特性

    哈希函数所生成的哈希值需要在数组中实现均匀分布。均匀分布的意义十分重大，它能够有效减少冲突的发生概率。一旦冲突频繁出现，哈希表的性能将会大打折扣，查找、插入和删除等操作的效率都会显著降低。

  2. 高效计算能力

    哈希函数的计算过程应当尽可能地快速。在实际应用场景中，哈希表往往需要处理大量的数据，而且这些操作可能会被频繁地执行。它必须确保哈希表在高负载的情况下依然可以快速、稳定地运行，为用户提供高效的数据处理服务。

哈希函数算法丰富多样，每一种都具备独特的特性与适用场景。接下来，为大家详尽地介绍一些常见的哈希函数算法：

除留余数法

除留余数法的核心思想是通过将键值除以一个特定的正整数，然后取其余数作为哈希值。这个余数会被用作哈希表数组的索引，从而确定键值对应的元素在哈希表中的存储位置。

设key为要进行哈希处理的键值，m为哈希表的大小（通常是一个正整数），那么通过除留余数法得到的哈希值h(key)可以用公式表示为：h(key)= key % p，即求余数。·

除留余数法实现简单，计算速度快。但p的选择很关键，通常p会选取不大于m的质数（素数），以保证哈希值更均匀分布，减少冲突。

1
2
3
4
5
// 除留余数法哈希函数
int hashFunction(int key, int p) 
{
    return key % p;
}

乘法哈希法

乘法哈希法的基本思想是先将关键字 key 乘以一个介于 0 到 1 之间的常数 A，提取结果的小数部分，再将这个小数部分乘以哈希表的大小 m，最后取结果的整数部分作为哈希地址 h(key)。其公式可以表示为：h(key) = ⌊m × (key × A % 1)⌋，符号⌊ ⌋表示向下取整。

常数 A 的选择对哈希函数的性能有重要影响。理论上，A可以取满足0<A<1的任意值，但一些特殊的值可以使哈希结果更加均匀分布。一个常用的经验值是A≈0.6180339887，这个值也被称为黄金分割比。使用黄金分割比作为 A 的值，能在很多情况下使哈希函数的性能较好，让关键字均匀地分布在哈希表中。

1
2
3
4
5
6
// 乘法哈希法
int multiplicationHash(int key, int m) 
{
    const double A = (std::sqrt(5) - 1) / 2;
    return static_cast<int>(m * ((key * A) - static_cast<int>(key * A)));
}
  • 首先，计算 key * A 的小数部分，通过 (key * A) - static_cast<int>(key * A) 实现。
  • 然后，将小数部分乘以哈希表的大小 m，并将结果转换为整数类型，得到最终的哈希地址。

平方取中法

平方取中法先将关键字进行平方运算，然后取平方结果的中间若干位作为哈希地址。之所以采用这种方法，是因为一个数平方后的中间几位通常会更均匀地依赖于该数的每一位，这样能在一定程度上减少哈希冲突的发生，使得哈希值在哈希表中分布得更为均匀。

平法取中法的处理步骤如下:

  1. 计算平方：对给定的关键字进行平方操作。

  2. 确定位数：根据哈希表的大小m，确定需要从平方结果中取出的位数r。一般通过不等式2r≥m来确定r的值（若采用十进制，可类比为10r≥m），以保证取出的位数所表示的数值范围能够覆盖哈希表的所有地址。

  3. 提取中间位：从平方结果中提取中间的r位作为哈希地址。若平方结果的位数为偶数，中间r位的选取方式相对直观；若为奇数，中间位的定义可能会根据具体实现有所不同，通常选取最中间及其相邻的若干位。

  4. 处理超出范围：如果提取的中间r位所表示的数值超出了哈希表的大小m，可以通过取模运算（即对 m取余）将其映射到哈希表的有效地址范围内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 平方取中法哈希函数
int midSquareHash(int key, int tableSize) 
{
    long long squared = static_cast<long long>(key) * key;
    std::string squaredStr = std::to_string(squared);
    int r = 0;
    int temp = tableSize - 1;
    while (temp > 0) 
    {
        r++;
        temp /= 10;
    }
    int mid = squaredStr.length() / 2;
    int start = mid - r / 2;
    if (start < 0)
    {
        start = 0;
    }
    std::string hashStr = squaredStr.substr(start, r);
    int hashValue = std::stoi(hashStr);
    return hashValue % tableSize;
}
  • 首先计算关键字 key 的平方，为了避免溢出，使用 long long 类型存储结果。
  • 将平方结果转换为字符串 squaredStr，方便后续提取中间的若干位。
  • 确定需要提取的位数 r，通过不断除以 10 来计算 tableSize - 1 的位数。
  • 计算平方结果字符串的中间位置 mid 和提取的起始位置 start。
  • 使用 substr 函数从平方结果字符串中提取中间的 r 位，存储在 hashStr 中。
  • 将提取的字符串 hashStr 转换为整数 hashValue。
  • 最后通过取模运算确保哈希值在哈希表大小范围内。

折叠法

折叠法的基本思想是把一个较长的关键字分割成位数相同的若干部分（最后一部分的位数可以不同），然后将这些部分进行相加，根据哈希表的大小对相加结果进行适当处理（通常是取模运算），从而得到哈希地址。通过这种方式，能将长关键字映射到哈希表的地址空间内，并且在一定程度上使哈希值分布得更均匀，减少哈希冲突。

折叠法主要分为两种类型：

  1. 移位折叠：将分割后的各部分按照原来的顺序依次排列，然后进行相加。就像把关键字的各部分依次“拼接”在一起后求和。

  2. 边界折叠：将分割后的各部分中，除了第一个部分外，其余部分进行反转后再相加。可以理解为部分部分的顺序被颠倒后再求和。

处理过程分为以下几个步骤：

  1. 分割关键字：依据预先设定的位数，把较长的关键字分割成若干部分。

  2. 处理各部分：

    • 对于移位折叠，直接将各部分相加。

    • 对于边界折叠，除第一个部分外，将其余部分反转后再相加。

  3. 取模运算：将相加的结果对哈希表的大小取模，得到最终的哈希地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 移位折叠法
int shiftFolding(int key, int tableSize, int partLength) 
{
    std::string keyStr = std::to_string(key);
    std::vector<int> parts;
    for (size_t i = 0; i < keyStr.length(); i += partLength) 
    {
        std::string partStr = keyStr.substr(i, partLength);
        parts.push_back(std::stoi(partStr));
    }
    int total = 0;
    for (int part : parts) 
    {
        total += part;
    }
    return total % tableSize;
}

// 边界折叠法
int boundaryFolding(int key, int tableSize, int partLength) 
{
    std::string keyStr = std::to_string(key);
    std::vector<int> parts;
    for (size_t i = 0; i < keyStr.length(); i += partLength) 
    {
        std::string partStr = keyStr.substr(i, partLength);
        if (i > 0) 
        {
            std::reverse(partStr.begin(), partStr.end());
        }
        parts.push_back(std::stoi(partStr));
    }
    int total = 0;
    for (int part : parts) 
    {
        total += part;
    }
    return total % tableSize;
}

  • 移位折叠函数 shiftFolding

    1. 关键字转换与分割：

      • 首先将整数 key 转换为字符串 keyStr，方便进行分割操作。
      • 通过循环，按照 partLength 长度将 keyStr 分割成多个子字符串，将这些子字符串转换为整数并存储在 parts 向量中。

    2. 求和：遍历 parts 向量，将各部分相加得到总和 total。

    3. 取模运算：将总和 total 对 tableSize 取模，得到最终的哈希值。

  • 边界折叠函数 boundaryFolding

    其步骤与移位折叠类似，但在处理每个部分时，除了第一个部分外，会将其余部分的字符串进行反转，然后再转换为整数存储到 parts 向量中，后续的求和与取模操作相同。

举个例子：假设哈希表大小 m=1000，关键字 key=123456789，设定分割位数为 3 位。

移位折叠

  • 分割关键字：123、456、789。
  • 各部分相加：123 + 456 + 789 = 1368。
  • 取模运算：1368  % 1000 = 368，所以哈希地址为 368。

边界折叠

  • 分割关键字：123、456、789。
  • 部分反转并相加：123 + 654 + 987= 1764 。
  • 取模运算：1764  % 1000 = 764，哈希地址为 764。

1.2 哈希冲突

哈希冲突（也称为哈希碰撞）是指通过哈希函数将不同的键（Key）映射到哈希表的同一索引位置的现象。哈希函数的作用是将任意大小的数据（键）转换为固定大小的哈希值，这个哈希值通常会作为哈希表中的索引，用于快速查找、插入和删除数据。当产生哈希冲突之后，会对数据的存储、数据的操作性能、系统的稳定性和可靠性、算法的扩展性等方面产生非常严重的影响。

接下来，我将为大家详细地剖析哈希冲突产生的具体原因：

  1. 哈希空间有限

    哈希函数通常会将一个可能非常大的键空间映射到一个相对较小的哈希空间。例如，一个哈希表的大小为 n，那么哈希函数的输出范围通常是 0 到 n - 1。假设我们有 m 个不同的键需要存储在这个哈希表中，且 m > n，根据鸽巢原理，必然会有至少两个键被映射到同一个哈希值，从而产生冲突。

    示例：假设有一个大小为 10 的哈希表，使用简单的哈希函数 h(key) = key % 7 来计算键的哈希值。如果我们有键 9 和 16，计算它们的哈希值：

    • h(9) = 9 % 7 = 2

    • h(16) = 16 % 7 = 2

    可以看到，键 9 和 16 被映射到了同一个哈希值 2，这就产生了哈希冲突。

  2. 哈希函数设计不合理

    如果哈希函数不能均匀地将键分布到哈希空间中，就会导致某些哈希值被频繁使用，而其他哈希值很少被使用，从而增加了冲突的可能性。

    示例：图书馆使用哈希表来管理图书的借阅信息，每本图书有唯一的图书编号。

    采用 h(图书编号) = 图书编号的前两位数字 作为哈希函数。图书馆的图书编号可能是按照图书分类进行编排的，例如，文学类图书的编号前两位都是 01，那么所有文学类图书的借阅信息都会被映射到哈希表中对应 01 的位置。

  3. 数据分布不均匀

    即使哈希函数设计得很好，如果输入的数据本身具有某种规律性或聚集性，也可能导致哈希冲突。

    例如，如果输入的键大多是偶数，而哈希函数对奇偶性比较敏感，那么就可能会出现大量冲突。

哈希冲突会影响哈希表的性能，因为当发生冲突时，需要额外的处理来解决冲突，例如开放寻址法（线性探测、二次探测等）或链地址法（在每个哈希位置使用链表存储多个元素）。这些解决冲突的方法会增加查找、插入和删除操作的时间复杂度，降低哈希表的效率。因此，在设计哈希函数和哈希表时，需要尽量减少哈希冲突的发生。

1.3 负载因子

在哈希表中，负载因子（Load Factor）是一个衡量哈希表中元素填充程度的指标。它的计算方式是哈希表中已存储的元素数量（n）与哈希表的槽位数（m）的比值，用公式表示为：负载因子(α) = n / m。
其中，n 代表哈希表中实际存储的元素个数，m 代表哈希表的总槽位数（也可理解为哈希表数组的长度）。

例如，一个哈希表有 80个槽位，当前已经存储了 60 个元素，那么这个哈希表的负载因子就是 :

(α) = n/m = 60/80 = 3/4 = 0.75。

在实现哈希表时，底层必然会涉及到负载因子，这主要基于以下几点原因：

  1. 衡量哈希冲突的可能性

    • 负载因子与哈希冲突的发生概率密切相关。当负载因子较小时，意味着哈希表中的元素相对较少，槽位比较空闲，不同元素被映射到相同槽位的可能性就较低，哈希冲突发生的频率也会较低。

    • 随着负载因子的增大，哈希表中的元素不断增多，槽位逐渐被填满，元素被映射到同一槽位的概率就会显著增加，哈希冲突变得更加频繁。例如，当负载因子接近 1 甚至超过 1 时，哈希冲突会急剧增加，导致哈希表的性能大幅下降。

  2. 指导哈希表的动态扩容

    • 为了保证哈希表的性能，需要根据负载因子来决定是否对哈希表进行扩容。当负载因子达到一定阈值（这个阈值通常是根据具体的应用场景和哈希表的实现来设定的，常见的阈值为 0.75）时，就需要对哈希表进行扩容操作。

    • 扩容的过程通常是创建一个更大的新哈希表，将原哈希表中的所有元素重新计算哈希值并插入到新的哈希表中。通过扩容，可以降低负载因子，减少哈希冲突的发生，从而提高哈希表的查找、插入和删除操作的效率。

  3. 平衡空间和时间复杂度

    • 负载因子在哈希表的空间和时间复杂度之间起到平衡作用。如果负载因子设置得过低，虽然可以减少哈希冲突，提高操作效率，但会浪费大量的内存空间，因为哈希表中有很多空闲的槽位。

    • 相反，如果负载因子设置得过高，虽然可以节省内存空间，但会导致哈希冲突频繁发生，使得哈希表的操作时间复杂度增加，性能变差。因此，合理控制负载因子可以在空间和时间复杂度之间找到一个较好的平衡点，以满足不同应用场景的需求。

2. 开放寻址法

开放地址法（Open Addressing）是处理哈希表中哈希冲突的一种常见方法。当一个键通过哈希函数计算得到的槽位已经被占用时，通过某种规则（探测序列）在哈希表中继续寻找下一个可用的槽位，直到找到一个空槽或者确定哈希表已满为止。常用的探测方法有三种。

2.1 线性探测

线性探测是指当发生哈希冲突时，从冲突的槽位开始，依次检查下一个槽位，即按照顺序逐个向后查找空闲槽位。如果当前槽位为 h(k)（k为键），那么下一个探测的槽位为 (h(k)+1)  % m，再下一个为 (h(k)+2)  % m，以此类推，直到找到空闲槽位或遍历完整个哈希表，其中 m是哈希表的大小。

假设哈希表大小 m=19，哈希函数 h(k)=k  % 17，我们依次插入键 k1=34、k2=51、k3=1、k4=18、k5=35、k6=52。插入过程如下:

  1. 插入键 k1=34
    • 计算哈希值：h(34) = 34 % 17 = 0。
    • 由于槽位 0 为空，将键 k1 插入槽位 0。
  2. 插入键 k2=51
    • 计算哈希值：h(51) = 51 % 17 = 0。
    • 槽位 0 已被 k1 占用，发生哈希冲突。使用线性探测，检查 (0+1) % 19 = 1，槽位 1 为空，将键 k2 插入槽位 1。
  3. 插入键 k3=1
    • 计算哈希值：h(1) = 1 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。使用线性探测，检查 (1+1) % 19 = 2，槽位 2 为空，将键 k3 插入槽位 2。
  4. 插入键 k4=18
    • 计算哈希值：h(18) = 18 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。使用线性探测，依次检查：
      • 第一个探测槽位：(1+1) % 19 = 2，槽位 2 已被 k3 占用。
      • 第二个探测槽位：(1+2) % 19 = 3，槽位 3 为空，将键 k4 插入槽位 3。
  5. 插入键 k5=35
    • 计算哈希值：h(35) = 35 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。使用线性探测，依次检查：
      • 第一个探测槽位：(1+1) % 19 = 2，槽位 2 已被 k3 占用。
      • 第二个探测槽位：(1+2) % 19 = 3，槽位 3 已被 k4 占用。
      • 第三个探测槽位：(1+3) % 19 = 4，槽位 4 为空，将键 k5 插入槽位 4。
  6. 插入键 k6=52
    • 计算哈希值：h(52) = 52 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。使用线性探测，依次检查：
      • 第一个探测槽位：(1+1) % 19 = 2，槽位 2 已被 k3 占用。
      • 第二个探测槽位：(1+2)  % 19 = 3，槽位 3 已被 k4 占用。
      • 第三个探测槽位：(1+3)  % 19 = 4，槽位 4 已被 k5 占用。
      • 第四个探测槽位：(1+4)  % 19 = 5，槽位 5 为空，将键 k6 插入槽位 5。

通过以上插入过程可以清晰看到，当多个键的哈希值相同时，线性探测会依次向后寻找空闲槽位进行插入。随着插入元素增多，哈希冲突可能会导致元素聚集，影响哈希表的性能。

2.2 二次探测

二次探测法是通过一系列二次方形式的偏移量来寻找下一个可用的位置。假设哈希函数为 H(k)，其中 k是关键字，当发生冲突时，依次探测的地址为：H(k, i) = (H(k) + i2) %  m 或者 H(k, i) = (H(k) − i2)  %  m ，其中 m 是哈希表的长度，(i=1,2,3,⋯)。

下面我们以哈希表大小 m=19，哈希函数 h(k)=k  % 17 为例，依次插入键 k1=34、k2=51、k3=1、k4=18、k5=35、k6=52 来展示二次探测的过程。

  1. 插入键 k1=34
    • 计算哈希值：h(34) = 34 % 17 = 0。
    • 由于槽位 0 为空，将键 k1 插入槽位 0。
  2. 插入键 k2=51
    • 计算哈希值：h(51) = 51 % 17 = 0。
    • 槽位 0 已被 k1 占用，发生哈希冲突。开始进行二次探测：
      • 第一次探测（i=1）：h(51, 1) = (h(51) + 12) % 19 = (0 + 1)  % 19 = 1。
    • 槽位 1 为空，将键 k2 插入槽位 1。
  3. 插入键 k3=1
    • 计算哈希值：h(1) = 1 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。进行二次探测：
      • 第一次探测（i=1）：h(1, 1) = (h(1) + 12) % 19 = (1 + 1)  % 19 = 2。
    • 槽位 2 为空，将键 k3 插入槽位 2。
  4. 插入键 k4=18
    • 计算哈希值：h(18) = 18 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。开始进行二次探测：
      • 第一次探测（i=1）：h(18, 1) = (h(18) + 12) % 19 = (1 + 1)  % 19 = 2，槽位 2 已被 k3 占用。
      • 第一次探测（i=2）：h(18, 2) = (h(18) + 22) % 19 = (1 + 4)  % 19 = 5。
    • 槽位 5 为空，将键 k4 插入槽位 5。
  5. 插入键 k5=35
    • 计算哈希值：h(35) = 35 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。开始进行二次探测：
      • 第一次探测（i=1）：h(35, 1) = (h(35) + 12) % 19 = (1 + 1)  % 19 = 2，槽位 2 已被 k3 占用。
      • 第二次探测（i=2）：h(35, 2) = (h(35) + 22) % 19 = (1 + 4)  % 19 = 5，槽位 5 已被 k4 占用。
      • 第三次探测（i=3）：h(35, 3) = (h(35) + 32) % 19 = (1 + 9)  % 19 = 10。
    • 槽位 10 为空，将键 k5 插入槽位 10。
  6. 插入键 k6=52
    • 计算哈希值：h(52) = 52 % 17 = 1。
    • 槽位 1 已被 k2 占用，发生哈希冲突。开始进行二次探测：
      • 第一次探测（i=1）：h(52, 1) = (h(52) + 12) % 19 = (1 + 1)  % 19 = 2，槽位 2 已被 k3 占用。
      • 第二次探测（i=2）：h(52, 2) = (h(52) + 22) % 19 = (1 + 4)  % 19 = 5，槽位 5 已被 k4 占用。
      • 第三次探测（i=3）：h(52, 3) = (h(52) + 32) % 19 = (1 + 9)  % 19 = 10，槽位 10 已被 k5 占用。
      • 第四次探测（i=4）：h(52, 4) = (h(52) + 42) % 19 = (1 + 16)  % 19 = 17。
    • 槽位 17 为空，将键 k6 插入槽位 17。

二次探测可以在一定程度上缓解线性探测中元素聚集的问题，但也可能存在二次聚集的情况，即不同的键在发生冲突后可能会探测到相同的位置。

2.3 双重哈希

双重哈希是使用两个不同的哈希函数来处理冲突。当发生冲突时，它不像线性探测或二次探测那样按照固定的模式（如线性递增或二次方递增）来寻找下一个可用位置，而是利用第二个哈希函数计算出一个偏移量，根据这个偏移量来探测下一个位置。设第一个哈希函数为 H1(k)，第二个哈希函数为 H2(k)，哈希表的大小为 m，当在 H1(k)位置发生冲突时，后续探测的位置计算公式为：Hi = (H1(k) + i × H2(k))  % m，其中 i=1,2,3,⋯。

注意事项：哈希函数 h2(k) 的值要与哈希表大小 m 互质（互质是指两个整数的最大公约数为 1），以保证在发生哈希冲突时，通过双重哈希的探测序列能够遍历哈希表中的每一个槽位。

常见的第二个哈希函数形式为 h2(k) = p - (k % p)，其中 p 是一个小于哈希表容量 m 的质数。由于 p 是质数，h2(k) 的结果范围是 [1, p]，只要 p 与 m 互质，那么 h2(k) 与 m 互质的概率就会比较高。通常可以选择一个接近 m 的质数作为 p。也可以根据业务场景自定义出更符合需求的哈希函数。

已知哈希表大小 m=19，第一个哈希函数 h1(k)=k  % 17。为了确保能遍历到哈希表中的所有槽位，第二个哈希函数 h2(k) 的值要与 m=19 互质，只要让第二个哈希函数的结果落在 [1, m - 1] 这个区间内，就可以保证其与 m 互质。这里我自定义一个哈希函数: h2(k) = 1 + (k  % 16)。

我们依次插入键 k1=34、k2=51、k3=1、k4=18、k5=35、k6=52 来展示双重哈希的过程。

  1. 插入键 k1=34
    • 计算哈希值：h(34) = 34 % 17 = 0。
    • 由于槽位 0 为空，将键 k1 插入槽位 0。
  2. 插入键 k2=51
    • 计算哈希值：h1(51) = 51 % 17 = 0，发现槽位 0 已被占用，发生冲突。
    • 计算哈希值：h2(51) = 1 + (51 % 16) = 1 + 3 = 4。
    • 开始进行双重哈希探测：
      • 第一次探测（i=1）：h(51, 1) = (h(51) + 1 * h2(51)) % 19 = (0 + 1 * 4)  % 19 = 4。
      • 槽位 4 为空，将键 k2 插入槽位 4。
  3. 插入键 k3=1
    • 计算哈希值：h1(1) = 1 % 17 = 1。
    • 槽位 1 为空，将键 k3 插入槽位 1。
  4. 插入键 k4=18
    • 计算哈希值：h(18) = 18 % 17 = 1，发现槽位 1 已被占用，发生冲突。
    • 计算哈希值：h2(18) = 1 + (18% 16) = 1 + 2 = 3。
    • 开始进行双重哈希探测：
      • 第一次探测（i=1）：h(18, 1) = (h(18) + 1 * h2(18)) % 19 = (1 + 1 * 3)  % 19 = 4，槽位 4 已被占用。
      • 第二次探测（i=2）：h(18, 2) = (h(18) + 2 * h2(18)) % 19 = (1 + 2 * 3)  % 19 = 7。
    • 槽位 7 为空，将键 k4 插入槽位 7。
  5. 插入键 k5=35
    • 计算哈希值：h(35) = 18 % 17 = 1，发现槽位 1 已被占用，发生冲突。
    • 计算哈希值：h2(35) = 1 + (35% 16) = 1 + 3 = 4。
    • 开始进行双重哈希探测：
      • 第一次探测（i=1）：h(35, 1) = (h(35) + 1 * h2(35)) % 19 = (1 + 1 * 4)  % 19 = 5。
    • 槽位 5 为空，将键 k4 插入槽位 5。
  6. 插入键 k6=52
    • 计算哈希值：h(52) = 52 % 17 = 1，发现槽位 1 已被占用，发生冲突。
    • 计算哈希值：h2(52) = 1 + (52% 16) = 1 + 4 = 5。
    • 开始进行双重哈希探测：
      • 第一次探测（i=1）：h(52, 1) = (h(35) + 1 * h2(52)) % 19 = (1 + 1 * 5)  % 19 = 6。
    • 槽位 6 为空，将键 k6 插入槽位 6。

通过双重哈希，我们可以有效地处理哈希冲突，并且在 h2(k) 与 m 互质的情况下，能够遍历到哈希表中的所有槽位。

2.4 代码实现

接下来，我们将运用开放寻址法来构建一个哈希表。在设计这个哈希表类时，我们会着重实现数据添加、数据获取以及数据删除这几个核心功能，以确保该哈希表具备高效且全面的数据管理能力。

定义哈希表类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 定义哈希表类
class HashTable 
{
public:
    enum class HashMode {Division, Multiplication, Square, Fold};
    enum class ProbeMode {Linear, Quadratic, DoubleHashing};
    HashTable(HashMode hash = HashMode::Division, ProbeMode probe = ProbeMode::Linear);

    optional<int> get(int key);
    void insert(int key, int value);
    void remove(int key);
    void print();

private:
    // 除留余数法
    int divisionHash(int key);
    // 乘法哈希法
    int multiplicationHash(int key);
    // 平方取中法哈希函数
    int midSquareHash(int key);
    // 边界折叠法
    int boundaryFolding(int key, int partLength = 2);
    int hashFunction(int key);

    ///////////////////////////// 探测方式 /////////////////////////////
    // 线性探测
    int linear(int index, int i);
    // 二次探测
    int quadratic(int index, int i);
    // 双重哈希
    int doubleHashing(int key, int index, int i);
    // 探测函数
    int probe(int key, int index, int i);
    void resize();    

private:
    int m_size;
    int m_capIndex;
    int m_capacity; 
    vector<optional<int>> m_keys;
    vector<optional<int>> m_values;
    const double m_loadFactor = 0.75;
    HashMode m_hashMode;
    ProbeMode m_probeMode;
    const vector<int> m_primeNums = { 2, 5, 11, 23, 47, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49193, 98387 };
};

哈希函数算法

在这个哈希表类中我们提供了四种哈希函数算法：除留余数法、乘法哈希法、平法取中法、边界折叠法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int HashTable::divisionHash(int key)
{
    return key % m_capacity;
}

int HashTable::multiplicationHash(int key)
{
    const double A = (sqrt(5) - 1) / 2;     // 黄金分割  0.6180339887
    return static_cast<int>(m_capacity * ((key * A) - static_cast<int>(key * A)));
}

int HashTable::midSquareHash(int key)
{
    long long squared = static_cast<long long>(key) * key;
    string squaredStr = to_string(squared);
    int r = 0;
    int temp = m_capacity - 1;
    while (temp > 0)
    {
        r++;
        temp /= 10;
    }
    int mid = squaredStr.length() / 2;
    int start = mid - r / 2;
    if (start < 0)
    {
        start = 0;
    }
    string hashStr = squaredStr.substr(start, r);
    int hashValue = stoi(hashStr);
    return hashValue % m_capacity;
}

int HashTable::boundaryFolding(int key, int partLength)
{
    string keyStr = to_string(key);
    vector<int> parts;
    for (size_t i = 0; i < keyStr.length(); i += partLength)
    {
        string partStr = keyStr.substr(i, partLength);
        if (i > 0)
        {
            reverse(partStr.begin(), partStr.end());
        }
        parts.push_back(stoi(partStr));
    }
    int total = 0;
    for (int part : parts)
    {
        total += part;
    }
    return total % m_capacity;
}

随后，我们借助 hashFunction 函数对哈希函数算法予以封装。在哈希表类里，会依据 m_hashMode 的取值来精准判定当前所采用的哈希算法，以此增强代码的模块化与可维护性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int HashTable::hashFunction(int key)
{
    int value = 0;
    switch (m_hashMode)
    {
    case HashMode::Division:
        value = divisionHash(key);
        break;
    case HashMode::Multiplication:
        value = multiplicationHash(key);
        break;
    case HashMode::Square:
        value = midSquareHash(key);
        break;
    case HashMode::Fold:
        value = boundaryFolding(key);
        break;
    default:
        value = divisionHash(key);
        break;
    }
    return value;
}

探测方式

当发生哈希冲突之后，哈希表类中提供了三种探测方式：线性探测、二次探测、双重哈希探测：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 线性探测
int HashTable::linear(int index, int i)
{
    return (index + i) % m_capacity; // 线性探测
}
// 二次探测
int HashTable::quadratic(int index, int i)
{
    return (index + i * i) % m_capacity;
}
// 双重哈希
int HashTable::doubleHashing(int key, int index, int i)
{
    int prime = m_primeNums[m_capIndex-1];
    int hash2 = prime - (key % prime);
    cout << "hash2 = " << hash2 << endl;
    return (index + i * hash2) % m_capacity;
}

与前文提及的哈希算法函数类似，这三种探测方式同样被封装进了一个名为 probe 的函数里。后续将依据 m_probeMode 的具体取值来决定选用哪种探测方式，以实现灵活、高效的探测操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int HashTable::probe(int key, int index, int i)
{
    if (m_probeMode == ProbeMode::Linear)
    {
        return linear(index, i);
    }
    else if (m_probeMode == ProbeMode::Quadratic)
    {
        return quadratic(index, i);
    }
    else
    {
        return doubleHashing(key, index, i);
    }
    return 0;
}

哈希表扩容

当哈希表内元素的填充程度超过负载因子 m_loadFactor 的设定值时，就有必要对哈希表进行扩容操作。新的哈希表容量将从类内部的素数表 m_primeNums 中选取。具体选用素数表中的哪一个数据，由 m_capIndex 负责精准控制，以此确保哈希表在扩容过程中能依据预设规则合理调整容量大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void HashTable::resize()
{
    m_capIndex++;   // 素数表指针
    if (m_capIndex >= m_primeNums.size()) 
    {
        cout << "素数表中已经没有可用数值用来扩容了...!" << endl;
        return;
    }
    vector<optional<int>> oldKeys = m_keys;
    vector<optional<int>> oldValues = m_values;
    // 数组扩容
    m_capacity = m_primeNums[m_capIndex];  
    m_keys = vector<optional<int>>(m_capacity);
    m_values = vector<optional<int>>(m_capacity);
    m_size = 0;
    // 重新哈希
    for (int i = 0; i < oldKeys.size(); ++i)
    {
        if (oldKeys[i].has_value()) 
        {
            insert(oldKeys[i].value(), oldValues[i].value());
        }
    }
}

数据获取和遍历

在哈希表类的构造函数中主要是对类成员变量进行初始化:

1
2
3
4
5
6
7
HashTable::HashTable(HashMode hash, ProbeMode probe) : m_size(0), m_capIndex(1), 
                                                       m_hashMode(hash), m_probeMode(probe)
{
    m_capacity = m_primeNums[m_capIndex];
    m_keys.resize(m_capacity);
    m_values.resize(m_capacity);
}

我们可以根据哈希键值对的键值 key来获取对应的value值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
optional<int> HashTable::get(int key)
{
    int index = hashFunction(key);
    int startIndex = index;
    for (int i=1; m_keys[index].has_value(); ++i) 
    {
        if (m_keys[index].value() == key) 
        {
            return m_values[index];
        }
        index = probe(key, startIndex, i);
        if (index == startIndex)    // 回到了起始位置
        {
            break;
        }
        cout << "find index = " << index << endl;
    }
    return nullopt;
}

对于哈希表中的数据，我们可以根据哈希数组的容量对里边的数据进行遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void HashTable::print()
{
    for (int i = 0; i < m_capacity; ++i) 
    {
        cout << "Index " << i << ": ";
        if (!m_keys[i].has_value()) 
        {
            cout << "EMPTY";
        }
        else 
        {
            cout << "(" << m_keys[i].value() << ", " << m_values[i].value() << ")";
        }
        cout << endl;
    }
}

数据的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void HashTable::insert(int key, int value)
{
    if ((double)m_size / m_capacity >= m_loadFactor)
    {
        resize();
    }
    int index = hashFunction(key);
    int start = index;
    for (int i=1; m_keys[index].has_value(); ++i)
    {
        if (m_keys[index].value() == key)
        {
            m_values[index] = value;
            return;
        }
        index = probe(key, start, i);
    }
    m_keys[index] = key;
    m_values[index] = value;
    m_size++;
}

数据的删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void HashTable::remove(int key)
{
    int index = hashFunction(key);
    int startIndex = index;
    for (int i = 1; m_keys[index].has_value(); ++i) 
    {
        if (m_keys[index].value() == key) 
        {
            m_keys[index] = nullopt;
            m_values[index] = nullopt;
            m_size--;
            return;
        }
        index = probe(key, startIndex, i);
        if (index == startIndex) 
        {
            break;
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int main() 
{
    HashTable ht(HashTable::HashMode::Division, HashTable::ProbeMode::Quadratic);
    ht.insert(34, 30);
    ht.insert(51, 50);
    ht.insert(1, 10);
    ht.insert(2, 25);
    ht.insert(3, 33);
    ht.insert(4, 45);
    ht.insert(5, 65);
    ht.insert(16, 85);
    ht.insert(18, 20);
    ht.insert(35, 40);
    ht.insert(52, 60);
    ht.insert(77, 70);
    ht.insert(99, 90);

    auto result = ht.get(99);
    if (result.has_value()) 
    {
        cout << "key = 99, value = " << result.value() << endl;
    }
    else 
    {
        cout << "没有找到 key 为 99 的 value 值!" << endl;
    }
    ht.remove(2);
    ht.print();
    return 0;
}

3. 链地址法

3.1 何为链地址法

链地址法（Chaining Addressing），也称为拉链法，是一种用于处理哈希表（Hash Table）中哈希冲突（Hash Collision）的经典方法。链地址法的核心思想是将所有哈希到同一位置的元素通过链表（或者其他数据结构，如红黑树等）连接起来，每个位置对应一个链表，当发生哈希冲突时，将新元素插入到该位置对应的链表中。

假设学校的图书馆要给每本图书分配一个存放位置，采用的方式是根据图书编号除以书架数量得到的余数来确定图书应该放在哪个书架上。这就类似于哈希表中使用哈希函数将键映射到特定位置。

比如图书馆有 5 个书架，编号为 0 - 4。现在有一些图书，它们的编号分别是 12、22、7、17、27。

  • 计算图书存放书架：

    • 对于编号为 12 的图书，12%5=2，所以它应该放在 2 号书架。
    • 编号为 22 的图书，22%5=2，同样也会被分配到 2 号书架，这里就发生了“哈希冲突”，就像不同的键被哈希函数映射到了同一个位置。
    • 编号为 7 的图书，7%5=2，还是要放在 2 号书架。
    • 编号为 17 的图书，17%5=2，依旧放在 2 号书架。
    • 编号为 27 的图书，27%5=2，还是放在 2 号书架。

  • 采用链地址法解决冲突：
    为了解决多个图书都要放在同一个书架的问题，图书馆管理员在每个书架上安装了多个挂钩，每个挂钩可以挂一个小袋子，把图书放在小袋子里，然后依次挂在挂钩上。这样，2 号书架就会挂着多个装有图书的小袋子，按照放入的顺序依次排列。就好比在哈希表中，每个位置对应一个链表，发生冲突的元素都被添加到这个链表中。

    通过上文的详细讲解不难发现，在应对哈希冲突问题时，链地址法所具备的优势极为显著的：

    1. 简单易实现：链地址法的实现相对简单，只需要在每个哈希位置维护一个链表即可。

    2. 处理冲突能力强：无论哈希冲突的情况多么严重，都可以通过链表存储所有冲突的元素，不会出现无法插入元素的情况。

    3. 动态性好：可以方便地插入、删除和查找元素，不需要对哈希表进行大规模的重建。

    然而，凡事皆有两面性，在享受链地址法带来的便利的同时，它所存在的弊端也不容小觑，对此我们必须要有清晰的认知：

    1. 空间开销大：除了存储元素本身，还需要额外的指针来维护链表，增加了空间开销。

    2. 查找效率可能降低：当链表过长时，查找元素的时间复杂度会接近O(n)，而不是理想的 O(1)。

    在使用链地址法解决哈希冲突的时候，为了提高其性能，可以从多个方面进行优化：

    1. 采用更高效的数据结构替代链表

      链表在查找、插入和删除操作时，平均时间复杂度为 O(n)，当链表过长时，性能会显著下降。可以考虑使用更高效的数据结构，如红黑树、跳表等。

    2. 动态扩容

      当哈希表的负载因子（元素数量与槽位数量的比值）过高时，哈希冲突的概率会大大增加，此时可以对哈希表进行动态扩容。

    3. 优化哈希函数

      一个好的哈希函数可以使元素更均匀地分布在哈希表中，减少冲突的发生。可以使用更复杂的哈希函数，如乘法哈希、全域哈希 等。

    4. 并发优化

      在多线程环境下，哈希表的并发访问可能会导致数据不一致的问题。可以采用一些并发控制机制来提高性能。

      • 分段锁：将哈希表分成多个段，每个段使用独立的锁，不同段的操作可以并发进行。
      • 无锁数据结构：使用原子操作和 CAS（Compare-And-Swap）等技术实现无锁的哈希表。

3.2 代码实现

当采用链地址法来实现哈希表类时，需要对上面运用开放地址法所定义的哈希表类做出相应修改。

定义哈希表类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 定义哈希表类
class LinkHashTable
{
public:
    enum class HashMode { Division, Multiplication, Square, Fold };
    LinkHashTable(HashMode hash = HashMode::Division);

    optional<int> get(int key);
    void insert(int key, int value);
    void remove(int key);
    void print();

private:
    // 除留余数法
    int divisionHash(int key);
    // 乘法哈希法
    int multiplicationHash(int key);
    // 平方取中法哈希函数
    int midSquareHash(int key);
    // 边界折叠法
    int boundaryFolding(int key, int partLength = 2);
    int hashFunction(int key);
    void resize();

private:
    int m_size;
    int m_capIndex;
    int m_capacity;     // 哈希表大小
    vector<list<pair<int, int>>> m_table;
    const double m_loadFactor = 0.75;
    HashMode m_hashMode;
    const vector<int> m_primeNums = { 2, 5, 11, 23, 47, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49193, 98387 };
};
  • m_table 现在是一个 std::vector<std::list<std::pair<int, int>>>，每个槽位存储一个链表，链表中的每个元素是一个键值对。
  • 哈希函数使用：哈希函数用于确定键应该插入到哪个槽位。

哈希函数算法

在当前的链式哈希表类中还是提供了四种哈希函数算法：除留余数法、乘法哈希法、平法取中法、边界折叠法，这部分内容和开放地址法对应的哈希表类的代码是相同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
int LinkHashTable::divisionHash(int key)
{
    return key % m_capacity;
}

int LinkHashTable::multiplicationHash(int key)
{
    const double A = (sqrt(5) - 1) / 2;     // 黄金分割  0.6180339887
    return static_cast<int>(m_capacity * ((key * A) - static_cast<int>(key * A)));
}

int LinkHashTable::midSquareHash(int key)
{
    long long squared = static_cast<long long>(key) * key;
    string squaredStr = to_string(squared);
    int r = 0;
    int temp = m_capacity - 1;
    while (temp > 0)
    {
        r++;
        temp /= 10;
    }
    int mid = squaredStr.length() / 2;
    int start = mid - r / 2;
    if (start < 0)
    {
        start = 0;
    }
    string hashStr = squaredStr.substr(start, r);
    int hashValue = stoi(hashStr);
    return hashValue % m_capacity;
}

int LinkHashTable::boundaryFolding(int key, int partLength)
{
    string keyStr = to_string(key);
    vector<int> parts;
    for (size_t i = 0; i < keyStr.length(); i += partLength)
    {
        string partStr = keyStr.substr(i, partLength);
        if (i > 0)
        {
            reverse(partStr.begin(), partStr.end());
        }
        parts.push_back(stoi(partStr));
    }
    int total = 0;
    for (int part : parts)
    {
        total += part;
    }
    return total % m_capacity;
}

int LinkHashTable::hashFunction(int key)
{
    switch (m_hashMode)
    {
    case HashMode::Division:
        return divisionHash(key);
    case HashMode::Multiplication:
        return multiplicationHash(key);
    case HashMode::Square:
        return midSquareHash(key);
    case HashMode::Fold:
        return boundaryFolding(key);
    default:
        return divisionHash(key);
    }
}

哈希表扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void LinkHashTable::resize()
{
    m_capIndex++;
    if (m_capIndex >= m_primeNums.size())
    {
        cout << "素数表中已经没有可用数值用来扩容了...!" << endl;
        return;
    }
    m_capacity = m_primeNums[m_capIndex];
    vector<list<pair<int, int>>> newTable(m_capacity);
    for (const auto& bucket : m_table)
    {
        for (const auto& pair : bucket)
        {
            int index = hashFunction(pair.first);
            newTable[index].emplace_back(pair);
        }
    }
    m_table = move(newTable);
}

数据获取和遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
LinkHashTable::LinkHashTable(HashMode hash) : m_size(0), m_capIndex(1), m_hashMode(hash)
{
    m_capacity = m_primeNums[m_capIndex];
    m_table.resize(m_capacity);
}

optional<int> LinkHashTable::get(int key)
{
    int index = hashFunction(key);
    for (const auto& pair : m_table[index])
    {
        if (pair.first == key)
        {
            return pair.second;
        }
    }
    return nullopt;
}

void LinkHashTable::print()
{
    for (int i = 0; i < m_capacity; ++i)
    {
        cout << "Bucket " << i << ": ";
        for (const auto& pair : m_table[i])
        {
            cout << "(" << pair.first << ", " << pair.second << ") ";
        }
        cout << endl;
    }
}

数据插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void LinkHashTable::insert(int key, int value)
{
    if (static_cast<double>(m_size) / m_capacity >= m_loadFactor)
    {
        resize();
    }
    int index = hashFunction(key);
    for (auto& pair : m_table[index])
    {
        if (pair.first == key)
        {
            pair.second = value;
            return;
        }
    }
    m_table[index].emplace_back(key, value);
    ++m_size;
}

数据删除

1
2
3
4
5
6
7
8
9
10
11
12
13
void LinkHashTable::remove(int key)
{
    int index = hashFunction(key);
    for (auto it = m_table[index].begin(); it != m_table[index].end(); ++it)
    {
        if (it->first == key)
        {
            m_table[index].erase(it);
            --m_size;
            return;
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main()
{
    LinkHashTable hashTable(LinkHashTable::HashMode::Division);
    hashTable.insert(1, 100);
    hashTable.insert(2, 200);
    hashTable.insert(3, 300);
    hashTable.insert(4, 400);
    hashTable.insert(5, 500);
    hashTable.insert(11, 110);
    hashTable.insert(12, 210);
    hashTable.insert(13, 310);
    hashTable.insert(14, 410);
    hashTable.insert(15, 510);

    auto value = hashTable.get(2);
    if (value)
    {
        cout << "Value for key 2: " << *value << endl;
    }

    hashTable.remove(2);
    value = hashTable.get(2);
    if (!value)
    {
        cout << "Key 2 not found." << endl;
    }

    hashTable.print();

    return 0;
}