【数据结构】哈希表

📝前言：
这篇文章我们来讲讲unorder_map和unordered_set，以及他们底层实现的数据结构哈希表，最后再模拟封装实现一下：
1，unordered_map和unordered_set的介绍
2，哈希表的介绍
3，封装unordered_map和unordered_set

🎬个人简介：努力学习ing
📋个人专栏：C++学习笔记
🎀CSDN主页 愚润求学
🌄其他专栏：C语言入门基础，python入门基础，python刷题专栏，Linux

---

一，unordered_map && unordered_set

和map和set的对比

• 迭代器区别：unordered的意思就是无序的，即：unordered_map的迭代器遍历出的序列是无序的。（注意两个都是单向迭代器）
• 底层区别：map的底层是红黑树，而unordered_map的底层是哈希表，增删改查的效率上：红黑树：O(logN)，哈希表：O(1)
• 对key的要求不同：map的key要求支持 < 比较，而unordered_map的key要支持 转成整型（这个和哈希表特性有关） 和 ==比较
• 接口区别：大部分接口和map相同，多了一些用于哈希表的特有接口
• 同样有multi版本（即：允许重复key）

• 仿函数Hash：把key转换成整型
• 仿函数Pred：让key支持==比较

二，哈希表

哈希表：将数据通过特定的哈希函数映射到存储位置上，后续查找数据的时候，可以利用哈希函数直接算出对应的位置，查找效率变成：O(1)

哈希表的映射

哈希表的映射就是指数据通过哈希函数映射到特定位置的过程。

比如直接定址法：
以关键字key作为哈希地址，或者通过一个简单的线性函数计算出哈希地址。比如，把字母映射到数组下标：arr[ch - 'a']

• 优点是简单直接，不会产生冲突
• 空间地址要开很大，且容易浪费

负载因子

假如哈希表已经映射存储了N个值，哈希表的大小为M，则负载因子(load factor) = $N/M$

哈希冲突

指：有两个不同key映射到同一个位置。哈希冲突不可避免（除非直接定址），但是要尽量减少

哈希函数

将key映射转换成哈希地址的函数。哈希函数的目的就是进行映射，一个能减少冲突的函数才是好函数。

除法散列法 / 除留余数法（重点）

除法散列法也叫除留余数法，即：
假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，即：哈希函数为：h(key) = key % M（这样我们就可以得到一个 [0, M-1] 的数）

M 的取值的讲究

先上结论再解释：

• M的取值要避免取，2的n次幂 / 10的n次幂这种值。
• 应该取：不太接近2的整数次幂的⼀个质数

原因：质数的因数只有 1 和它本身，这意味着：作为除数时，出现相同结果，出现冲突的概率更低。
但是，当哈希表扩容时，因为我要保证M一直为素数所以无法按标准的2倍来扩容，为此：sgi版本的哈希表给了⼀个近似2倍的质数表，每次去质数表获取扩容后的大小：

inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.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;
}

当然这不是绝对的，如果有其他方法能够减少冲突也是可行的。

比如，Java中的HashMap采取除法散列法时就是2的整数次幂做哈希表的大小M，但是它的哈希函数的处理不止仅取模这么简单。
假如它的M取的值是：2^16：它会让key的二进制中的后十六位异或前十六位，得到最后的映射地址
即：

1. key & (1 << 16 - 1)，得到后16位key1
2. key >> 16，得到前16位key2
3. 让 1 和 2 的结果想异或，得到映射地址

这样的做法可以让所有位都参与运算，得到的地址值重复的概率更低

乘法散列法

乘法散列法对哈希表大小M没有要求。
我们想想哈希函数本质是什么？把Key映射到 [0, M - 1] 里，即 M * [0, 1)得到的数一定满足要求。那只要找到一个和 Key有关的 [0, 1) 的小数就可以了。
所以，乘法散列法的步骤：

• 第一步：Key 乘以 A（0 < A < 1），取得到的数的小数部分 B
• 第二步：M * B 向下取整，得到映射地址

全域散列法

Hab (key) = ((a × key + b)%P )%M，P选⼀个足够大的质数，a可以随机选 [1,P-1] 之间的任意整数，b可以随机选 [0,P-1] 之间的任意整数，这些函数构成了⼀个有P*(P-1)个函数的全域散列函数组。假设 P = 17，M = 6，a = 3，b = 4，则 ：H34 (Key) = ((3 × Key + 4) % 17) % 6
每次程序启动的时候，会随机选取一个a和b生成对应的哈希函数。
这种随机性为的是：避免有心之人针对我们提供的哈希函数，特意构造出⼀个发⽣严重冲突的数据集，导致我们的程序卡死。

哈希冲突的解决方法

开放定址法

在开放定址法中所有的元素都放到哈希表里，当⼀个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进行存储，开放定址法中负载因子⼀定是小于 1的。

线性探测

从发生冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。
比如： M = 17，key1 = 8， key2 = 25
key1 放入到下标为 8 的位置，25 放入的时候，发现位置 8 有数据了，则向后找位置，发现下标为 9 的位置没有数据，则放入位置 9

查找的时候，算出对应的哈希地址，如果发现有值则已知2往后找，直到遇到空位置则代表没找到停止。
但是，思考一下：如果中途有一个元素被删除了，那不是提前遇到空了吗
所以我们每一个位置需要设置三种状态：空，删除，存在。
当遇到删除状态的时候，还继续往后找。

缺点：容易造成元素的扎堆

二次探测

从发⽣冲突的位置开始，依次左右按⼆次方跳跃式探测，直到寻找到下⼀个没有存储数据的位置为止。

双重散列

第⼀个哈希函数计算出的值发⽣冲突，使用第⼆个哈希函数计算出⼀个跟key相关的偏移量值，不断往后探测，直到寻找到下⼀个没有存储数据的位置为止。

链地址法

开放定址法中各种方法，不管怎样都还是在内部互相抢占位置。
链地址法中所有的数据不再直接存储在哈希表中，哈希表变成一个指针数组，当没有数据映射到对应位置时，这个位置的指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。

链地址法的负载因子可以大于 1。负载因子越⼤，哈希冲突的概率越⾼，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低

扩容：
stl中unordered_xxx的最⼤负载因子基本控制在1，大于1就扩容。

当一个桶特别长影响查找效率：Java8的HashMap中当桶的⻓度超过⼀定阀值(8)时就把链表转换成红黑树。

key转换成整型

因为key有可能是string或其他类型，但是我们的哈希函数多数时候是基于整型计算的，所以要key要能够转换成整型

三，封装实现

代码有点长，可以上我的GIthub仓库获取

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！