• C++布隆过滤器

    一、前提引入

    思考如下的题目

    将长度为10的字符串保存在哈希表中，需要多少空间

    对于每个字符来说，都有256中可能（即ASCII的理论字符数量，常用ASCII编码只有128个），因此一个长度为10的字符串有256^{10}种比特组合

    因此将字符串转换成整型，是从大范围转换到小范围。也就是多对一，因此将其映射到哈希表中，一定会产生冲突

    可能出现如下情况

    将其进行二次映射，也就是采用两个位置进行映射，从而尽量减少冲突。二次映射可能又会导致冲突，但是二次映射的目的不是消除冲突，而是尽量减少冲突

     由于是多个哈希函数映射，因此对于一个字符串x是否存在的判断可能出现以下情况

    ①x在哈希表中：x的多个映射位置的比特值都为1。但由于多次映射，比特值为1可能是别的字符串映射的结果。因此x在哈希表中的判断是不一定准确的，可能出现误判情况

    ②x不在哈希表中：如果x的多个映射位置中有任意一个的比特值为0，则代表x不在哈希表中。也就是说别的字符串映射结果并不影响x不在哈希表中的映射。所以x不在哈希表中的判断是一定准确的

    二、布隆过滤器概念

    布隆过滤器是哈希与位图的结合

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

    在数据量足够大的时候，不论如何选择哈希函数，都一定会出现冲突问题，而布隆过滤器的设计理念就是降低冲突的概率

    布隆过滤器将哈希的单次映射调整为多次映射。也就是对于同一个关键字使用多个哈希函数进行映射，一个值映射一个位置，容易出现误判，但是一个值映射多个位置就可以降低误判率

    哈希函数的数量并不是越多越好，每多一个哈希函数，关键字映射的位就越多，占用的比特数量就越多。因此需要选择数量合适的哈希函数个数。

    最佳的哈希函数个数计算：k=\frac{m}{n}ln2

    其中k为哈希函数个数，m为布隆过滤器长度，n为元素个数

    三、布隆过滤器的实现

    查找

    分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中

    删除 

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

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

    缺陷： 1. 无法确认元素是否真正在布隆过滤器中 2. 存在计数回绕

    程序实现

    以下实现的几种哈希函数，采用其他大佬实现的经过数学验证的，尽量减少冲突的哈希函数。可以根据自己的需求更改

    1. #pragma once
    2.  
    3. #include
    4. #include
    5. #include
    6. #include
    7. using std::string;
    8. using std::bitset;
    9.  
    10. namespace my_BloomFilter
    11. {
    12. 	struct BKDRHash
    13. 	{
    14. 		size_t operator()(const string& s)
    15. 		{
    16. 			size_t hash = 0;
    17. 			for (auto ch : s)
    18. 			{
    19. 				hash += ch;
    20. 				hash *= 31;
    21. 			}
    22. 			return hash;
    23. 		}
    24. 	};
    25.  
    26. 	struct APHash
    27. 	{
    28. 		size_t operator()(const string& s)
    29. 		{
    30. 			size_t hash = 0;
    31. 			for (long i = 0; i < s.size(); i++)
    32. 			{
    33. 				size_t ch = s[i];
    34. 				if ((i & 1) == 0)
    35. 				{
    36. 					hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
    37. 				}
    38. 				else
    39. 				{
    40. 					hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
    41. 				}
    42. 			}
    43. 			return hash;
    44. 		}
    45. 	};
    46.  
    47. 	struct DJBHash
    48. 	{
    49. 		size_t operator()(const string& s)
    50. 		{
    51. 			size_t hash = 5381;
    52. 			for (auto ch : s)
    53. 			{
    54. 				hash += (hash << 5) + ch;
    55. 			}
    56. 			return hash;
    57. 		}
    58. 	};
    59.  
    60.  
    61. 	template<size_t N,class K=string,class Hash1=BKDRHash,class Hash2=APHash,class Hash3=DJBHash>
    62. 	class BloomFilter
    63. 	{
    64. 	public:
    65. 		void set(const K& key)
    66. 		{
    67. 			size_t len = N * _X;
    68.  
    69. 			size_t hash1 = Hash1()(key) % len;
    70. 			_bs.set(hash1);
    71.  
    72. 			size_t hash2 = Hash2()(key) % len;
    73. 			_bs.set(hash2);
    74.  
    75. 			size_t hash3 = Hash3()(key) % len;
    76. 			_bs.set(hash3);
    77. 		}
    78.  
    79. 		bool test(const K& key)
    80. 		{
    81. 			size_t len = N * _X;
    82.  
    83. 			size_t hash1 = Hash1()(key) % len;
    84. 			if (!_bs.test(hash1))
    85. 			{
    86. 				return false;
    87. 			}
    88.  
    89. 			size_t hash2 = Hash2()(key) % len;
    90. 			if (!_bs.test(hash2))
    91. 			{
    92. 				return false;
    93. 			}
    94.  
    95. 			size_t hash3 = Hash3()(key) % len;
    96. 			if (!_bs.test(hash3))
    97. 			{
    98. 				return false;
    99. 			}
    100.  
    101. 			// 在      不准确的，存在误判
    102. 			// 不在    准确的
    103.  
    104. 			return true;
    105. 		}
    106.  
    107. 	private:
    108. 		static const ssize_t _X = 6;
    109. 		bitset _bs;
    110. 	};
    111. }

    四、布隆过滤器的实现场景

    布隆过滤器优点：

    1. 增加和查询元素的时间复杂度为:O(K)，K为哈希函数的个数，一般比较小，与数据量大小无关

    2. 哈希函数相互之间没有关系，方便硬件并行运算

    3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

    4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

    5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

    6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

    布隆过滤器缺点：

    1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再 建立一个白名单，存储可能会误判的数据)

    2. 不能获取元素本身

    3. 一般情况下不能从布隆过滤器中删除元素

    4. 如果采用计数方式删除，可能会存在计数回绕问题

    可以通过布隆过滤器对数据进行初步判断。比如在账号注册阶段，可以用于用户名查重等操作，如果该用户名不存在，则可以注册。如果该用户名存在，则在数据库中进行查找，二次确认

    实际应用中数据库中的数据量可能特别大，数据都存储在硬盘中。因此采用过滤操作提升查找速度是十分必要的

    五、题目

    1.大文件找交集

    有两个文件，分别由100亿个query，如果只有1G内存，如何查找两个文件的交集？

    query可以简单理解为字符串，假设单个query平均为50字节，100亿个大约是5000亿字节。大约是500个G。两个文件总和有1T数据

    对于无法放进内存的大数据量，一般都是采用切分的方法。将大量数据切割成多个可以放进内存的小文件。如果采用平均切割的话，对每个小文件都要进行操作，实际意义不大。因此采用哈希切分

    哈希切分思想：对每个query都执行哈希函数，并取模。从而求得下标i值，将该query存入文件Ai中

    i= HashFunc(query) \ mod\ 1000

    这里取模1000，代表着将原有500G的大文件，划分为1000个小文件

    如上图，分别将大文件AB各划分为1000个长度不同的小文件，分别对相同下标的小文件求交集，找到的就是交集

    由于不是平均切分，如果存在的冲突多，可能导致单个Ai或Bi小文件过大。单个文件中可能出现大量的重复的query或者有大量不同的query

    情况一：使用unordered_set/set读取整个小文件query，都可以成功插入set，则单个文件中出现大量重复的query

    情况二：使用unordered_set/set读取整个小文件query，插入过程中抛异常，则是有大量不同的query。因此更换成其他哈希函数，再次切割，再次求交集

    2.哈希切割

    有一个超过100G大小的log file，log中存着IP地址，设计算法找打出现次数最多的IP地址？如果只有1G内存，如何找到top K的IP？如何直接使用Linux系统命令实现？

    与上题类似。利用哈希切分成500个小文件，一次读取数据i= HashFunc(ip) \ mod\ 500

    依次处理每个小文件，使用unordered_map/map统计IP出现的次数

    情况一：统计过程中，出现内存异常，则说明单个小文件过大，冲突太多，需要重新更换哈希函数，再次哈希切分这个小文件

    情况二：如果没有出现异常，则正常统计。统计完一个小文件，记录其中最大的，再统计下一个小文件

    将所有文件统计完成后，可以将最大的进行堆排序获取最大的K个IP地址

  • 相关阅读:
    轻松解决软件游戏msvcr120.dll丢失问题，msvcr120.dll丢失的修复步骤分享
    数据结构与算法之美笔记03
    【计算机视觉 | 目标检测】目标检测常用数据集及其介绍（八）
    SpringBoot中有几种定义Bean的方式？
    计算机二级access
    【OpenCV 例程200篇】206. Photoshop 色阶调整算法
    Elasticsearch 范围查询
    （57、58）性能分析命令2
    【Prism系列】Prism子窗口实现
    SAP UI5 SimpleForm 控件的 adjustLabelSpan 属性
  • 原文地址：https://blog.csdn.net/RXY24601/article/details/132875279