C++布隆过滤器和哈西切分

一、布隆过滤器的提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：不能处理哈希冲突
3. 将哈希与位图结合，即布隆过滤器

二、布隆过滤器的概念

位图的局限性？
只能处理整数
如果是处理字符串、自定义类型呢？
需要布隆过滤器来处理

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

---

我们想要判断三个单词在不在结构中，首先将三个单词字符串转换成一个哈希值，然后在遍历布隆过滤器结构，看sort单词对应的20位置是0还是1，即可判断在不在。

一个单词字符串，即映射一个比特位，这是多么的节省空间啊！！！

存在的问题？

咱们的位图采用的是直接定址法，不会产生位置冲突。
但是布隆过滤器采用的是相对地址映射，字符串的排列组合情况是很多的，很有可能产生位置冲突(不同的字符串，映射到相同的位置)

所以字符串转成整数，是一定存在误判的：

1、在
2、不在
谁会误判呢？
在 会存在误判，不在 的结果是准确的(因为不在的情况下，那个映射的位置，比特位一定是0)

布隆是怎么解决这个问题的呢？

绞尽脑汁，想要把这个误判给干掉，但是解决不了，所以咱们允许误判，但是把这个误判的概率降低

如何降低误判呢？

采用一个单词映射多个位置的办法，这样误判率就会被降低了

但是也不敢映射过多的位置，这样的话，会使用更多的额外空间来存储，空间效率也不是很高

布隆过滤器应该开多大呢？

这个文章里面给出了https://zhuanlan.zhihu.com/p/43263751
利用公式，咱们可以计算，布隆过滤器长度和单词之前的数量关系(大概是4倍的关系)

---

三、布隆过滤器的实现

一般情况下布隆过滤器都是用来处理字符串的，所以这里可以将模板参数K的缺省类型设置为string。布隆过滤器中的成员一般也就是一个位图，我们可以在布隆过滤器这里设置一个非类型模板参数N，用于让调用者指定位图的长度，设置一个非类型模板参数X，用于控制位图长度与插入元素的倍数关系。

template<
size_t N,
size_t X=8,
class K=string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash,
class HashFunc3 = DJBHash
>
class BloomFilter
{
public:
	// 具体一些操作函数
private:
	bitset<X*N> _bs;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

实例化布隆过滤器的时候，我们选取了三个将字符串转为整型的哈西函数，这三个函数综合评分是最高，产生哈西冲突的概率也是最小的

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;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

布隆过滤器的插入

插入元素时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后将位图中的这三个比特位设置为1即可。

void Set(const K&key)
{
	size_t len = X * N;
	size_t index1 = HashFunc1()(key) % len;
	size_t index2 = HashFunc2()(key) % len;
	size_t index3 = HashFunc3()(key) % len;
		
	cout << index1 << endl;
	cout << index2 << endl;
	cout << index3 << endl << endl;
	
	// 将这三个位置标记为1
	_bs.set(index1);
	_bs.set(index2);
	_bs.set(index3);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

布隆过滤器的判断在不在

判断时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后判断位图中的这三个比特位是否被设置为1。这里就会存在前文所说到的误判：
1、在(存在误判)
2、不在(准确的)

bool Test(const K& key)
{
	size_t len = X * N;
	size_t index1 = HashFunc1()(key) % len;
	if (_bs.test(index1) == false)
	{
		return false;
	}
	size_t index2 = HashFunc2()(key) % len;
	if (_bs.test(index2) == false)
	{
		return false;
	}
	size_t index3 = HashFunc3()(key) % len;
	if (_bs.test(index3) == false)
	{
		return false;
	}

	return true;// 在 的情况是存在误判
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试1：

void TestBloomFilter1()
{
	BloomFilter<100> bf;
	bf.Set("sort");
	bf.Set("left");
	bf.Set("right");
	bf.Set("eat");
	bf.Set("tea");
}
1
2
3
4
5
6
7
8
9

我们可以看到，是不存在冲突的

测试2：

void TestBloomFilter2()
{
	BloomFilter<100> bf;
	bf.Set("张三");
	bf.Set("李四");
	bf.Set("牛魔王");
	bf.Set("红孩儿");
	bf.Set("eat");

	cout << bf.Test("张三") << endl;
	cout << bf.Test("李四") << endl;
	cout << bf.Test("牛魔王") << endl;
	cout << bf.Test("红孩儿") << endl;
	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("二郎神") << endl;
	cout << bf.Test("猪八戒") << endl;
	cout << bf.Test("ate") << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

测试3：

void TestBloomFilter3()
{
	BloomFilter<100> bf;

	srand(time(0));
	size_t N = 100;
	std::vector<std::string> v1;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(1234 + i);
		v1.push_back(url);
	}

	for (auto& str : v1)
	{
		bf.Set(str);
	}

	for (auto& str : v1)
	{
		cout << bf.Test(str) << endl;
	}
	cout << endl << endl;

	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(6789 + i);
		v2.push_back(url);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.Test(str))
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		string url = "zhihu.com";
		//std::string url = "https://www.baidu.com/s?wd=ln2&rsv_spt=1&rsv_iqid=0xc1c7784f000040b1&issp=1&f=8&rsv_bp=1&rsv_idx=2&ie=utf-8&tn=baiduhome_pg&rsv_dl=tb&rsv_enter=1&rsv_sug3=8&rsv_sug1=7&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=ln2&rsp=5&inputT=4576&rsv_sug4=5211";
		//std::string url = "https://zhidao.baidu.com/question/1945717405689377028.html?fr=iks&word=ln2&ie=gbk&dyTabStr=MCw0LDMsMiw2LDEsNSw3LDgsOQ==";
		//std::string url = "https://www.cnblogs.com/-clq/archive/2012/01/31/2333247.html";
		url += std::to_string(rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

如何减小误判率？

控制X因子，X越大误判率越接近0，开的空间越大，误判率越低

布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕
3. 存储空间整体变多了，布隆过滤器的优势也没有了

布隆过滤器的优点

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

布隆过滤器的缺点

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

四、布隆过滤器的应用场景

需求:数据量大，节省空间，允许误判，这样场景，就可以使用布隆过滤器

昵称没被用过，那么一定不在布隆过滤器中，我们可以准确判断，但是如果某个昵称使用过，这个就存在误判，所以再去数据库中查找，看看到底用没用过。

常见的适用常见还有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

五、布隆过滤器的扩展[面试题]

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

近似算法

交集里面
1、存在不是交集的query 2、有相同query没进去
是第一种情况

近似算法，(允许有部分摸鱼的！)也就是允许存在一些误判，那么我们就可以使用布隆过滤器。
先读取其中一个文件当中的query，将其全部映射到一个布隆过滤器当中。
然后读取另一个文件当中的query，依次判断每个query是否在布隆过滤器当中，如果在则是交集，不在则不是交集。

精确算法

query是字符串，比如是sql语句，是网络请求url
假设每个query是10byte,100亿个query需要多少存储空间?——100G左右的空间
这里用咱们的set bitset 等都完成不了，需要使用哈西切分

六、哈西切分

一个文件不是100G吗，咱一次处理不了(内存只有1G)，那么就把这个文件切割成为100份，能够平均切分吗？不能，因为不能提高效率，例如A0文件中，可能都存在B0~B99中的交集，我们依次比较，还是没能提高效率，所以咱们要哈西切分。

切分的时候，选择一个哈西函数进行切分，依次遍历文件中的每个query，通过哈西函数，把每个query转换成为一个整数 i (0<=i <= 200)，切分时依次遍历A文件当中的每个query，通过哈希函数将每个query转换成一个整型 i，然后将这个query写入到小文件Ai当中。对于B文件也是同样的道理，但切分A文件和B文件时必须采用的是同一个哈希函数。由于切分A文件和B文件时采用的是同一个哈希函数，因此A文件与B文件中相同的query计算出的 i 值都是相同的，最终就会分别进入到Ai和Bi文件中，这也是哈希切分的意义。

---

如何读取交集呢？

Ai和Bi小文件找交集即可，A和B中相同的query一定进入编号相同的小文件

有点类似于归并排序的思想。
我们就只需要分别找出A0与B0的交集、A1与B1的交集、…、A199与B199的交集，最终将这些交集和起来就是A文件和B文件的交集。

如何在A1和B1小文件中查找交集呢？

这里我们就可以加载进入内存操作了
我们可以将其中一个小文件加载到内存，并放到一个set容器中，再遍历另一个小文件当中的query，依次判断每个query是否在set容器中，如果在则是交集，不在则不是交集。

如何确定切割的份数呢？

这个取决于咱们有多少内存，比如咱们只有1G内存，那么总共100G文件，那么切分成200份，一份500M左右，刚好差不多可以同时加载A1和B1进入内存中

可能会存在两个小文件的大小都大于1G

可以扩大我们的除数，比如扩大到1000，这样让我们切割的份数更多。
如果Ai和Bi都太大，超过内存，可以考虑换个哈希算法，重新再切分一次。
还可以将这两个小文件再进行一次切分，将其切成更小的文件，方法与之前切分A文件和B文件的方法类似(递归算法)。

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

出现次数最多的IP

还是要用到哈西切分

相同的ip一定进入了同一个小文件，那么我们使用map统计一个小文件中的ip的次数，就是他准确的次数。用一个map maxCount容器统计出每个小文件中各个IP地址出现的次数，然后将这个map清空，比对各个小文件中出现次数最多的IP地址，过程中记录出现次数最多的IP，使用一个pair countIP结构l来记录即可，且不断的更新pair，最终就能够得到log file中出现次数最多的IP地址。

找到TOP K 的IP？

可以使用优先级队列
出现次数最多的k个ip
priority_queue ,com> minHeap 使用小堆

Linux命令找出top 10

sort log_file | uniq -c | sort -nr k 1,1 | head -10

sort 命令将以默认的方式将文本文件的第一列以 ASCII 码的次序排列，并将结果输出到标准输出。-n 依照数值的大小排序。-r 以相反的顺序来排序。[-k field1[,field2]] 按指定的列进行排序。
uniq -c或–count 在每列旁边显示该行重复出现的次数。

sort命令
uniq命令
拓展学习：一致性哈西