▶ 位图、布隆过滤器和哈希切割等都是哈希思想的重要应用，它们通过不同的方式来解决海量数据处理中的存储和查询效率问题。下面就来学习一下这三样东西：

一、位图(bitmap)

● 位图概念

所谓位图，就是用每一位(bit)来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在。

● 核心原理‌

通过直接定址法将整数映射到比特位上，用0/1标记数据是否存在。例如：现有40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断这个数是否在这40亿个数中呢？【腾讯面试题】

1.遍历，时间复杂度为$O(N)$
2.排序($O(N\ast Io{g}_{2}N)$)，利用二分查找: $lo{g}_{2}N$
3.位图解决

如果直接去遍历这40亿个数，时间消耗很大，不适合；如果利用二分查找的话，首先数据得是有序的，所以排序也需要很大的时间消耗；如果将这40亿个不重复的无符号整数存到内存中，大概需要160G的内存，数据量太大内存也存不下；那上面的1和2就不能高效的进行数据查找⚠️

换种思路：数据是否在给定的整形数据中，结果是 在(1) 或者 不在(0)，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

对于存储数据存在状态的bit位来说，我们是开不出比特位这种内存的，因为最小的可操作存储单位是字节，而不能开多少的比特位。我们可以开char、short或int类型的数组来存放数据的状态，因为bit位是组成字节的最小单位嘛！我们可以根据数据量的多少，来决定开什么类型的数组和开多大的空间，然后数组里的元素都初始化为0(int类型数组)；如果是char类型的数组，则数组初始化为’\0’。即一开始开辟的数组里的元素的所有bit位上都得是0。

紧接着就是要把数据映射到bit位上，这个要怎么操作呢？如果拿到一个数据，要将这个数据映射到一个bit位上，把这个bit位的值置为1。那这里肯定涉及到位的运算，要用到关于位的操作符！

举个例子：假如现在有：1,7,3,4,93,94这些数据，采用直接定址法hashi = key的话，则可以将他们映射到6个bit位上，即直接将数据对应下标进行bit位的修改：

这里采用的是直接定址法，即用下标与数据直接对应起来去找比特位。上图画有96个bit位，由于数据的最大值也就到94，那上面的96个bit位其实可以囊括0到95范围的数据。但如果数据大于等于96呢？那一开始我们就要根据数据的范围开辟好空间。而且只能以字节为单位开辟空间。比如我们将上面的96个bit位划分为四个四个的字节，即以整型间隔：(注: 1byte == 8bit)

假设现在就是一个一个的整型大小，我们要将数据的存在状态映射进去，怎么映射呢？如果现在来了一个数据x：

首先我们要知道这个数据x要映射在哪个整型里？知道了数据x属于哪个整型后，其次就要知道该数据x要映射在这个整型的第几个比特位上？方法就是🧐：
🔥i = x / 32，计算出x属于第i号整型位置
🔥j = x % 32，计算出x属于第i号整型的第j号比特位上
其中32是你划分的bit位数的间隔。
比如：现在要映射40这个数，则40/32=1，说明40要被映射到下标为1的整型里，然后再计算这个整型要映射到第几号bit位上：40%32=8，说明要映射到下标为1的整形的第8号比特位上，则这个比特位就要置为1。那要怎么将对应的bit位置为1呢？很简单: 将这个数或等1左移j位后的值即可。

需要注意：数组元素的下标是从0开始的，而我们标识比特位也是从0开始的，这是因为x%32的结果可能为0，以0为起点能确保bit位与内存地址的数学映射关系保持一致性，所以下标从0开始记。你只要知道不同的数一定会映射在不同的bit位上。
🧐注意：一个数左移是低位往高位移动，而右移是高位往低位移动。

如果现在的数据集合中删除了某个数，则其映射的bit位上的值要置为0。置为0的方法，就是让_bits[i]与等1左移j位后按位取反的值即可。例如，将上面映射的bit位上的1置为0：

注意：按位取反是所有位都要取反。即0变为1，1变为0。

在将数据都映射到bit位上后，现在给你一个数，让你来判断它是否在这堆集合里面，那现在就方便多了，直接按照映射规则，去对应bit位上检测是否为1即可。关键是要怎么检测这个数对应的bit上是0还是1呢？可以通过返回按位与1左移j位后的返回值来进行判断：
_bits[i] & (1<<j)
上面这个值要么是0(不在)，要么是非0(在)。至于运算过程，可以参照上面的自行推导。

位图的三个核心接口实现：

//N是一个非类型模版参数,表示需要的bit位数
template<size_t N>
class bitset
{
public:
	bitset()
	{
	    //开辟的空间是按整型来开辟的，则要根据需要的bit位数去计算出对应的整型个数
	    //+1是为N/32后所得到的余数开辟的一个整型，因为N/32后有余数，说明空间不够，再加一个1就可以解决了
		_bits.resize(N / 32 + 1, 0);
	}

	void set(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_bits[i] |= 1 << j;
	}

	void reset(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_bits[i] &= ~(1 << j);
	}

	bool test(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		return _bits[i] & (1 << j);
	}
private:
	vector<int> _bits;
};

std库中的位图：bitset

● 位图的应用

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

例如：
(1) 给定100亿个整数，设计算法找到只出现一次的整数？
(2) 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？
(3) 位图的应用变形：1个文件有100亿个int，但只有1G内存，设计算法找到出现次数不超过2次的所有整数

(1)和(3)可以在简单位图的基础上进行封装，即用两个位图来实现查找只出现一次的整数或不超过2次的整数。两个位图一样大小，同下标的bit位双双映射每个数出现的次数状态：00表示没有出现，01表示出现1次，10表示出现2次，11表示出现3次及以上。

对于(2)来说呢，其实也可以用上面的方法：用两个位图来判断两个集合的交集有哪些，用直接定址法hashi = key将两个集合里的数据分别映射在对应的bit位上，然后通过比对两个位图对应bit位上的值是否为1来判断是否是交集。

二、布隆过滤器

● 布隆过滤器的提出

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

● 布隆过滤器的概念

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

链接：BloomFilter
简单来说：布隆过滤器就是用来处理非数字型的海量数据的高效查找的！比如在海量的字符串集合中的查找一个字符串是否存在，先将字符串集合映射到布隆过滤器中，再通过它来判断一个字符串在不在集合里。但是可能会遇到以下的问题：


💣但是上面说的就一定对吗，难道通过上面的方式真的就能准确的判断"apple"这个字符串在不在了吗？再看下图：

通过上面的分析可以知道：纵使一个字符串映射了三个bit位，降低了误判的概率；但还是可能会出现不同字符串的比特位映射冲突的问题！那能不能再增加映射的位数呢，即增加哈希函数的个数？如果再增加哈希函数的个数，那空间消耗也就越多，即很快会把bit位占满，那哈希冲突还是会变多！因为对于每个字符串来说，映射的bit位增多了，那后续插入的字符串大概率就会跟别的字符串映射的位置冲突！意思是再把布隆过滤器变长吗？要知道布隆过滤器就是用来节省空间的！你也不能一直增加布隆过滤器的长度， 那其性能就会下降。

说明布隆过滤器的长度(bit位数)和哈希函数的个数选择 与 误判的概率之间肯定有一种关系，我们要结合实际去做出相应的权衡：




那么根据上面的公式：如果我们选择的哈希函数个数为k=3，而ln2≈0.69，则得到布隆过滤器长度与数据个数之间的一个关系式为m=4.3n；即布隆过滤器长度与数据量之间呈现一个差不多4倍到5倍的关系就已经能很好的降低误报率了。

学到这里，就知道了误判其实是布隆过滤器的固有属性；那布隆过滤器的使用场景，其实就是用来高效判断"绝对不存在"，且能容忍少量"误判存在"的场景。

🤔再来思考一个问题：
判断一个字符串在不在集合里，判断在和不在都会出现误判吗？
首先通过上面的分析可知，判断一个字符串在，是会出现误判的！但是判断一个字符串不在一定是准确的。为什么呢？
🔥试想：如果一个字符串不在集合中，则先前你一定没有将其映射到对应的bit位上，即这个字符串对应的所有bit位上的值一定有0或者全为0。所以当你看到这个字符串映射的所有bit位上有0时，就说明这个字符串不在。

那利用布隆过滤器可以准确的判断不在的特点，就可以快速的进行过滤，针对性的去处理在的情况。什么意思呢？举一个布隆过滤器的使用场景：

比如：你现在要使用一个app，且你是新人；则你需要注册一个昵称，并且你的昵称不能和已经存在的用户昵称相冲突。假如这个软件已经在其服务器的数据库中存储了那些已经注册的用户昵称，则先将这些已存在用户的昵称映射到一个布隆过滤器中，当你注册这个app时输入一个新昵称，那app就会通过布隆过滤器进行判断：这个昵称是否已经存在？我们说过布隆过滤器对于在的情况是会出现误判的，但是对于不在的情况，是判断准确的。所以当判断这个昵称是在的情况下，并不知道是误判还是真的在？则在判断出在的情况下，还会到服务器的数据库中去比对，以验证是否真的有这个昵称：

通过将数据库中的昵称映射到布隆过滤器中，在注册新昵称时，能够通过布隆过滤器快速的判断出这个昵称是否存在：判断为不在，确实就是不在；而判断在的情况下，再进一步去服务器的数据库中验证是否是真的存在，即二次验证。
🤬试想：如果你要在app客户端上注册1万个昵称，而这1万个昵称中有5千个是注册过的，另外的5千个是没注册过的。在没有布隆过滤器的情况下，每注册一个昵称，都要去数据库里比对一遍，注册1万个昵称就要去库里比对1万次，效率很低；而有布隆过滤器的情况下，能够把没注册过的5千个昵称快速的筛选出来，只有判断在的5千个昵称我们才进一步去数据库里比对，这就实现了效率的提升。这才是布隆过滤器真正的意义所在。

🍉总结：布隆过滤器的作用就是把不在的数据给快速过滤掉。

● 布隆过滤器的插入

布隆过滤器是一个bit向量或者说bit数组，长这样：

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的bit位置成1，例如针对值"baidu"和三个不同的哈希函数分别生成了哈希值1、4、7，则上图转变为：

Ok，我们现在再存一个值"tencent"，如果哈希函数返回3、4、8的话，图继续变为：

值得注意的是，4这个bit位由于两个值的哈希函数都返回了这个bit位，因此它被覆盖了。现在我们如果想查询"dianping"这个值是否存在，哈希函数返回了1、5、8三个值，结果我们发现5这个bit位上的值为0，说明没有任何一个值映射到这个bit位上，因此我们可以很确定地说"dianping"这个值不存在。而当我们需要查询"baidu"这个值是否存在时，那么哈希函数必然会返回1、4、7，然后我们检查发现这三个bit位上的值均为1，那么我们就可以说"baidu"存在了么？答案是: 不可以，只能是说"baidu"这个值可能存在。

这是为什么呢？答案跟简单，因为随着增加的值越来越多，被置为1的bit位也会越来越多，这样某个值"taobao"即使没有被存储过，但是万一哈希函数返回的三个bit位都被其他值置为了1呢，那么程序还是会判断"taobao"这个值存在。

● 布隆过滤器的查找

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

● 布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
比如: 删除上图中的"tencent"元素，如果直接将该元素所对应的二进制比特位置0，则"baidu"元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
当然也有支持删除的方法: 将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
💣缺陷:
1.无法确认元素是否真正在布隆过滤器中
2.存在计数回绕

即：指在使用无符号整(如unsigned int)作为计数器时，当数值达到其最大值后继续递增，会重新从0开始计数的现象‌。这种就是计数回绕。

● 布隆过滤器的优缺点

🥝优点🥝：

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

🎯缺点🎯：

1.有误判率，即存在假阳性(False Position)，不能准确判断元素是否在集合中。解决方法：二次验证
2.不能获取元素本身
3.一般情况下不能从布隆过滤器中删除元素
4.如果采用计数方式删除，可能会存在计数回绕问题

● 布隆过滤器的应用

(1) 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集? 分别给出精确算法和近似算法。

query：指通过指令在数据库或系统中检索数据的操作请求。也可以指数据库查询‌，即使用结构化查询语言(SQL)等从数据库获取信息

🍉🍉🍉对于上面问题：
近似算法：先给一个布隆过滤器，将其中一个A文件的数据通过几个哈希函数分别映射到对应的bit位上，然后另一个B文件再用这个布隆过滤器去判断是否有跟A文件里一样的query。但这样存在的问题就是：可能非交集的数据也会被误判为交集。
精确算法：用哈希切分的方法，先将两个文件切分成多个小文件，然后再将小文件里的数据加载进内存中进行找交集：

假设这里平均1个query为50byte，1G约等于10亿byte，则100亿 query约等于5000亿byte，5000亿byte就约等于500G。这样的话内存是存不下这里的两个文件的，那哈希表/红黑树这些数据结构就通通用不上了！那我们就要对大文件进行哈希分割：

哈希切分文件的好处就是：A和B文件中只要是相同的query，通过相同的哈希函数映射出来的值一定是相等的，所以相同的query一定会被映射分配到相同编号(i)的文件里。这样找交集的时候只需将对应编号的两个小文件加载进内存中，用哈希表/红黑树这些能高效查找数据的数据结构存储query以后，就能实现快速的查找两个文件的交集，而且一定是精确查找。

布隆过滤器的简单逻辑实现：

template<size_t N,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		bs.set(hash1);
		bs.set(hash2);
		bs.set(hash3);
	}

	//布隆过滤器不支持修改,因为删除元素可能会影响到其他的元素
	//当然也有办法修改，就是每个bit位用引用计数的方法，记录下它有几个元素映射着
	//void ReSet();

	bool Test(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		if (bs.test(hash1) == false)
			return false;

		size_t hash2 = HashFunc2()(key) % N;
		if (bs.test(hash2) == false)
			return false;

		size_t hash3 = HashFunc3()(key) % N;
		if (bs.test(hash3) == false)
			return false;

		//返回在,可能存在误判也可能真的在
		return true;
	}
private:
	bitset<N> bs;
};

三、哈希切割(分)

现有如下问题：
(1) 给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址?
(2) 与上题条件相同，如何找到top K的IP?

问题(1)：100G的文件，内存小存不下，如何找出那个出现次数最多的IP地址呢？这里跟上面布隆过滤器那里讲到的找交集有一样的思路就是通过哈希切分来找这里出现次数最多的IP地址：

问题(2)直接用堆排序的方法，把所有IP地址依次读进一个小堆结构里，就可以找出出现次数最多的前K个IP地址。
代码仓库：bitset&bloomfilter