devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】-- 哈希应用之布隆过滤器_可扩展的布隆过滤器

作者：羊村懒王 | 2024-04-18 00:11:50

赞

踩

可扩展的布隆过滤器

目录

一、布隆过滤器介绍

二、布隆过滤器实现

1.布隆过滤器

2.三种哈希函数

（1）BKDR哈希 

（2）AP哈希

（3）DJB哈希

3.标识

4.检查在不在 

5.删除 

 三、完整代码段

四、布隆过滤器优缺点

1.优点

2.缺点 

五、布隆过滤器应用

1.找文件交集 

（1）近似算法

（2）精确算法

2.扩展布隆过滤器

六、哈希应用

1.找到出现次数最多的IP

2. 找到top K的IP

3.用Linux系统命令实现找到top K的IP

一、布隆过滤器介绍

        位图有使用起来，节省空间，并且效率高的优点。位图的缺点，只能处理整形。

        假如起昵称时要看一个字符串有没有被占用，用一个bit位标识。哈希解决冲突时，可以把后续同样位置冲突的元素的挂起来，形成链表。但是现在，如果要用位图存储字符串，bit位存不了指针，挂不起来，处理不了哈希冲突。如果用哈希存储又会浪费空间。

        因此能不能考虑将哈希和位图结合针对字符串等非整形的类型，设计一个像位图一样的判断key在不在的节省空间的数据结构呢？可以——布隆过滤器

布隆过滤器是一种紧凑的、巧妙的概率型数据结构，能够高效插入查询，来判断一个元素在或不在，用多个哈希函数，把一个数据映射到位图中，不仅能提高查询效率，还能节省空间

 映射多个位时，这种情况下也可能存在误判，但是误判概率低了，因为当映射的多个位都被占用才会冲突，才会导致误判。如上图中的"华山"还没存入呢，要映射的几个位都变成了1，这时会导致"华山"被误判。但是这种误判发送的概率比较低，只在几个位全都被占用的情况下才发生。

二、布隆过滤器实现

1.布隆过滤器

 只需要位图一个成员即可：

  1. #define  _CRT_SECURE_NO_WARNINGS  1
  2. #pragma once
  3. #include "BitSet.h"
  4. #include <string>
  5. using namespace std;
  6.  
  7. template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
  8. class BloomFilter
  9. {
  10. private:
  11. 	delia::BitSet<N> _bitset;
  12. };

2.三种哈希函数

由于要用三种不同的哈希算法进行计算来降低冲突，因此，可以选择3种不同的哈希算法：

（1）BKDR哈希 

  1. struct HashBKDR
  2. {
  3. 	size_t operator()(const string& s)
  4. 	{
  5. 		size_t value = 0;
  6. 		for (auto e : s)
  7. 		{
  8. 			value += e;
  9. 			value *= 131;
  10. 		}
  11.  
  12. 		return value;
  13. 	}
  14. };

（2）AP哈希

  1. struct HashAP
  2. {
  3. 	size_t operator()(const string& s)
  4. 	{
  5. 		register size_t hash = 0;
  6. 		size_t ch;
  7. 		for (long i = 0; i < s.size(); i++)
  8. 		{
  9. 			ch = s[i];
  10. 			if ((i & 1) == 0)
  11. 			{
  12. 				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
  13. 			}
  14. 			else
  15. 			{
  16. 				hash ^= (~(hash << 11) ^ ch ^ (hash >> 5));
  17. 			}
  18. 		}
  19.  
  20. 		return hash;
  21. 	}
  22. };

（3）DJB哈希

  1. struct HashDJB
  2. {
  3. 	size_t operator()(const string& s)
  4. 	{
  5. 		register size_t hash = 5381;
  6. 		for (auto e : s)
  7. 		{
  8. 			hash += (hash << 5) + e;
  9. 		}
  10.  
  11. 		return hash;
  12. 	}
  13. };

3.标识

 用三种哈希函数分别计算对应的比特位，将这三个比特位都置1：

  1. 	void Set(const K& key)
  2. 	{
  3. 		size_t i1 = Hash1()(key) % N;//也可以写成Hash1 hf1; size_t i1 = hf1(key) % N;
  4. 		size_t i2 = Hash2()(key) % N;
  5. 		size_t i3 = Hash3()(key) % N;
  6.  
  7. 		cout << i1 << " " << i2 << " " << i3 << endl;
  8.  
  9. 		_bitset.set(i1);
  10. 		_bitset.set(i2);
  11. 		_bitset.set(i3);
  12. 	}

4.检查在不在 

分别用三种哈希函数计算三个比特位，如果检测到有一个比特位为不在，那就返回不在：

  1. 	bool Tests(const K& key)
  2. 	{
  3. 		size_t i1 = Hash1()(key) % N;
  4. 		if (_bitset.test(i1) == false)
  5. 		{
  6. 			return false;
  7. 		}
  8.  
  9. 		size_t i2 = Hash2()(key) % N;
  10. 		if (_bitset.test(i2) == false)
  11. 		{
  12. 			return false;
  13. 		}
  14.  
  15. 		size_t i3 = Hash3()(key) % N;
  16. 		if (_bitset.test(i3) == false)
  17. 		{
  18. 			return false;
  19. 		}
  20.  
  21. 		return true;//可能存在误判，如"华山"
  22. 	}

5.删除 

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

比如：删除"钟楼"元素，如果直接将该元素所对应的二进制比特位置0，“华山”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

 三、完整代码段

BloomFilter.h: 

  1. #pragma once
  2. #include "BitSet.h"
  3. #include <string>
  4. using namespace std;
  5.  
  6. //BKDR哈希
  7. struct HashBKDR
  8. {
  9. 	size_t operator()(const string& s)
  10. 	{
  11. 		size_t value = 0;
  12. 		for (auto e : s)
  13. 		{
  14. 			value += e;
  15. 			value *= 131;
  16. 		}
  17.  
  18. 		return value;
  19. 	}
  20. };
  21.  
  22. //AP哈希
  23. struct HashAP
  24. {
  25. 	size_t operator()(const string& s)
  26. 	{
  27. 		register size_t hash = 0;
  28. 		size_t ch;
  29. 		for (long i = 0; i<s.size(); i++)
  30. 		{
  31. 			ch = s[i];
  32. 			if ((i & 1) == 0)
  33. 			{
  34. 				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
  35. 			}
  36. 			else
  37. 			{
  38. 				hash ^= (~(hash << 11) ^ ch ^ (hash >> 5));
  39. 			}
  40. 		}
  41.  
  42. 		return hash;
  43. 	}
  44. };
  45.  
  46. //DJB哈希
  47. struct HashDJB
  48. {
  49. 	size_t operator()(const string& s)
  50. 	{
  51. 		register size_t hash = 5381;
  52. 		for (auto e : s)
  53. 		{
  54. 			hash += (hash << 5) + e;
  55. 		}
  56.  
  57. 		return hash;
  58. 	}
  59. };
  60.  
  61. template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
  62. class BloomFilter
  63. {
  64. public:
  65. 	void Set(const K& key)
  66. 	{
  67. 		size_t i1 = Hash1()(key) % N;//也可以写成Hash1 hf1; size_t i1 = hf1(key) % N;
  68. 		size_t i2 = Hash2()(key) % N;
  69. 		size_t i3 = Hash3()(key) % N;
  70.  
  71. 		cout << i1 << " " << i2 << " " << i3 << endl;
  72.  
  73. 		_bitset.set(i1);
  74. 		_bitset.set(i2);
  75. 		_bitset.set(i3);
  76. 	}
  77.  
  78. 	bool Tests(const K& key)
  79. 	{
  80. 		size_t i1 = Hash1()(key) % N;
  81. 		if (_bitset.test(i1) == false)
  82. 		{
  83. 			return false;
  84. 		}
  85.  
  86. 		size_t i2 = Hash2()(key) % N;
  87. 		if (_bitset.test(i2) == false)
  88. 		{
  89. 			return false;
  90. 		}
  91.  
  92. 		size_t i3 = Hash3()(key) % N;
  93. 		if (_bitset.test(i3) == false)
  94. 		{
  95. 			return false;
  96. 		}
  97.  
  98. 		return true;//可能存在误判，如"华山"
  99. 	}
  100. private:
  101. 	delia::BitSet<N> _bitset;
  102. };
  103.  
  104. void TestBloomFilter()
  105. {
  106. 	BloomFilter<100> bf;
  107. 	bf.Set("大雁塔");
  108. 	bf.Set("钟楼");
  109. 	bf.Set("兵马俑");
  110. 	bf.Set("华山");
  111. }

Test.cpp

  1. #define  _CRT_SECURE_NO_WARNINGS  1
  2. #include "BloomFilter.h"
  3.  
  4. int main()
  5. {
  6. 	TestBloomFilter();
  7. 	return 0;
  8. }

四、布隆过滤器优缺点

1.优点

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

（5）数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
（6）使用同一组散列函数的布隆过滤器可以进行交、并、差运算 

2.缺点 

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

五、布隆过滤器应用

1.找文件交集 

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

（1）近似算法

判断交集本质上是判断在不在，读取第一个query，将元素都映射到布隆过滤器中，再读取第二个文件中的query，判断每个query在不在布隆过滤器中，如果在就是交集。

（2）精确算法

 假设每个query是20字节，100亿个query就是100亿*20个字节=2000亿KB=200GB，使用哈希切分

 

2.扩展布隆过滤器

如何扩展BloomFilter使得它支持删除元素的操作？

        布隆过滤器本不支持删除，这是由于布隆过滤器判断一个元素在不在时可能会存在误判，删除它对应的bit位时会影响其他元素，且多个元素可能会映射到同一bit位，因此删除某一bit位时会影响其他元素，可能会导致其他元素也被删除。

        不过可以采用以下方法让布隆过滤器支持删除元素：

        在布隆过滤器中找到该元素后，由于使用多个位表示一个元素，因此可以对布隆过滤器的每一个bit位使用计数来代替0/1(在不在)，当有多个元素映射到该bit位时，该bit计数++ ，删除时，该bit计数--。

六、哈希应用

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

1.找到出现次数最多的IP

（1）文件超过100G，不能加载到内存中，就需要将文件进行哈希切分，通过一个哈希函数，将log文件中的每个IP都转换为整数，如果IP相同，那么转换后的整数也相同，就会映射到同一个小文件中。

 （2）切分成小文件后就可以加载到内存了，对于每次加载到内存的小文件，使用map<string,int>对该小文件中的所有IP进行次数统计，找出出现次数最多的IP。

（3）将每个文件中出现次数最多的IP再使用map<string,int>进行统计，就能找到出现次数最多的那个IP了。

另外：将文件切分为100个小文件，这100个小文件并不是均匀切分的，有的可能会小于1G，有的则可能会大于1G，当有几十个文件都大于1G时，可以考虑将文件直接切分为200份，而不是100份，这样每个小文件大约为512MB。

2. 找到top K的IP

（1）对100G的文件建堆，内存放不下，因此还是要切分成小文件，如上图中将100G的大文件利用哈希函数切分成100个小文件。

（2）将第一个文件加载到内存中，对第一个小文件建有K个元素的小堆，只要比堆顶元素大就进堆，最后堆里剩下的就是第一个小文件中出现次数最多的K个IP。

（3）将剩下的其它小文件依次加载到内存，每加载一个小文件，就将该小文件中的所有IP和堆顶元素进行比较，只要比堆顶元素大，就进堆。最后堆里留下的就是出现次数最多的K个IP。

3.用Linux系统命令实现找到top K的IP

假如有以下文件IP.log：

  1. 192.168.1.5
  2. 69.52.220.44
  3. 10.152.16.23
  4. 192.168.3.10
  5. 192.168.1.4
  6. 192.168.2.1
  7. 192.168.0.9
  8. 10.152.16.23
  9. 192.163.0.9
  10. 192.168.0.9 
  11. 69.52.220.44 
  12. 192.168.1.4 
  13. 192.168.1.5
  14. 192.163.0.9 
  15. 192.168.2.1
  16. 192.168.0.1
  17. 192.168.0.2
  18. 192.168.0.9
  19. 9.9.9.9
  20. 127.0.0.1
  21. 192.168.0.90
  22. 192.168.0.89
  23. 192.168.0.8
  24. 192.168.0.9
  25. 192.163.0.9

（1）按行排序，并将结果输出到标准输出 

sort 文件名

 

 （2）统计并显示文本文件中出现的行或列的次数

uniq -c

（3）根据出现次数倒序排序

sort -r

 （4）查看开头K行

head -k

显示出现次数最多的前K个IP

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/443038
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号