C++之哈希表的基本介绍以及其自我实现
这也就意味着，当元素个数小于容器的大小时，则每一个元素都能够找到自己唯一的一个地址来存放自己。由此引出了直接寻址法。 这种思想，在之前的leetcode387题，字符串中的第一个唯一字符中使用过。
在这里插入图片描述
代码语言：javascript
AI代码解释
class Solution { public: int firstUniqChar(string s) { int count[26] = {0}; for(auto e : s) { count[e-'a']++; } for(int i = 0; i < s.size();i++) { if(count[s[i] - 'a'] == 1) return i; } return -1; } };将每一个字符出现的次数存储到大小为26的数组中，找到次数为1的字符。在这里不做过多的赘述。 但我们的哈希表如果使用上述方式实现，必然会造成效率低下。而C++的大佬们，早已实现各种方法的哈希表，让我们来看看。
一.哈希概念
哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。
1.1 哈希冲突
两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞。
哈希冲突的产生原因
哈希冲突是指不同的键通过哈希函数计算后，得到了相同的哈希值，从而被映射到哈希表中相同的位置。产生哈希冲突的原因主要有以下几点：
（一）哈希函数的局限性
哈希函数的设计至关重要，但再好的哈希函数也无法完全避免冲突。理想情况下，哈希函数应该能够将不同的键均匀地分布到哈希表的各个位置，但实际上，由于键的集合通常是无限的，而哈希表的大小是有限的，这就导致了不同键产生相同哈希值的情况。例如，对于简单的取模哈希函数hash(key) = key % table_size，当键是 5 和 10，且哈希表大小为 5 时，它们的哈希值都是 0，从而产生冲突。
（二）键的分布特性
键本身的分布特性也会影响哈希冲突的发生。如果键的分布较为集中，即大量键的特征相似，那么它们通过哈希函数计算后更容易产生相同的哈希值。比如，在一个存储用户信息的哈希表中，如果用户 ID 是连续的整数，且哈希表大小较小，那么相邻的用户 ID 很可能产生冲突。
1.2负载因⼦
假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么负载因子 = N/M ，负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等，他的英⽂为loadfactor。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低
1.3 将关键字转为整数
我们将关键字映射到数组中位置，⼀般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后⾯代码实现中再进⾏细节展⽰。下⾯哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的Key是关键字转换成的整数。
1.4 哈希函数
⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个⽅向去考量设计。
除法散列法/除留余数法
除法散列法是一种基于取模运算的散列函数设计方法。其基本思想是将键值 k 通过取模运算映射到散列表的某个位置。具体来说，散列函数可以表示为： h(k)= k % m 其中，k 是键值，m 是散列表的大小（即表的长度），h(k) 是计算得到的散列地址。
- 取模运算的作用 取模运算的核心作用是将键值 k 映射到一个较小的范围内，即 [0,m−1]。这样，无论键值 k 有多大，都可以通过取模运算将其“折叠”到散列表的有效索引范围内。
- 选择合适的 m 选择合适的散列表大小 m 对于除法散列法的性能至关重要。理论上，m 应该是一个质数，因为质数可以减少键值之间的相关性，从而降低冲突的概率。例如，如果 m 是 2 的幂（如 16、32、64 等），那么取模运算可以简化为位运算，但这种情况下冲突的概率可能会增加。因此，选择一个质数作为 m 是一个较好的选择。
乘法散列法
乘法散列法的核心思想是通过乘法和位运算将键值映射到散列表的某个位置。其基本步骤如下：
- 选择一个常数 A：常数 A 是一个介于 0 和 1 之间的浮点数，通常选择为一个无理数，如黄金分割比 ≈ 0.6180339887。选择无理数的原因是它可以更好地将键值分布到散列表的不同位置，减少冲突的概率。
- 计算乘积：将键值 k 与常数 A 相乘，得到一个浮点数 kA。
- 提取小数部分：从 kA 中提取小数部分，即 {kA}=kA−⌊kA⌋，其中 ⌊x⌋ 表示对 x 向下取整。
- 计算散列地址：将提取的小数部分乘以散列表的大小 m，并向下取整，得到最终的散列地址。具体公式为：h(k)=⌊m⋅{kA}⌋
全域散列法
全域散列法（Universal Hashing）是一种高效的散列函数设计方法，通过随机选择散列函数来减少冲突的概率，从而提高散列表的性能。
在这里插入图片描述
P需要选⼀个⾜够⼤的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。
需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。
1.5解决哈希冲突
为了解决哈希冲突，C++ 中主要有以下几种常用的方法
（一）链地址法
链地址法是将所有具有相同哈希值的键存储在一个链表中。每个哈希表的槽位对应一个链表的头指针。当发生冲突时，新的键会被添加到相应链表的末尾。这种方法的优点是实现简单，且能够很好地处理大量冲突的情况。例如，对于上述提到的键 5 和 10 的冲突，它们会被存储在同一个链表中，通过遍历链表可以找到对应的键值对。
（二）开放定址法
在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。
- 线性探测
在这里插入图片描述
- 二次探测
在这里插入图片描述
- 双重探测
在这里插入图片描述
.
（三）再哈希法
再哈希法是当发生冲突时，使用另一个哈希函数重新计算哈希值，直到找到空闲位置。这种方法可以有效避免聚集现象，但需要设计两个合适的哈希函数，且计算成本相对较高。例如，第一个哈希函数是hash1(key) = key % table_size，第二个哈希函数是hash2(key) = prime - (key % prime)，其中 prime 是小于哈希表大小的质数。当发生冲突时，通过hash(key, i) = (hash1(key) + i * hash2(key)) % table_size来寻找新的位置，i 是探测次数。