什么是哈希

在上一篇博客map和set我们详细的介绍了以红黑树为底层的数据结构，本篇博客论述的哈希这种数据结构实际上是unordered_map和unordered_set的数据结构的底层。

哈希实际上是一种映射关系，map和set实际上在搜索的时候对树进行遍历，理论上的时间复杂度是O(log2N)，但是哈希是可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

问题引入

先来一道OJ387. 字符串中的第一个唯一字符

解决这个问题有一个常见的解法：开一个26个空间的int数组，每一个位置映射26个字母表中一个字母，该位置储存的数为该位置映射字母出现的个数。只要遍历一遍字符串即可得到答案。这里就用了哈希的思想。

注意：

• 哈希函数（HashFunc）： 这里26个英文字母的映射方法，可以是不同的，例如：可以a映射数组下表为0，b映射下表为2以此类推…，也可以z映射数组下表为0，y映射下表为2以此类推…。这就是哈希函数（函数实际上是一种线性映射关系！），哈希函数是可以自定义的。
• 散列表（HashTable）：这里开辟的空间为26的int数组就是散列表，与哈希函数计算出来的存储位置对应。

---

哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

---

哈希函数设计原则：

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

---

面对哈希冲突有两种常见的方法：

直接定址法

直接定址法就是上面OJ题的思路是一种一对一的映射关系
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

• 优点：简单、均匀
• 缺点：需要事先知道关键字的分布情况
• 使用场景：适合查找比较小且连续的情况

除留余数法 （常用、重点）

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

注意：

• 这里的Key与我们在KV模型中的key略有不同， key由于需要取模所以必须是一个正整数——这同时也决定了key是存在范围（一般定义成size_t类型，也就是key只有4294967295种不同情况）
• 如果你想映射一个字符串，理论上不同字符串种类要远远大于不同Key值种类的范围，如果一定让一个字符串对应一个Key，就一定有一些字符串会具有相同的Key值。

哈希冲突

那么问题就出现了，如果不同的值（x）进入哈希函数计算出了相同的值（y）（类比：y=x^2一个y对应两个x），这时就出现了哈希冲突
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

造成哈希冲突有两个原因（以除留余数法为例）：

1. 哈希表开的空间太小，导致不同的key映射到了相同数组下表，解决方法也非常简单——数组增容就完事了
2. 当你插入值的范围大于Key值的范围时，不管你空间开多大，都会造成哈希冲突，因为不同插入的值会对应相同的Key，这个解决方法是更换哈希函数

哈希冲突的解决方法

---

闭散列

闭散列：
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置？

• 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
  对于每一个节点设置三种状态：占用（FULL），空（EMPTY），删除（DELETE）
  插入就是修改节点的值和节点的状态为（FULL）
  删除 则是直接修改节点的状态为（DELETE），实际上是一种伪删除
  散列表的载荷因子：就是插入元素的个数/哈希表的大小，一般在插入的过程中要控制载荷因子在一定的范围内，否则需要扩容来人为降低载荷因子

• 二次探测
  线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位
  置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法
  key值加上{1，-1,4，-4,9，-9…}，如果key加上值的位置已经被占用了，就一直往后加，知道找到空位为止。

总结
闭散列空间利用效率很低

---

开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中。
这样发送冲突之后就不会影响下一位

插入
插入操作就是先算出插入元素在开散列所在的位置，然后采用链表头插

删除
插入操作就是先算出插入元素在开散列所在的位置，然后删除方法同链表删除元素相同

扩容
先开辟一个新的指针数组，然后遍历原来的开散列，将每一个元素依次按上面的插入逻辑插入新的散列之中

开散列实现代码

---

unordered_map && unordered_set 封装实现

这里提供unordered_map的封装的代码，unordered_map底层用的是开散列，封装的方式与map是一样的，具体参考博客map和set 的封装

哈希的应用

位图

先来一道腾讯的面试题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中。【腾讯】

Solution

• 直接遍历——时间复杂度O(N)
• 排序之后，二分查找——时间复杂度O(log2N)
• 位图
  位图就是每一个元素都是bit的一维数组，位图的映射是直接定址法，位图仗着自己单个空间小，所以开辟一个很大的数组表示一个很大的范围。但是缺点也很明显：数组元素是bit只能表示两种状态。至于表示多种状态一种常用的方法开辟若干个位图，这样k值映射的位置就对应了多个bit位
  

布隆过滤器

前面说过一个问题，就是哈希函数是由Key模上散列的大小得出最后的存储位置，但是由于Key必须是正整数所以限制了Key的不同的个数最多只有42亿。但是遇到插入的是字符串这种不同个数是无穷的值时很容易就发生冲突了（如上图所示）。

于是我们做出以下改变，使插入的值不在映射一个位置，而是映射多个位置。相比映射了一个位置添加了多个保险

假设插入顺序是{"hello","world","repeat","bye"}

• 插入
  插入的逻辑非常简单，将插入值映射的所有位的值全部置1

• 检查是否存在

  1. 不存在——只要检查值所对应的位中存在一个位没有被置1，则说明该值未被插入，也就不存在。这个结果是100%确定的。
  2. 存在——检查值所有对应的位如果全为1 ，则说明该值存在。但是这个结果准确吗？
     存在的结果是不准确的，例如上面案例在插入"hello"和"world"之后，如果检查"bye"是否存在的时候，你就会发现bye所有映射的位全部都置成了1 ，但是显然"bye"并未被插入。

布隆过滤器应用场景
我们在注册账号的时候输入昵称的时候，需要快速检测该昵称是否被注册过。可以设置一个布隆过滤器在数据库的上层，输入昵称之后不用先到数据库中查询，而是先在布隆过滤器中查询，如果查出来没有，那么一定数据库中不存在该昵称。如果查出来存在，则在去数据库里面查找一下到底是否存在。

---

代码实现
布隆过滤器的底层是一个位图

实现中的问题

• 如何确定位图应该开多大？
  实际上是有公式的：
  
  k为哈希函数个数，m为布隆过滤器底层位图的大小，n为插入元素的个数。因为k是在实现过程中是确定的，所以m和n就成了一个正比例函数
  代码

哈希经典面试题

哈希切分

• 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
  思路：
  假设内存为4GB，100G的ip地址不可能都加载到内存中，这里采用一个变式 的哈希桶，但是这个哈希桶挂的不是链表，而是文件
  
  100G中的所有ip都通过HashFunc函数分配到相应的桶之中，保持每一个文件（桶）的大小在1GB左右，分配完之后将每一个文件都加载到内存中用map来统计个数。这是大体思路。
  思路漏洞
  万一通过哈希函数分配过程中还没分配完某个文件就已经超过了1GB，该如何处理？
  分为两种情况：
  1. 冲突的ip多，但都是不同的ip，map是无法计数的——解决方法：更换哈希函数将该文件切分成若干子文件，重复上述思路
  2. 冲突的ip多，但都是相同的ip，map是可以统计的 ，切分完之后分段放进内存用map统计次数
• 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出 精确算法和近似算法
  这道题和上一题的思路一致，我们可以对两个文件分别做哈希切分（但是要使用同样的哈希函数），这样相同query才会分到同一个文件夹里面。然后我们在对两个小文件分别加载到内存里面使用set先去重再找交集

位图应用

• 给定100亿个整数，设计算法找到只出现一次的整数？
  使用位图，但是位图只能表示该数存在还是不存在，并不能很好的标识出现的次数。所以这里使用两个位图来解决问题，两个位图，每个位对应两个bit位也就能表示四种状态。问题便得到了很好的解决。
  思考
  100亿个整数开辟位图是不是要100亿个bit位？——
  注意bit位的数量是由数据的范围决定的而不是数据的个数，这也是哈希的本质！整数最多也就42亿个，多出来的都是重复的！

• 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
  使用位图先给一个文件所有整数标记，注意只需注意文件里面数是否存在，出现几次并不在处理范围内。然后遍历第二个文件并用改为图检查，即可找出交集
  注意
  我们开辟一个42亿的位图~0.5G，生下来0.5G内存用来重复读取文件

• 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整 数
  与第一题思路一模一样

布隆过滤器

• 如何扩展BloomFilter使得它支持删除元素的操作
  现有的布隆过滤器是不支持删除操作的，因为删除某一个元素意味着要清空所有他在位图中的对应位，这可能影响别的元素（因为一个位可能被多个元素共用）。解决方法也很简单：对每个位设置一个计数器，删除某一个元素只需要该元素对应所有位的计数器减1即可。但是缺点也十分明显，会消耗很大的空间，本来位图的优势就是每一个位只占一个bit，现在好了每个位变成一个计数器，空间开销会变得巨大！