【C++入门到精通】哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]

在这里插入图片描述

引言

在现代计算机科学和数据结构中，哈希（Hash）是一项重要而广泛应用的技术。通过将输入数据映射为固定长度的哈希值，哈希函数能够快速高效地进行数据存储、搜索和比较。然而，由于输入数据的多样性和哈希值的有限长度，哈希冲突成为了一个不可避免的问题。本文将介绍哈希概念、哈希冲突、哈希函数及其冲突解决方法，以及哈希在计算机科学中的应用。

通过对哈希概念、哈希冲突、哈希函数及其冲突解决方法以及哈希在计算机科学中的应用的深入研究，我们能够更好地理解和应用哈希技术，提高数据处理和存储的效率。接下来，让我们一起踏上哈希之旅吧！

一、哈希概念

哈希（Hash）是一种将任意长度的数据映射为固定长度值的算法。它是一种单向函数，即从哈希值无法反向推导出原始输入数据。哈希函数的设计目标是使不同的输入数据产生不同的哈希值，并且在相同的输入下始终生成相同的哈希值。哈希函数的输出通常称为哈希码、哈希摘要或哈希值。
在这里插入图片描述

🔴哈希函数具有以下特点和应用：

确定性：对于相同的输入，哈希函数总是生成相同的哈希值。这个特性使得哈希函数可以用于数据的唯一标识，例如文件校验和、消息摘要等。
不可逆性：从哈希值无法还原出原始输入数据。即使输入数据发生微小的改变，其哈希值也会有很大的差异。这种特性在密码存储、数字签名等场景中非常重要。
哈希冲突：不同的输入数据可能产生相同的哈希值，这就是哈希冲突。好的哈希函数应该最大程度地减少冲突的概率，以保证数据的唯一性。
哈希表：利用哈希函数将数据映射到数组中，可以实现高效的数据存储和检索。哈希表常用于实现字典、集合等数据结构，可以提供快速的元素查找和插入操作。
密码存储：在存储用户密码时，通常使用哈希函数对密码进行哈希计算，并将哈希值存储在数据库中。当用户登录时，输入的密码经过哈希计算后与存储的哈希值进行比较，用于验证密码的正确性。
数据完整性校验：通过对数据进行哈希计算，可以生成唯一的哈希值，用于验证数据在传输过程中是否被篡改。如果接收到的数据的哈希值与预期的哈希值不相符，则说明数据已被修改。

常见的哈希算法包括 MD5（Message Digest Algorithm 5）、SHA-1（Secure Hash Algorithm 1）、SHA-256 等。然而，由于计算能力的提升和哈希碰撞的可能性，一些传统的哈希函数已经不再被认为是安全的，因此在安全性要求较高的场景中，应选择更强大、抗碰撞能力更强的哈希算法。

总结来说，哈希是一种将任意长度的数据转换为固定长度值的算法，具有唯一性、不可逆性和高效性等特点。它在数据的唯一标识、数据完整性验证、密码存储等方面有广泛的应用。

二、哈希冲突

哈希冲突指的是不同的输入数据经过哈希函数计算后，产生了相同的哈希值。当两个或多个不同的输入数据生成相同的哈希值时，就发生了哈希冲突。

由于哈希函数将无限的输入域映射到有限的输出域，所以在理论上，哈希冲突是不可避免的。好的哈希函数应该尽量减少哈希冲突的概率，使其发生的概率非常低。如果哈希冲突的概率过高，将会降低哈希函数的效率和可靠性，因为哈希冲突可能会导致数据的错误匹配或冲突。

三、哈希函数

哈希函数是一种将输入数据映射为固定长度值（哈希值）的函数。它的设计目标是使不同的输入数据产生不同的哈希值，并且在相同的输入下始终生成相同的哈希值。

⭕哈希函数应具备的特点

确定性：对于相同的输入，哈希函数总是生成相同的哈希值。这个特性使得哈希函数可以用于数据的唯一标识，例如文件校验和、消息摘要等。
不可逆性：从哈希值无法还原出原始输入数据。即使输入数据发生微小的改变，其哈希值也会有很大的差异。这种特性在密码存储、数字签名等场景中非常重要。
均匀性：好的哈希函数应尽可能均匀地将输入数据映射到哈希值空间中，以减少哈希冲突的概率。
高效性：哈希函数应该具有高效的计算速度，能够快速生成哈希值。

⭕哈希函数设计原则

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值。
域必须在0到m-1之间。
哈希函数计算出来的地址能均匀分布在整个空间中。
哈希函数应该比较简单。

⭕常见的哈希函数

（1）直接定址法（重要）

它通过将关键字的某个线性函数作为哈希函数来计算哈希值。具体而言，直接定址法使用的哈希函数形式为

$H a s h (k ey) = a * k ey + b$

其中 a 和 b 是常数，key 是关键字。

直接定址法的思想是通过线性函数的计算，将关键字映射到哈希表的不同位置。不同的关键字可能会映射到相同的位置，这就导致了哈希冲突。当发生冲突时，直接定址法会尝试使用不同的线性函数参数 a 和 b 继续探测哈希表的下一个位置，直到找到一个空槽位来存储冲突的数据。

直接定址法的优点是简单、易于实现，并且不需要额外的数据结构来处理冲突。然而，直接定址法的缺点是当冲突发生时，可能会产生大量的聚集现象，即连续的数据会聚集在同一个区域。这样会导致哈希表的效率下降，因为查找和插入操作都需要对冲突链进行线性扫描。

（2）除留余数法（重要）

除留余数法（也称为取模法或取余法）是一种常见的哈希函数，用于将关键字映射到哈希表的索引位置。

除留余数法的基本原理是，将关键字除以一个正整数（通常是哈希表的大小），然后取余数作为哈希值。具体而言，假设哈希表的大小为 m，关键字为 key，则哈希函数可以表示为

$H a s h (k ey) = k ey (m o d) m$ (其中 mod 是取余操作)

除留余数法的优点是简单、快速，并且哈希值范围在 0 到 m-1 之间，恰好对应哈希表的索引位置。由于取余操作的特性，除留余数法对数据的分布并不敏感，即使数据不均匀分布，仍然可以得到较好的哈希结果。

然而，除留余数法也存在一些问题。如果选择的哈希表大小与数据集的特征相关，可能会导致冲突较多，影响查询和插入的效率。此外，当哈希表大小为质数时，可以更好地避免冲突，因为质数具有较好的随机性。

因此，在使用除留余数法时，需要根据具体的应用场景和数据集特征来选择合适的哈希表大小，以获得较好的性能和哈希冲突的抵抗能力。此外，除留余数法通常与其他解决哈希冲突的方法结合使用，例如链地址法、开放寻址法等，以进一步提高哈希表的效率和质量。

（3）平方取中法（了解）

它的基本思想是将关键字的平方值进行位运算，然后取中间的几位作为哈希值。

具体而言，假设关键字为 k，哈希表的大小为 m，则平方取中法的哈希函数可以表示为
$Hash(key) = (key^2 >> r)按位与(m-1)$
其中 >> 是右移操作，r 是一个常数，通常选取为关键字位数的一半。

平方取中法的优点是能够产生较好的随机性，即使数据分布不均匀也可以获得较好的哈希结果。此外，平方取中法对哈希表大小和质数并不敏感，因此选择合适的哈希表大小和质数不需要过多的考虑。

然而，平方取中法也存在一些问题。如果关键字的位数过少（例如只有几位），可能会导致哈希值重复的情况，影响哈希表的效率和质量。此外，平方取中法的计算过程比较复杂，可能会降低哈希函数的效率。

因此，在使用平方取中法时，需要根据具体的应用场景和数据集特征来选择合适的哈希函数和相关参数，以获得相对较好的哈希结果和性能。此外，平方取中法通常也会与其他解决哈希冲突的方法结合使用，例如链地址法、开放寻址法等，以提高哈希表的效率和质量。

（4）折叠法（了解）

折叠法是一种哈希函数设计方法，它可以将多个关键字的信息压缩到一个哈希值中。具体来说，折叠法将关键字分为若干段，对每一段进行相加或者相乘等操作，之后将这些操作的结果相加或相乘得到哈希值。

以下是一个简单的折叠法示例，假设我们要将关键字 1234567890 哈希到一个长度为 4 的哈希表中：

将 1234567890 拆分成两个数字段：12 和 34567890。
对这两个数字段进行相加操作：12 + 34567890 = 34567902。
将相加的结果再拆分成两个数字段：34 和 567902。
对这两个数字段再进行相加操作：34 + 567902 = 567936。
最终的哈希值即为 567936 % 10000 = 7936，其中 10000 是哈希表大小。

我们可以看到，折叠法可以将长关键字转化为短的数字段，并且保留了关键字的信息。通过逐步将数字段相加，我们可以在尽可能保持哈希质量的同时获得较短的哈希值。

（5）随机数法（了解）

随机数法是一种哈希函数设计方法，它利用随机数生成器将关键字映射到哈希值。具体来说，随机数法使用一个随机数生成器生成一个随机数，然后将该随机数与关键字进行组合，最后将组合结果作为哈希值。
$H a s h (k ey) = r an d o m (k ey)$
(其中random是产生随机数的函数）

以下是一个简单的随机数法示例，假设我们有一个关键字 “hello” 需要哈希：

生成一个随机数：例如，假设我们生成的随机数是 12345。
将随机数与关键字进行组合：例如，我们可以将随机数添加到关键字的开头或结尾，得到 “hello12345”。
将组合后的结果转化为哈希值：可以使用其他哈希函数（如MD5、SHA-1等）将组合后的字符串转化为哈希值。

这样，我们就通过随机数法得到了关键字 “hello” 的哈希值。

（6）数学分析法（了解）

数学分析法是一种哈希函数设计方法，它利用数学运算将关键字映射到哈希值。具体来说，数学分析法通过数学函数、算法或数论等数学原理对关键字进行转换和计算，最终得到哈希值。

以下是一个简单的数学分析法示例，假设我们有一个关键字 “hello” 需要哈希：

将关键字转化为数字：可以使用ASCII码或Unicode码将字符转化为对应的数字。例如，将 “hello” 转化为 ASCII 码，得到数字序列 [104, 101, 108, 108, 111]。
对数字序列进行数学运算：可以使用加法、乘法、异或等运算对数字序列进行处理。例如，将每个数字相加，得到 104 + 101 + 108 + 108 + 111 = 532。
对数学运算结果进行转化：可以进一步对数学运算结果进行转化，例如取余数或进行位运算。例如，将 532 取余 100，得到哈希值 32。

这样，我们就通过数学分析法得到了关键字 “hello” 的哈希值。

数学分析法的优点在于可以灵活地利用数学原理进行哈希函数的设计。通过选择合适的数学函数、算法或数论原理，可以更好地满足哈希函数的要求，如均匀分布、抗碰撞等。同时，数学分析法也具有较高的效率和可控性。

然而，需要注意的是，在使用数学分析法时，需要根据具体应用场景和需求选择合适的数学运算方法，并进行充分的测试和分析，以确保哈希函数的性能和质量。

四、哈希冲突解决方法

哈希表的哈希冲突解决方法分为开放地址法和链地址法两种，其中链地址法属于闭散列，开放地址法属于开散列。开放地址法相对于链地址法来说，更容易实现、更节约空间，并且在缓存方面具有很好的特性；而链地址法则相对于开放地址法来说，更能够保证哈希表中元素的均匀分布，并且可以通过动态调整链表长度来优化性能。下面我们来逐一分析

1. 闭散列

⭕闭散列（Closed Hashing），也称为开放寻址法（Open Addressing），是散列技术的一种。在采用闭散列方法的散列表（Hash Table）中，所有的元素都是直接存储在散列表里面的。

当插入新元素时，首先会通过哈希函数计算元素的哈希值，并将其作为索引放到散列表中的相应位置。如果该位置已经被占据（这种情况通常被称为冲突或碰撞），它将寻找表内的另一个位置。

⭕线性探测

其基本思路是，当通过哈希函数计算得到的索引位置已被占用时（即发生了冲突），不是把新的元素放入一个链表中，而是向后找一个未被占用的位置。即：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

下面给出了一个简单的例子：

首先，我们有一个大小为 $M$ 的哈希表 (默认情况下所有位置为空) 和一个哈希函数 $ha s h$ 。
当我们希望插入一个新的元素 $x$ 时，我们先计算其哈希值 $i = ha s h (x)$ 。
接着我们查看哈希表中索引 $i$ 的位置，如果该位置为空，我们就在这里插入元素 $x$ 。
如果索引 $i$ 的位置已经被一个其他的元素 $y$ 占据，那就产生了冲突。此时，我们就向后查找，也就是查看索引 $i + 1, i + 2, ...$ , 直到找到一个空的位置为止，并把 $x$ 插入在那个位置上。

- 载荷因子

在哈希表中，载荷因子（也常被称为负载因子）是一个很重要的性能指标。它被定义为哈希表中已被占用的槽位（或称为条目、元素）数量与哈希表大小（总槽数量）的比值。

在数学表达式中，载荷因子（负载因子）可以被表示为：

$α = 表中的元素个数 / 散列表的长度$

在一个使用线性探测的哈希表中，载荷因子的大小直接影响了查找、插入和删除操作的性能。

⭕当载荷因子较低时，哈希表内的冲突概率较低，所以线性探测的成本较低。但是，哈希表的内存利用率也较低。

⭕当载荷因子较高时，虽然哈希表的内存利用率提高了，但是冲突的概率也随之增加，这使得线性探测的成本变高，从而降低操作的性能。

**因此，在设计哈希表时，需要在载荷因子和性能之间找到一个合理的平衡。一般来说，对于使用线性探测的哈希表，载荷因子的上限通常设置在0.5到0.85之间。**当载荷因子达到这个阈值时，通常需要进行哈希表的扩容操作：申请一个更大的哈希表，并将所有元素重新插入新哈希表。

- 插入

线性探测是一种开放寻址法的冲突解决策略，具体操作如下：

假设我们有以下变量：

table: 散列表，大小为M。
h(x): 散列函数，计算元素x的散列值。
x: 所需插入的元素。

插入元素的操作步骤如下：

首先，计算元素x的散列值，我们称其为i，即i = h(x)。
然后，查看散列表table中的索引i位置。若此位置为空（即table[i]为空），那就将元素x放在那里。
如果table[i]处已经有其他元素（即产生了冲突），则我们需要开始线性探测。也就是说，我们将索引i递增，查看table[i+1]，table[i+2]，一直到table[M-1]，然后再从头（table[0]）开始，直到table[i-1]。这种查找顺序的变化叫做“环绕”，因为它将表视为一个环形结构。
在进行线性探测的过程中，一旦找到一个空的位置，就将元素x放入此处，并结束操作。
如果线性探测回到了原点，说明散列表已满，此时需要扩展表的大小，并重新进行散列。

🍔方法一：传统方法插入进行扩容（代码冗余）

// 插入键值对函数
bool Insert(const pair<K, V>& kv)
{
    // 查找是否已有相同键存在，如果已存在则返回false，不执行插入
    if (Find(kv.first))
        return false;

    // 如果哈希表大小为0，或者已达到装填因子的阈值（此处为0.7），需要进行哈希表扩容
    if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
    {
        // 判断新的哈希表大小：若原表大小为0，则新表大小设为10；否则设为原表大小的两倍
        size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;

        // 创建新的哈希表
        vector<HashData> newtables(newsize);

        // 遍历原哈希表，将已存在的元素重新映射到新表
        for (auto& data : _tables)
        {
            // 只处理存在的数据，即 _state 状态为 EXIST 的数据
            if (data._state == EXIST)
            {
                // 通过哈希函数重新计算元素在新表中的位置
                size_t i = 1;
                size_t index = hashFunc(data._kv.first);  // 使用哈希函数计算新的索引位置

                // 使用线性探测法解决冲突：若计算出的新位置已被占用，就继续向后查找，直到找到空的位置
                while (newtables[index]._state == EXIST)
                {
                    index = (hashFunc(data._kv.first) + i) % newtables.size();  // 线性探测: (h(key) + i) mod new_table_size
                    ++i;  // 尝试下一个位置
                }

                // 将元素插入到新的位置
                newtables[index]._kv = data._kv;
                newtables[index]._state = EXIST;
            }
        }

        // 将新哈希表和原哈希表交换，完成扩容操作
        _tables.swap(newtables);
    }
    size_t hashi = kv.first % _tables.size();

	// 线性探测
	size_t i = 1;
	size_t index = hashi;
	while (_tables[index]._state == EXIST)
	{
		index = hashi + i;
		index %= _tables.size();
		++i;
	}

	_tables[index]._kv = kv;
	_tables[index]._state = EXIST;
	_n++;
    return ture;
}
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

🍔方法二：复用插入函数进行扩容

你的代码在插入键值对的逻辑上是正确的，相比之前的代码进行了一些改进。下面是对你修改后的代码进行解释：

bool Insert(const pair<K, V>& kv)
{
    // 查找是否已有相同键存在，如果已存在则返回false，不执行插入
    if (Find(kv.first))
        return false;

    // 如果哈希表大小为0，或者已达到装填因子的阈值（此处为0.7），需要进行哈希表扩容
    if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
    {
        // 判断新的哈希表大小：若原表大小为0，则新表大小设为10；否则设为原表大小的两倍
        size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;

        // 创建新的哈希表
        HashTable<K, V> newht;
        newht._tables.resize(newsize);

        // 遍历原哈希表，将已存在的元素重新映射到新表
        for (auto& data : _tables)
        {
            // 只处理存在的数据，即 _state 状态为 EXIST 的数据
            if (data._state == EXIST)
            {
                // 将元素插入到新的哈希表中
                newht.Insert(data._kv);
            }
        }

        // 将新哈希表和原哈希表交换，完成扩容操作
        _tables.swap(newht._tables);
    }

    // 计算新键值对kv的哈希值及索引位置
    size_t hashi = kv.first % _tables.size();

    // 线性探测
    size_t i = 1;
    size_t index = hashi;
    while (_tables[index]._state == EXIST)
    {
        index = hashi + i;
        index %= _tables.size();
        ++i;
    }

    // 将新键值对kv插入到哈希表中
    _tables[index]._kv = kv;
    _tables[index]._state = EXIST;
    _n++;

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

- 删除

在这里插入图片描述

线性探测解决哈希碰撞的方法虽然简单有效，但也因为数组中位置的连续性而存在一定的问题。当删除哈希表中的某个键值对时，在该键值对后面的所有键值对都需要重新排列，以保持哈希表连续的状态。因此，在使用线性探测法解决冲突的哈希表中，删除操作需要特别小心处理。比如上图中，删除元素24，如果直接删掉，54查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

bool Erase(const K& key)
{
	HashData<K, V>* ret = Find(key);
	if (ret)
	{
		ret->_state = DELETE;
		--_n;
		return true;
	}
	else
	{
		return false;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

- 查找

在哈希表中进行查找操作时，通过线性探测法沿着哈希表的连续位置依次查找，直到找到目标元素或者遇到空闲位置为止。

HashData<K, V>* Find(const K& key)
{
	if (_tables.size() == 0)
	{
		return false;
	}

	size_t hashi = key % _tables.size();

	// 线性探测
	size_t i = 1;
	size_t index = hashi;
	while (_tables[index]._state != EMPTY)
	{
		if (_tables[index]._state == EXIST
			&& _tables[index]._kv.first == key)
		{
			return &_tables[index];
		}

		index = hashi + i;
		index %= _tables.size();
		++i;

		// 如果已经查找一圈，那么说明全是存在和删除的状态
		if (index == hashi)
		{
			break;
		}
	}
	return nullptr;
}
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

⭕二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： $H_i$ = ( $H_0$ + $i^2$ )% m, 或者： $H_i$ = ( $H_0$ - $i^2$ )% $m$ 其中：i =1,2,3…， $H_0$ 是通过散列函数 $H a s h (x)$ 对元素的关键码 $k ey$ 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

闭散列（开放定址法）模拟实现

#pragma once
#include 
enum State
{
	EMPTY,
	EXIST,
	DELETE
};

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

template<class K, class V>
class HashTable
{
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
			return false;

		// 负载因子超过0.7就扩容
		//if ((double)_n / (double)_tables.size() >= 0.7)
		if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
		{
			//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			//vector newtables(newsize);
			 遍历旧表，重新映射到新表
			//for (auto& data : _tables)
			//{
			//	if (data._state == EXIST)
			//	{
			//		// 重新算在新表的位置
			//		size_t i = 1;
			//		size_t index = hashi;
			//		while (newtables[index]._state == EXIST)
			//		{
			//			index = hashi + i;
			//			index %= newtables.size();
			//			++i;
			//		}

			//		newtables[index]._kv = data._kv;
			//		newtables[index]._state = EXIST;
			//	}
			//}

			//_tables.swap(newtables);

			size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			HashTable<K, V> newht;
			newht._tables.resize(newsize);

			// 遍历旧表，重新映射到新表
			for (auto& data : _tables)
			{
				if (data._state == EXIST)
				{
					newht.Insert(data._kv);
				}
			}

			_tables.swap(newht._tables);
		}

		size_t hashi = kv.first % _tables.size();

		// 线性探测
		size_t i = 1;
		size_t index = hashi;
		while (_tables[index]._state == EXIST)
		{
			index = hashi + i;
			index %= _tables.size();
			++i;
		}

		_tables[index]._kv = kv;
		_tables[index]._state = EXIST;
		_n++;

		return true;
	}

	HashData<K, V>* Find(const K& key)
	{
		if (_tables.size() == 0)
		{
			return false;
		}

		size_t hashi = key % _tables.size();

		// 线性探测
		size_t i = 1;
		size_t index = hashi;
		while (_tables[index]._state != EMPTY)
		{
			if (_tables[index]._state == EXIST
				&& _tables[index]._kv.first == key)
			{
				return &_tables[index];
			}

			index = hashi + i;
			index %= _tables.size();
			++i;

			// 如果已经查找一圈，那么说明全是存在+删除
			if (index == hashi)
			{
				break;
			}
		}

		return nullptr;
	}

	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_n;
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0; // 存储的数据个数

};

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

2. 开散列

（1）开散列的概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
在这里插入图片描述
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素

（2）开散列实现

- 增容

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？

开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。
在开散列中，当哈希表的装填程度达到一定阈值时，就需要进行增容操作，以保持较低的冲突率和较好的性能。

⭕增容操作的一般步骤如下：

创建一个新的更大的哈希表，通常是原哈希表大小的两倍或更多。
遍历原哈希表中的每个槽位，将非空的键值对重新插入到新哈希表中。这涉及到重新计算键的哈希值，并根据新哈希表的大小选择合适的槽位。
将新哈希表替换为原哈希表，成为新的哈希表。

下面是扩容操作的具体代码：

void _CheckCapacity()
{
    // 获取当前哈希表的桶数量和元素数量
    size_t bucketCount = BucketCount();
    size_t elementCount = Size();
    
    // 如果元素数量等于桶数量，则需要进行扩容操作
    if (elementCount == bucketCount)
    {
        // 创建一个新的哈希表，其桶数量与当前哈希表相同
        HashBucket<V, HF> newHt(bucketCount);
        
        // 遍历当前哈希表中的每个桶
        for (size_t bucketIdx = 0; bucketIdx < bucketCount; ++bucketIdx)
        {
            PNode pCur = _ht[bucketIdx];
            
            // 遍历当前桶中的每个节点
            while (pCur)
            {
                // 将该节点从原哈希表中拆出来
                _ht[bucketIdx] = pCur->_pNext;
                
                // 计算该节点的新桶编号
                size_t bucketNo = newHt.HashFunc(pCur->_data);
                
                // 将该节点插入到新哈希表中
                pCur->_pNext = newHt._ht[bucketNo];
                newHt._ht[bucketNo] = pCur;
                
                // 继续遍历当前桶中的下一个节点
                pCur = _ht[bucketIdx];
            }
        }
        
        // 更新新哈希表的元素数量
        newHt._size = elementCount;
        
        // 交换当前哈希表和新哈希表的指针，从而使得当前哈希表指向新哈希表
        this->Swap(newHt);
    }
}
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

- 插入

⭕插入操作的一般步骤如下：

首先，通过调用Find函数来查找是否已经存在与待插入元素的键（kv.first）相同的元素。如果存在，则返回false，表示插入失败。
然后，创建一个Hash对象，用于计算哈希值。
判断当前哈希表的元素数量（_n）是否等于桶的数量（_tables.size()）。如果相等，说明负载因子为1，即达到了扩容的条件。需要进行扩容操作。
扩容操作中，首先计算新的桶的数量newsize，根据当前桶的数量选择合适的扩容方式。然后创建一个新的哈希表newht，并调用resize函数将其桶的数量设置为newsize。
通过遍历旧哈希表_tables中的每个桶，将每个桶中的元素插入到新的哈希表newht中。具体操作是通过循环遍历每个桶的链表，将链表中的每个节点插入到新哈希表中。
最后，通过调用swap函数交换旧哈希表_tables和新哈希表newht的内容，完成扩容操作。
接下来，计算待插入元素的哈希值hashi，通过取模运算将其映射到对应的桶中。
创建一个新的节点newnode，并将待插入元素kv赋值给新节点的键值对。然后将新节点插入到桶的头部，即将新节点的_next指针指向当前桶的头节点，再将当前桶的头节点指向新节点。
最后，更新哈希表的元素数量_n，表示成功插入了一个元素，并返回true。

下面是插入操作的具体代码：

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
	{
		return false;
	}

	Hash hash;

	// 负载因因子==1时扩容
	if (_n == _tables.size())
	{
		size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2;
		HashTable<K, V> newht;
		newht.resize(newsize);
		for (auto cur : _tables)
		{
			while (cur)
			{
				newht.Insert(cur->_kv);
				cur = cur->_next;
			}
		}

		_tables.swap(newht._tables);

	}

	size_t hashi = hash(kv.first) % _tables.size();
	// 头插
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;

	++_n;
	return true;
}
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

- 删除

计算元素的哈希值和桶编号

在删除元素之前，需要先计算元素的哈希值和桶编号，以确定元素在哈希表中的位置。可以使用哈希函数对元素进行哈希运算，得到一个哈希值，然后使用取模运算将其映射到对应的桶中。

size_t hashValue = HashFunc(data);
size_t bucketNo = hashValue % _bucketCount;
1
2

查找待删除元素所在的链表

根据桶编号，找到待删除元素所在的链表。遍历该链表，查找待删除元素。

PNode pCur = _buckets[bucketNo];
PNode pPrev = nullptr;
while (pCur != nullptr)
{
    if (pCur->_data == data)
        break;  // 找到待删除元素
    pPrev = pCur;
    pCur = pCur->_next;
}
1
2
3
4
5
6
7
8
9

删除元素

如果找到了待删除元素，需要执行删除操作。具体操作包括将待删除元素从链表中移除，并更新桶的头节点和元素数量。

if (pCur != nullptr)
{
    if (pPrev != nullptr)
        pPrev->_next = pCur->_next;  // 将待删除元素从链表中移除
    else
        _buckets[bucketNo] = pCur->_next;
    delete pCur;
    --_size;
}
1
2
3
4
5
6
7
8
9

- 查找

⭕查找操作的一般步骤如下：

首先，判断哈希表是否为空，如果为空，则直接返回nullptr，表示未找到目标元素。
接下来，使用哈希函数对传入的键值key进行哈希运算，并取模运算得到哈希值hashi。哈希值决定了目标元素所在的桶的索引。
通过索引hashi找到对应的桶，将桶中的头节点赋值给cur。
进入一个循环，遍历当前桶中的链表，查找目标元素。
在循环中，首先判断当前节点cur的键值是否与目标键值key相等。如果相等，则说明找到了目标元素，直接返回cur指针。
如果当前节点cur的键值不等于目标键值key，则将cur指向链表中的下一个节点，继续遍历。
如果遍历完整个链表仍未找到目标元素，则返回nullptr，表示未找到。

总结起来，首先根据传入的键值key计算哈希值，并根据哈希值找到对应的桶。然后在桶的链表中遍历，逐个比较节点的键值，直到找到目标元素或遍历完整个链表。如果找到目标元素，则返回该节点的指针；如果未找到目标元素，则返回nullptr。

下面是查找操作的具体代码：

Node* Find(const K& key)
{
	if (_tables.size() == 0)
		return nullptr;
	Hash hash;
	size_t hashi = hash(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（3）开散列存储其他类型的方法

哈希函数采用除留余数法，被模的key必须要为整形才可以处理，此处提供将key转化为整形的方法（整形数据不需要转化）

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
1
2
3
4
5
6
7
8

key为字符串类型

⭕key为字符串类型，需要将其转化为整形

BKDR哈希算法是一种简单且常用的字符串哈希算法，通过遍历字符串中的每个字符，将每个字符的ASCII码加到哈希值上，并乘以一个固定的质数31。最后返回计算得到的哈希值。

具体实现如下：

template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto ch : s)
        {
            hash += ch;
            hash *= 31;
        }
        return hash;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在这个特化版本中，operator()接受一个字符串类型的键值s，并使用循环遍历字符串中的每个字符。对于每个字符，将其ASCII码加到哈希值hash上，并乘以31。最后返回计算得到的哈希值。

需要注意的是，这只是一个简单的示例实现，实际应用中可能需要更复杂的哈希函数来提高哈希表的性能和均匀性。此外，BKDR哈希算法虽然简单，但在某些情况下可能会导致较多的哈希冲突，因此在选择哈希函数时需要根据具体的应用场景进行评估和选择。

开散列模拟实现

namespace HashBucket
{
	template<class K, class V>
	struct HashNode
	{
		HashNode<K, V>* _next;
		pair<K, V> _kv;

		HashNode(const pair<K, V>& kv)
			:_next(nullptr)
			, _kv(kv)
		{}
	};

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

	// 特化
	template<>
	struct HashFunc<string>
	{
		// BKDR
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash += ch;
				hash *= 31;
			}

			return hash;
		}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		~HashTable()
		{
			for (auto& cur : _tables)
			{
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				cur = nullptr;
			}
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hash;
			size_t hashi = hash(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;
					}
					delete cur;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}


		// size_t newsize = GetNextPrime(_tables.size());
		size_t GetNextPrime(size_t prime)
		{
			// SGI
			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
			};

			size_t i = 0;
			for (; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > prime)
					return __stl_prime_list[i];
			}

			return __stl_prime_list[i];
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			Hash hash;

			// 负载因因子==1时扩容
			if (_n == _tables.size())
			{
				/*size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2;
				HashTable newht;
				newht.resize(newsize);
				for (auto cur : _tables)
				{
					while (cur)
					{
						newht.Insert(cur->_kv);
						cur = cur->_next;
					}
				}

				_tables.swap(newht._tables);*/

				//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newsize = GetNextPrime(_tables.size());
				vector<Node*> newtables(newsize, nullptr);
				//for (Node*& cur : _tables)
				for (auto& cur : _tables)
				{
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hash(cur->_kv.first) % newtables.size();

						// 头插到新表
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
				}

				_tables.swap(newtables);
			}

			size_t hashi = hash(kv.first) % _tables.size();
			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;
			return true;
		}

		size_t MaxBucketSize()
		{
			size_t max = 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				auto cur = _tables[i];
				size_t size = 0;
				while (cur)
				{
					++size;
					cur = cur->_next;
				}

				//printf("[%d]->%d\n", i, size);
				if (size > max)
				{
					max = size;
				}
			}

			return max;
		}
	private:
		vector<Node*> _tables; // 指针数组
		size_t _n = 0; // 存储有效数据个数
	};
}
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

3. 开散列与闭散列比较

内存占用：开散列只需要一个哈希表来存储元素，而闭散列需要额外的数据结构来存储冲突的元素，因此闭散列可能需要更多的内存空间。
冲突处理效率：开散列的冲突处理是通过探测的方式在哈希表中寻找下一个可用位置，如果探测序列过长，会导致性能下降。闭散列通过链表或其他哈希表来存储冲突的元素，可以有效避免探测序列过长的问题，但在数据结构中查找元素的效率可能较低。
哈希表的装载因子：开散列对装载因子（load factor）的要求较高，当装载因子过高时，探测序列会变得更长，性能会下降。而闭散列对装载因子的要求相对较低，可以容忍较高的装载因子。
删除操作：开散列的删除操作相对简单，只需将对应位置标记为删除状态即可。而闭散列的删除操作可能需要修改链表或其他哈希表的结构，较为复杂。

综上所述，开散列适用于存储密度较低、空间效率要求较高的场景，而闭散列适用于存储密度较高、冲突较多的场景。

在这里插入图片描述

相关阅读:
【leetcode】排序数组中两个数字之和
Input type=“file“ change事件只触发一次
接口测试之深入理解HTTPS
jupyter远程服务器配置以及服务器开机自启
2024全国水科技大会：【协办单位】山东文远环保科技股份有限公司
伸展树原理介绍
Ansible自动化部署工具-组件及语法介绍
Mybaits延迟加载实现原理
Python爬虫实战：淘宝商品爬取与数据分析
下拉框组件的封装（element ui ）

原文地址：https://blog.csdn.net/m0_75215937/article/details/133966371

【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]

阅读导航

引言

一、哈希概念

二、哈希冲突

三、哈希函数

⭕哈希函数应具备的特点

⭕哈希函数设计原则

⭕常见的哈希函数

（1）直接定址法（重要）

（2）除留余数法（重要）

（3）平方取中法（了解）

（4）折叠法（了解）

（5）随机数法（了解）

（6）数学分析法（了解）

四、哈希冲突解决方法

1. 闭散列

⭕线性探测

- 载荷因子

- 插入

- 删除

- 查找

⭕二次探测

闭散列（开放定址法）模拟实现

2. 开散列

（1）开散列的概念

（2）开散列实现

- 增容

- 插入

- 删除

- 查找

（3）开散列存储其他类型的方法

key为字符串类型

开散列模拟实现

3. 开散列与闭散列比较

【C++入门到精通】哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]