learn C++ NO.26——哈希应用

位图

位图的概念

位图是一种特殊的哈希表。位图通过使用一个比特位来表示元素的存在与否。在位图中，每个位对应一个某种映射关系的元素值，如果该位为 1 表示元素存在，为 0 则表示不存在。位图在处理大量数据的存在性判断、快速排序和去重等操作时具有很高的效率。

比如有20亿个不重复无符号整型数据，需要快速判断某一个数是否在其中时，应该怎么处理？快速判断在不在的场景在学习哈希表后，我们可以想到用unordered_set来进行。但是这里的数据范围太大，unordered_set底层维护的哈希桶以及节点的数据成员以及指针变量都需要内存资源。若果存20亿个无符号整型数据势必导致天量内存开销，所以我们没法使用unordered_set来处理。此时位图就可以上场了，位图可以使用比特位和每一个这个数进行映射，一个字节就可以映射8个整数。所以20亿个数据也只需要大概256MB的空间即可。然后通过 % 运算和 / 运算就可以以O(N)的时间复杂度构建20亿个数据的映射关系。并且只需要O(1)的时间复杂度就能快速判断某一个数在不在的需求。

模拟实现位图

位图的结构其实就是直接定址法的哈希表。由于C/C++原生没有提供存储1比特位的数据类型，既然如此不仅可以采用char类型，也可以采用int类型来进行存储。以存储int类型为例，那么一个int类型可以存32个比特位。所以仅需一个字节就能映射32个无符号整数，存20亿个无符号整数也只需要大概256MB的空间即可。

下面先定义一下位图的基本结构。

对外提供三个接口，一个用于将某个数对应的位修改成1， 一个用于将某个数对应的位修改成0，另一个用于判断数在不在。分别对应三个接口 set(size_t x), reset(size_t x) 以及 check(size_t x)。

需要注意的是位运算操作涉及内存的存储方式是大端存储还是小端存储。本人环境为VS2022下的32位平台debug版本是小端存储。大端存储是将数据的高位字节存储在低地址，低位字节存储在高地址；小端存储则相反，将数据的低位字节存储在低地址，高位字节存储在高地址。

实现思路如下，三个接口都是要找到参数数字对应的比特位。首先就是用x / 32 。获取在哈希表中的下标位置。然后在通过x % 32 确定在表里的位置。如果要将某一个比特位设置成1，那就先让那个位 按位或 上1即可。如果要将某一个比特位设置成0，那就先让那个位 按位与 上0即可。判断一个数在不在，就让存那个数的比特位 和1进行与操作就可。

位图的应用

给定百亿个整数，如何设计算法找到只出现一次的整数？答案是用两个位图来判断该数是否重复出现。两个位图分别的映射关系为两个比特位映射一个值。假设00表示未出现，01表示出现一次，10表示出现两次及以上。那么我们就可以用库里面提供的bitset来设计一个算法解决这个问题。

给两个文件，分别有100亿个整数，只有1G内存，如何找到两个文件交集？通过定义两个位图，将两个文件的内容分别映射到位图中。然后遍历两个位图，对应的位置进行与操作。最终，两个位图中只要位为1的就是两个文件的交集。

布隆过滤器

布隆过滤器是一种特殊的哈希表，用于判断一个元素是否可能在一个集合中。它的工作原理是：通过多个哈希函数将元素映射到一个位数组中，并将对应的位设置为 1 。当要查询一个元素时，同样通过这些哈希函数计算位置，如果所有对应位置都是 1 ，则元素可能在集合中；如果有任何一个位置是 0 ，则元素一定不在集合中。

布隆过滤器的优点是空间效率高、查询速度快。但是它也有一定的缺点，存在误判的可能，即可能会把不在集合中的元素判断为在集合中，但不会把在集合中的元素判断为不在集合中。

模拟实现布隆过滤器

布隆过滤器的类模板设计思路如下，需要提供一个非类型模板参数来初始化布隆过滤器的容量。以及一个类型模板决定被映射数据的类型。还需要提供三个模板接收仿函数类来进行哈希计算。

然后实现一下Set接口，用三个哈希函数计算一下哈希值并调用bitset的set接口将哈希值写入位图中。 接着实现一下Test接口，分别调用三个哈希函数计算哈希值，然后依次调用bitset的test接口进行判断在不在，三个哈希函数值只要有一个为false则表为false，反之三个哈希函数值都有效返回true。

布隆过滤器可以提供reset接口吗？答案是不行，因为所有的元素都是个设计三个哈希值的计算，肯定会出行某一位被至少两个元素的某一个哈希值同时映射。如果reset了某一个值，势必导致其他的值受到影响。虽然技术角度可以实现，但是需要底层开更多的空间，若空间优势不在，还需要用布隆过滤器吗？直接用红黑树为底层的set不是更加好，有保证正确性，效率也还过得去。

布隆过滤器的误判

布隆过滤器的误判产生的原理：布隆过滤器的元素个数足够大的情况下，也有可能是布隆过滤器的长度太短。可能会导致在进行哈希计算不存在的元素时，得到的不存在值的所有哈希值对应的比特位上都已经被设置成1，进而导致布隆过滤器的误判。

布隆过滤器的误判率需要根据哈希函数的个数、布隆过滤器的长度、插入元素的个数所决定。理论上来说哈希函数的个数越多哈希冲突的概率就越低，误判率也就越低。容器的长度越长，不同哈希值的组合越多，误判率也会更低。插入的元素个数非常大的情况下，就算哈希函数再多，哈希函数设计得再精妙，也难免会有误判。以上面实现的布隆过滤器为例，当哈希函数为3(k)，长度为m 和 插入数据位n 时，以公式 m = n * k * ln2得到误判率大概是在4.3左右，空间利用率最高，且相对的误判率较低。

下面通过一组测试来看看不同长度下的布隆过滤器的误判的概率是如何的。一个有10w个数量级来进行布隆过滤器的误判率测试，以近似字符串和不相似符串分别进行误判率进行测试。本测试的参照变量是布隆过滤器的长度。

通过对于布隆过滤器长度进行调整的观察后，可以看到若用一个比特位来映射一个字符串的比例下，近似字符串和非近似字符串的误判率高达百分之八十以上。若用8个比特位来映射一个字符串的比例下，近似字符串和非近似字符串的误判率仅仅为百分之4附近。所以，实际使用布隆过滤器的场景下可以相应多预留更多的空间以降低误判率。这也是为了性能所做的空间上的取舍。毕竟现代计算机的内存资源还是比较充沛的。个人端主流配置都是16G以上了，更别提服务器动则大几百G的内存。

布隆过滤器的应用场景

一个热门应用的注册模块需要快速判断当前用户昵称存不存在的场景。此时，如果直接用数据库的进行查询判断的话，相应的数据库端的负载就会比较大。相应的效率就会比较差，用户体验感就不好。如果在注册模块与数据库之间加上一个布隆过滤器，将数据库的所有昵称放在布隆过滤器里。利用布隆过滤器能够快速准确判断当前昵称在哈希计算后的值不存在的特性。就可以降低数据库的负载，提高整体的运行效率了。虽然，比隆过滤器可能无法准确判断值存在的场景，但是它可以准确判断值不存在的场景。

布隆过滤器也可以用于解决大量非整型数据的判断交集的场景。比如说找两个存有40亿条query语句(字符串数据)的文件的交集。将其中一个文件丢到布隆过滤器中，然后遍历另一个文件让布隆过滤器test每一条query语句。存在，就放到新的文件中。不存在则不做处理。

哈希切分

在上面描述的找两个存有40亿条query语句(字符串数据)的文件的交集问题下，使用布隆过滤器的效率太低了。下面介绍一个比较优秀的办法就是利用哈希切分来进行处理。

原理如下，通过直接定址法哈希函数将两个文件切分成2000个小文件来进行处理，这里就以A文件和B文件来举例描述这两个文件。切分后，让对应哈希值的小文件进行比对。相同的就丢到统一的文件中。这样会就完成了求交集的过程。因为两个切分后的文件大小并不大，可以放在内存里用unordered_set进行去重 + 快速判断匹配不匹配的问题。这样可以大幅度提高效率。

但也会面临一个问题，那就是哈希冲突的引发问题。假设有一个切分文件的语句可能来到了5亿条语句，那么此时势必导致没有办法在使用unordered_se容器进行去重+匹配的处理逻辑，因为unordered_se底层存储数据也有内存开销。此时这种情况一定不是大量重复元素的情况，因为大量重复元素的情况下，unordered_set可以做到去重，这不会导致内存不够的情况，所以排除这个场景。只有大量非重复元素才能让我们的比对逻辑出问题。那就需要将大文件再此切分成小文件来处理。

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？也是用哈希切分的思想进行解决。假设将数据切成500份，然后每份用unordered_map统计一下最次的出现的ip，将它们的键值对存到一个变量里。然后，将unordered_map进行clear()调用后，接着遍历下一个切分文件。遍历完所有切分文件，最大值就能找到了。