上一篇，我们了解完了哈希桶之和，现在我们来认识 一下关于哈希的应用。
前言
我们接下来会了解2种应用：
位图
布隆过滤器
接下来正式开始：
位图
什么是位图？
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
我们现在用一个面试题来引入位图：
面试题1
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
首先，我们先来复习一下计算机的单位转化：
1GB=1024MB=1024*1024KB=1024*1024*1024Byte≈10亿多Byte
一、分析传统方法的局限性
1. 用 set 存储：
无符号整数通常占4字节（32位），40亿个整数需占用 40*10^8*4 字节 = 160*10^8 字节 ≈16 GB内存。若内存不足（如普通设备内存远小于16GB）， set 会因内存溢出无法使用。因此否定这种方法！2. 排序+二分查找：(排序：O(NlogN))，二分查找: O（logN))
排序40亿个数本身需要极大内存和时间；且即使排序完成，存储这些数仍需约16GB内存，同样存在内存瓶颈。
那么，我们就引出来了今天所讲的---位图
原理
位图利用二进制位表示“存在与否”：用1个二进制位（0或1）对应1个无符号整数，若整数存在则对应位设为1，否则为0。
计算空间消耗---------优势
无符号整数范围是 0~ 2^32-1 （共约43亿个数），因此位图只需 2^{32} 个二进制位。
- 换算为字节：2^32 / 8 = 2^29 字节 = 512 MB（因为 1 字节 = 8 位）。- 512MB内存易满足，远小于 set 或直接存储的16GB。
操作步骤
1. 初始化位图：创建大小为 2^{32} 位的位图，初始所有位为0。2. 加载数据：遍历40亿个无符号整数，将每个数对应的位图位置设为1。
3. 查询判断：对于待查询的数，直接查看位图中对应位是1（存在）还是0（不存在），时间复杂度为 O(1) 。
那它是怎么进行在对应的位图设1的呢？
复习点：
我们学C语言的时候，知道计算机会有两种存储方式：分别是大端机和小端机。
干讲可能有点抽象，现在我们来模拟实现一下：
ps:位图是C++中的库，这里只是简单模拟一下
模拟实现
namespace bai
{
template<size_t N>
class BitSet
{
public:
BitSet()
{
a_.resize(N / 32 + 1);
}
void set(size_t x)
{
int i = x / 32;
int j = x % 32;
a_[i] |= (1 << j);
}
void reset(size_t x)
{
int i = x / 32;
int j = x % 32;
a_[i] &= (~(1 << j));
}
bool test(size_t x)
{
int i = x / 32;
int j = x % 32;
return a_[i] & (1 << j);
}
private:
vector<int> a_;
};
}整个代码量很少，所以直接摆上去了，现在主要任务是，分析它：
其中/32，%32在上面也已经解释过了。
关于操作符的知识：
|：有1则1，两0为0
&：有0则0，两1为1
~：取反，0变1，1变0
1<<j:1向左移到j位
相信学到这里的伙伴，看到这些知识点，应该就能看懂上面的代码逻辑了，不难。
测试：
额外知识：
关于计算机中整数表示范围及相关概念
- INT_MAX：3.921亿多 ： INT_MAX 是C语言等编程语言中 int 类型（通常为32位有符号整数）能表示的最大正整数，其值为2^{31}-1 = 2147483647，21亿多
- UINT_MAX ：无符号整数（如 unsigned int ）能表示的范围是0到2^{32}-1（约42亿多）。
- < -1 > 和 <0xffffffff> ：在计算机中，-1的补码表示为全1（对于32位整数就是 0xffffffff ）
位图的拓展：
以一个面试题来引入：
面试题2
给定100亿个整数，设计算法找到只出现一次的整数？
（ps:这肯定得排除哈希，红黑树....）
但是，还是有一个麻烦点的思路：
分治+哈希：
将100亿个整数分散到多个小文件中，eg:分100个小文件。
依据：相同的整数，哈希值一定相同，因此，只出现一次的整数，一定只会出现在一个小文件当中。
接着，逐批处理小文件，对每个小文件，用普通哈希表统计其中整数出现的次数，筛选处“只出现一次”的整数，记录到结果集中。
最后合并结果。
这里我们使用两个bit位：
现在我们来模拟实现第一种方法：
（ps:下面代码是基于BitSet来进一步写的）
template<size_t N> class towbit { public: void set(size_t x) { //00->01 if (!bt1.test(x) && !bt2.test(x)) { bt1.reset(x); bt2.set(x); } //01->10 else if(!bt1.test(x) &&bt2.test(x)) { bt1.set(x); bt2.reset(x); } } bool is_once(size_t x) { return !bt1.test(x) && bt2.test(x); } private: BitSet<N> bt1; BitSet<N> bt2; };对于每个整数，用2个二进制位表示其出现次数的状态：（上面代码就是通过更新x的状态）
- 00 ：未出现；- 01 ：出现1次；
- 10 ：出现≥2次；
- 11 ：保留（或无意义）。
面试题3
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
方案：
一个文件所有值映射到一个位图，另一个文件判断在不在？这样行不行？
这种方法：空间是够的，但是还是会存在一些问题：出来的交集，需要再次去重。
怎么解决它呢？
法一：
法二：
找到了就reset一下也可以
面试题4
位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
方案：
类似面试题2
变形：如果出现负数（可能会越界）所以得用BitSet<-1>,强转回（int）i;严格来说不影响。
当然也可以搞一个相对映射
位图的应用
1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记
布隆过滤器
引入：
对于一个想要查找公司名字的情景：
1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
万一存在上面的情况：在转字符串的时候，存在冲突？这会导致结果可能不正确？
针对上面的情况，我们有了一种方法---布隆过滤器。
概念：
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间
应用场景：
1.不需要精确的的场景，eg:快速判断昵称是否被注册过。（容忍误判）
此时就可以把它放到布隆过滤器里。
2.需要精确的的场景:eg:快速判断昵称是否被注册过(精确)
此时也可以把它放到布隆过滤器里，减少误判。而不是直接放到数据库那里查找，这就有利于减少数据库的查询负载压力，提高效率。
干讲抽象，我们还是先自行模拟一下，知道它大概的过程，再来进行讲解会好点：
模拟实现：
在模拟实现之前，先知道几个算法（这里我们并不会去学习它，只是用来测试而已）
1.BKDRHash 2.APHash 3.DJBHash
#include<string> using namespace std; struct BKDRHash { size_t operator()(const string& s) { // BKDR size_t value = 0; for (auto ch : s) { value *= 31; value += ch; } return value; } }; struct APHash { size_t operator()(const string& s) { size_t hash = 0; for (long i = 0; i < s.size(); i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5))); } } return hash; } }; struct DJBHash { size_t operator()(const string & s) { size_t hash = 5381; for (auto ch : s) { hash += (hash << 5) + ch; } return hash; } };布隆过滤器：
template<size_t N,class K=string,class Hash1= BKDRHash,class Hash2= APHash,class Hash3= DJBHash>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t x = Hash1()(key) % N;
bts.set(x);
size_t y = Hash2()(key) % N;
bts.set(y);
size_t z = Hash3()(key) % N;
bts.set(z);
}
bool test(const K&key)
{
size_t x = Hash1()(key) % N;
if (bts.test(x) == false) return false;
size_t y = Hash2()(key) % N;
if (bts.test(y) == false) return false;
size_t z = Hash3()(key) % N;
if (bts.test(z) == false) return false;
}
private:
bitset<N> bts;
};
布隆过滤器：
1.通过多映射几个，来降低冲突。
2.上面我们通过了仿函数的形式来对算法使用。
3.一般情况下，布隆过滤器不支持删除：因为映射了相同的值，reset后，会把别的映射在同位置的也会影响。
比如说：上面的，如果你删除了一个的话，另一个可能也映射到了该位置，也会被删了，严重时，结果直接没了。
4.布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1
5.查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中
注意：是0一定不存在，但是1是可能存在（存在误判）。
布隆过滤器：
优点：
1.增加和查询元素的时间复杂度为:O(K)(K为哈希函数的个数，一般比较小)与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
eg:红黑树，哈希空间大
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺陷：
1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法再
建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素4. 如果采用计数方式删除，可能会存在计数回绕问题
布隆过滤器的拓展：
1.如何拓展布隆过滤器使得它支持删除元素的操作：
多个位标识一个值，引用计数。
2.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出
精确算法和近似算法？
近似算法：用一个布隆过滤器，其中一个文件放进，另一个文件看在不在，如果在就是交集。
精确算法：
记住：这里是哈希切分，而不是平均切分。
这样做有什么好处呢？
以前这个小文件A0可能跟相同的B后面所有的小文件都需要找一下，而现在不用了，直接找交集。
也就是：对应的小文件找交集即可，如果平均切分，查询可能在任意位置，那么A0可能需要全部遍历一遍，A1......也是，切小的意思是：只有1GB内存，那么你在磁盘中找太慢了，那么我在内存中来，对一个小的跟你找可能会好找一些，比如是把一个小的放到一个哈希表里面去，剩下的挨着遍历，看在不在哈希表，在就是交集，不在就不是。
现在是编号相同的找一次即可，为什么？
理论支持：哈希切分：A和B相同的query一定会分别进入Ai和Bi编号相同的小文件，因为我们用的是同一个哈希函数，所有不可能一个进不同的编号，如果相同（重复）。
所以，大部分都可用哈希切分解决。
-->核心：内存太大了，我解决不了，那么我给你切小就可以解决，但是我平均切分的话（还是暴力求解），每个小文件都要去比对一下，不划算，所以哈希切分：数据分流进对应的编号上。
额外拓展：（简单了解了解，等到后面更新Linux的文件系统部分就清楚了）
那么 有人可能会疑惑了，那么文件读取又是怎么切分的？它难道可以在磁盘中切吗？
（其实等到后面Linux中的文件管理部分的内容你就会有焕然大悟的感觉）
它比如是不可能在磁盘中切分的，它是读取到内存里面运算，运算到编号是几，就写到对应的文件(文件描述符等等知识)，走一遍内存，但是它是几乎是没有内存消耗的，因为你不是一个一个的读取数据的，一般是一段一段读，加载到文件缓冲区里，若读的数据还在缓冲区，它就不会到磁盘里去找。
携带的其他问题：
1.重复问题：去重一下（放进两个set）或者找到就删一个
找交集，Ai读出来放到一个set，在依次读取Bi的query，在不在，在就是交集并且删掉，就可以找出Ai和Bi的交集了。
2.不是平均切分，会不会存在某一个内存特别大？
什么意思？即因为冲突太多，导致某个Ai文件太大，甚至超过1GB怎么办？
两种场景：eg:Ai有5GB
1.4GB都是相同的query，1GB冲突
2.大多数是冲突的。
解决方案：
1.先把Ai的query读到一个set，如果set的insert报错抛异常（bad_alloc）那么就说明大多数query都是冲突的，如果能够全部读出来，insert到里面，那么说明Ai有大量相同的query。
2.如果抛异常，说明有大量的冲突，再换一个哈希函数，再进行二次切分。
哈希切割的应用：
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
方案：
把它切分成多个小文件，相同ip一定进入了相同的小文件，然后用map去分别统计每个小文件ip出现的次数既可以
如何找到top K的IP
1.切分多个小文件
2.哈希表统计出现的次数
3.建立一个堆结构（小根堆）例如，要找top 10的IP，就维护一个大小为10的小根堆，遍历小文件中IP的次数时，若当前IP的次数大于堆顶元素的次数，就替换堆顶并调整堆。
4.处理完小文件后，堆中的元素就是top K的IP。
如何直接用Linux系统命令实现？(如果没学的话可先不看)
'{print $1}' 获取每一行文本中第1个字段 awk 提取IP列， sort 排序 uniq -c 统计每个IP出现的次数 sort -rn 按次数降序排序 head -K 取前K个（比如取前10个，就用 head -10 ）。 awk '{print $1}' log_file | sort | uniq -c | sort -rn | head -K
好了，关于哈希应用及拓展就分享到这里了，希望对大家有所进步！
最后，到了本次鸡汤环节：
希望好运会降临~
