2.4 哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

2.4.1 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去 1. 线性探测 从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止 插入 通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突， 使用线性探测找到下一个空位置，插入新元素 删除 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素 会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影 响。因此线性探测采用标记的伪删除法来删除一个元素。 （这里使用的是通过标记状态来解决）

线性探测优点：实现非常简单， 线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同 关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降 低。

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位 置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法 为：H_i = (H_0 + i^2 )% m, 或者：H_i = (H_0 - i^2 )% m。其中：i = 1,2,3…， H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表 的大小。（也就是如果我们从i从1开始找，如果已经被占用了，就把i改成2，再探测，直到探测到空为止 研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任 何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在 搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出 必须考虑增容

2.4.2 开散列

1. 开散列概念 开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中。

 从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素

我们把这个结构叫哈希桶，这也是单链表的应用的地方，正常来说单链表是不会单独拿来存储数据的，而是其他结构的子结构。但是如果这个哈希表如果太小也会导致单链表太长而导致查找效率低，所以我们可以通过保证全部的元素和哈希表的大小保持相等就可以达到最好的效果。这样既不会浪费空间，而且查找效率也高。

2. 开散列实现

放在下面模拟实现中

3. 模拟实现unordered_map和unordered_set

4. 哈希的应用

4.1 位图

4.1.1 位图概念

1. 面试题 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中。【腾讯】 1. 遍历，时间复杂度O(N) 2. 排序(O(NlogN))，利用二分查找: logN 3.红黑树以及哈希表，但是内存太大，不适合 4.位图解决（最优） 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一 个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0 代表不存在。 2. 位图概念 所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用 来判断某个数据存不存在的。

4.1.2 位图的实现

我们使用位图是利用哈希绝对映射的思想，因为在海量数据中需要使用到的空间必然很多，而且数据量十分庞大，我们使用绝对映射即可。

我们一般使用3个主要的函数：一个是记录，在位图置为1中，一个是销毁，在位图中置为0，还有一个是查找，看看该元素是否在位图中。

template class bit_set{public:bit_set(){//_bit.resize((N >> 3) + 1, 0);_bit.resize(N/8 + 1, 0);}void set(size_t x){size_t i = x >> 3;//等价于N/8size_t j = x % 8;//把那个bit置为1_bit[i] |= (1 << j);}void reset(size_t x){size_t i = x >> 3;//等价于N/8size_t j = x % 8;//把除了那个bit都保持不变_bit[i] &= (~(1 << j));}bool test(size_t x){size_t i = x >> 3;//等价于N/8size_t j = x % 8;return _bit[i] & (1 << j);}private:vector _bit;};void test_bit_set(){/*bit_set<100> bs1;bit_set<1000> bs2;bit_set<10000> bs3;*/bit_set<0xffffffff> bs;//bit_set<((size_t)-1)> bs;bs.set(1024);bs.set(10);bs.set(104);bs.set(102401);cout << bs.test(10) << endl;bs.reset(10);cout << bs.test(10) << endl;}

4.1.3 位图的应用

1. 快速查找某个数据是否在一个集合中 2. 排序 + 去重 3. 求两个集合的交集、并集等 4. 操作系统中磁盘块标记

4.2 布隆过滤器

4.2.1 布隆过滤器提出（背景）

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？ 1. 用哈希表存储用户记录，缺点：浪费空间 2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。 3. 将哈希与位图结合，即布隆过滤器

4.2.2布隆过滤器概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。 布隆过滤器的理论理解，这篇文章写的很好，可以值得学习

4.2.3 布隆过滤器的插入（布隆的代码实现）

我们可以通过使用stl库中的bitset来进行布隆过滤器的实现：

 布隆过滤器的模拟实现

4.2.4 布隆过滤器的查找（有可能误判）

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。 注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。 比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

 

4.2.5 布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。 如果我们一定要删除就要付出相当大代价，就是使用计数器的方式，使用多个位图来实现，但是这样的空间消耗太大了，还不如直接使用hash表，所以实际应用场景不多。 缺陷： 1. 无法确认元素是否真正在布隆过滤器中 2. 存在计数回绕

4.2.6 布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关 2. 哈希函数相互之间没有关系，方便硬件并行运算 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

4.2.7 布隆过滤器缺陷

1. 有误判率，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据) 2. 不能获取元素本身 3. 一般情况下不能从布隆过滤器中删除元素 4. 如果采用计数方式删除，可能会存在计数回绕问题

 5. 海量数据面试题

5.1 哈希切割

给一个超过100G大小的log fifile, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

思路：我们可以把这100G的数据分成100份，然后我们把其中的每一个数据都转换成整型，然后%100，这样就可以知道该元素在哪个分区，这样出现哈希冲突的的元素都会放在一个分区中，那么就会有下面两种情况：
1.很多数据在同一个分区中，分区大小很大，但是同时数据大量重复存在，可以使用map去记录元素的个数 2.很多数据在同一个分区中，分区大小很大，无法使用map去记录元素的个数 面对这两种情况，我们可以这样解决：无论如果我们都把这个分区的数据放入map中去，如果map可以存下，说明是情况1。这样使用map就可以解决数据最多的问题； 如果map在insert的时候抛异常，说明空间不够，就是情况2，那么我们就可以换另一种hash函数去把这里的数据再分类，之后再放入map中。

5.2 位图应用

思路：因为整数的存储最多就是42亿个数，存在大量重复，如果我们使用位图去存储这些数据就是512M就可以存下了（状态），然后遍历位图去找即可

思路：跟上面的方式一样，我们使用两个位图，这样内存刚好是1G，去中它们相同的状态即可

思路：出现次数不超过2次就是出现1次或者两次，我们可以使用两个位图，因为其中涉及到的就是4中状态：0，1，2，2次以上，所以我们可以使用00，01，10，11来记录。使用两个位图就可以知道当前的bit的出现的次数了。

5.3 布隆过滤器

如果是近似算法我们可以使用布隆过滤器来把找到的值全部放入交集中，如果我们想要找到精确的算法，那么我们就应该把100亿个query（假设一个query（查询指令）大概是50字节，这里就是500G），那么我们就把它们分成500份，使用分治以及hash的思想，和5.1的解决方式相同。

这样我们只能增加一个计数器来记录有多少个元素映射到了这个空间，每次删除就把这个位置的值--即可，但是消耗空间很大，一般不支持删除操作。