• C++位图，布隆过滤器

    本期我们来学习位图，布隆过滤器等相关知识，以及模拟实现，需求前置知识

    C++-哈希Hash-CSDN博客

    C++-封装unordered_KLZUQ的博客-CSDN博客

    目录

    位图

    布隆过滤器

    海量数据面试题

    全部代码

    位图

    我们先来看一道面试题

    给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在
    这 40 亿个数中。【腾讯】

     这是一个查找在不在的问题，我们该如何解决呢？使用set可以吗？排序+二分查找可以吗？

    如果但从效率来看，它们都是longN，但是都不行，40亿整数是160亿字节，换算下来大约是16G左右，内存是不会给我们开16G的，如果用set更恐怖，除了存整形，还要存各种附带的东西，left，right，parent，颜色等等，红黑树，哈希表这些都是有附带消耗的

    这是一个在不在的问题，所以我们可以用0和1来表示存在，所以这里可以用比特位来标记，我们开2^32个比特位进行标记，这里和哈希的直接定址法一样，我们这里是开范围，而且2^32比特位是0.5G左右

    此时我们来写需要的结构，我们用vector来实现，但是此时又有一个问题，什么类型的大小是一个比特位？没有，但是我们仔细回忆的话，位运算和位段都是可以实现一个比特位的

    我们这里要实现两个接口，一个set一个reset，分别是将x映射的位置标记为1和0

    一个int是32个比特位，假设此时x=80，我们首先要计算出x在第几个整形的位置，我们用x/32即可，在该整形的第几个位上面，我们可以用x%32，我们带入计算一下，80/32是2，刚好在第二个整形（从第0个开始），再用80%32是16，64+16是80，所以位置刚好是下标

    这里还有一个问题，我们的机器其实是小端机

    也就是说在内存中其实是这样的

    比如我们这里存了一个1，在内存中的存储就是这样的

    1.         //x映射的位置标记位1
    2. 		void set(size_t x)
    3. 		{
    4. 			size_t i = x / 32;
    5. 			size_t j = x % 32;
    6. 			_a[i] |= (1<
    7. 		}
    8. 		//x映射的位置标记位0
    9. 		void reset(size_t x)
    10. 		{
    11. 			size_t i = x / 32;
    12. 			size_t j = x % 32;
    13. 			_a[i] &= (~(1 << j));
    14. 		}

    我们实现这两个函数，使用位运算就可以巧妙的解决问题

    set我们让它的那个位置 | 上1，reset我们让那个位置&上~1（这里1用来移位，所以没有&0）

    接下来我们要判断某个位置是0还是1

    1.         bool test(size_t x)
    2. 		{
    3. 			size_t i = x / 32;
    4. 			size_t j = x % 32;
    5. 			return _a[i] & (1 << j);
    6. 		}

    我们&1即可，如果是0，返回则为假，是1返回真，注意这里是&，不是&=

    我们再加上构造函数，开一下空间，这里向上取整

    接着我们测试一下，没有问题

    下面我们要来完成面试题，首先我们要开42亿的空间（不是40亿，题目说的是40亿个不重复，有可能比40亿大）

    我们在这里写INT_MAX可以吗？不行，INT_MAX是21亿多

    我们应该用这个，无符号的最大值

    或者用更简单的办法，写个-1即可，因为这里是无符号，-1的补码是全1

    手动写16进制也可以

    另外位图在库里面也是有的 

    有各种接口，我们记住test，set和reset即可，其他的基本用不到

    我们来看一些位图的应用

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

     我们看第一个，100亿个整数，只出现一次

    我们之前用1个位标记在不在，现在我们可以用2个位来表示状态，2个位可以表示出4种状态，我们用3种即可，00表示不在，01表示出现一次，10出现2次及以上，我们把位图改造一下即可解决

    还有更省力的方法，我们用bitset来完成

    开两个位图，第一个的第一位和第二个的第一位结合起来就是一个数的状态，依次类推

    为了方便我们先把之前的myset改名和库里面一样的bitset

    1. template<size_t N>
    2. 	class twobitset
    3. 	{
    4. 	public:
    5. 		void set(size_t x)
    6. 		{
    7. 			//00 -> 01
    8. 			if (!_bs1.test(x) && !_bs2.test(x))
    9. 			{
    10. 				_bs2.set(x);
    11. 			}//01 -> 10
    12. 			else if(!_bs1.test(x) && _bs2.test(x))
    13. 			{
    14. 				_bs1.set(x);
    15. 				_bs2.reset(x);
    16. 			}
    17. 			// 本身是10代表出现2次及以上，就不变
    18. 		}
    19.  
    20. 		bool is_once(size_t x)
    21. 		{
    22. 			return !_bs1.test(x) && _bs2.test(x);
    23. 		}
    24.  
    25. 	private:
    26. 		bitset _bs1;
    27. 		bitset _bs2;
    28. 	};

    我们实现一个towbitset，实现一个set接口，对于出现的数字，如果00就变为01，01就变为10，10不用变，然后提供一个isonce，判断出现一次的数

    我们简单测试一下，没有问题 

    下面再看第二个问题，找两个文件的交集

    我们把一个文件的所有值映射到位图，然后另一个文件来判断在不在可以吗？

    可以，但是会有一些问题，比如第一个文件里有一个3，第二个文件里有3个3，那么这里得到的结果也是3个3，是需要进行去重的

    我们来看更好的方法

    我们把两个文件分别映射到两个位图，存在为1，不存在为0，然后对应的位置&一下即可，或者对应位置都为1的就是交集

    比如这样写

    我们再看第三个问题

     不超过2次就是1次和2次，我们还是用2个位来表示，00表示0次，01表示1次，10表示2次，11表示2次以上，解决思路类似问题1

    布隆过滤器

    刚才的问题都是数字，如果是string呢？比如文件1和文件2找交集，里面都是字符串，比如“语文“，”数学“，”英语“这些
    我们把这些字符串计算成对应成整形，映射到位图里，然后按刚才的思路走就行了，不过这样写会有一些问题，就是冲突，比如还有一个字符串”物理“，它和语文计算出的整形是一样的，映射到了同一个位置，是会受到影响的，就存在误判了

    那有什么办法可以解决这个问题吗？

    答案是不能，冲突是无法避免的，但是我们可以减少冲突

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

     举个例子，你要和一个网友去面基，网友告诉你当天他穿的黑色裤子，背着白色的书包，在见面地点你一定不会认错吗？不一定，虽然提供了两个信息，但是还是会有冲突，所以我们只能提供更多的信息来降低冲突，但是不管提供多少信息，在人足够多的情况下还是可能认错

    再回到我们的字符串，我们可以给一个字符串映射3个位置，虽然还可能会有认错，但是几率会低很多

    而且它们之间可能会有交叉

    我们新添加一个物理，甚至可能会有两个位置和前面的元素冲突，但是只要不全冲突就行，容错率是大大提升的

    应用场景：

    不需要精确的场景，比如快速判断昵称是否注册过，我们就可以把所有昵称放到数据库里，我们可以接受百分之3到5的误判率，比如一个昵称没有被使用，但是却显示被使用了，对于用户来说其实是没什么问题的，换一个即可

    假设我们需要精确，不容忍误判，我们可以这样玩，输入的不存在，就返回不存在，如果显示在，我们就去数据库再查一遍，以数据库的结果返回，这样可以减少不在的那些昵称要去查找的损耗，这里就是过滤器的作用，过滤掉了一些，降低数据库的负载压力，提高效率（为什么不全去数据库找？因为太慢了），这也是为什么他叫过滤器的原因

    下面我们来对字符串实现过滤器，我们前面使用了字符串哈希算法，这里就需要用到它了，但是这里还有一个问题，会存在双重冲突的问题

    第一个是两个字符串不同的，但转出来的整形是相同的，第二个是用除留余数法映射后可能回到相同的位置

    基于这两个问题，布隆就想到了映射多个位置，所以就有了布隆过滤器

    1. //BloomFilter.h
    2. struct BKDRHash
    3. {
    4.     size_t operator()(const string& str)
    5.     {
    6.         register size_t hash = 0;
    7.         for (auto ch : str)
    8.         {
    9.             hash = hash * 131 + ch;
    10.         }
    11.         return hash;
    12.     }
    13. };
    14.  
    15. struct APHash
    16. {
    17.     size_t operator()(const string& str)
    18.     {
    19.         register size_t hash = 0;
    20.         size_t ch;
    21.         for (size_t i = 0; i < str.size(); i++)
    22.         {
    23.             size_t ch = str[i];
    24.             if ((i & 1) == 0)
    25.             {
    26.                 hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
    27.             }
    28.             else
    29.             {
    30.                 hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
    31.             }
    32.         }
    33.         return hash;
    34.     }
    35.  
    36. };
    37.  
    38. struct DJBHash
    39. {
    40.     size_t operator()(const string& str)
    41.     {
    42.         register size_t hash = 5381;
    43.         for (auto ch : str)
    44.         {
    45.             hash += (hash << 5) + ch;
    46.         }
    47.         return hash;
    48.     }
    49. };
    50.  
    51. template<size_t N,
    52.     class K = string,
    53.     class Hash1 = BKDRHash,
    54.     class Hash2 = APHash,
    55.     class Hash3 = DJBHash>
    56. class BloomFilter
    57. {
    58. public:
    59. 	void Set(const K& key)
    60. 	{
    61.         size_t hash1 = Hash1()(key) % N;
    62.         _bs.set(hash1);
    63.  
    64.         size_t hash2 = Hash2()(key) % N;
    65.         _bs.set(hash2);
    66.  
    67.         size_t hash3 = Hash3()(key) % N;
    68.         _bs.set(hash3);
    69. 	}
    70.  
    71.     bool Test(const K& key)
    72.     {
    73.         size_t hash1 = Hash1()(key) % N;
    74.         if (_bs.test(hash1) == false)
    75.             return false;
    76.  
    77.         size_t hash2 = Hash2()(key) % N;
    78.         if (_bs.test(hash2) == false)
    79.             return false;
    80.  
    81.         size_t hash3 = Hash3()(key) % N;
    82.         if (_bs.test(hash3) == false)
    83.             return false;
    84.  
    85.         return true;//存在误判
    86.     }
    87. private:
    88. 	bitset _bs;
    89. };

    布隆过滤器实现起来就很简单了，我们借助库里面的bitset和三个字符串哈希算法来实现，然后我们将字符串哈希算法改为仿函数，我们只需要实现Set和Test即可

    我们简单测试一下，没有问题

    我们还可以把hash123打印出来看一看

    这里还是有一个冲突的，猪八戒的两个25

    如果数据足够多，空间小的话冲突的概率就会很大，这里沙悟净就出现了误判

    另外大家可以发现，我们这里是没有实现reset的，是不能实现的，举个例子，如果我们把上面的猪八戒reset了，5和6都会受影响，进而导致孙悟空和二郎神他们都会受影响，就不见了，所以一般不支持删除，删除一个值可能会影响其他值

    如果想要强行支持删除，那要付出很大的代价，比如可以使用多个位标识一个值，使用引用计数

    这里提供一篇知乎大佬写的布隆过滤器详解

    详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)

    建议大家看一看

     下面我们来测试一下，我们set大量的值，然后再给其他大量的值，这些值里有一部分在过滤器里，一部分不在，我们来看看不在过滤器里的值会不会出现误判（也就是原本不在过滤器里的值显示出在）

    1. void TestBloomFilter2()
    2. {
    3. 	srand(time(0));
    4. 	const size_t N = 100000;
    5. 	BloomFilter4> bf;
    6.  
    7. 	std::vector v1;
    8. 	//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
    9. 	std::string url = "猪八戒";
    10.  
    11. 	for (size_t i = 0; i < N; ++i)
    12. 	{
    13. 		v1.push_back(url + std::to_string(i));
    14. 	}
    15.  
    16. 	for (auto& str : v1)
    17. 	{
    18. 		bf.Set(str);
    19. 	}
    20.  
    21. 	// v2跟v1是相似字符串集（前缀一样），但是不一样
    22. 	std::vector v2;
    23. 	for (size_t i = 0; i < N; ++i)
    24. 	{
    25. 		std::string urlstr = url;
    26. 		urlstr += std::to_string(9999999 + i);
    27. 		v2.push_back(urlstr);
    28. 	}
    29.  
    30. 	size_t n2 = 0;
    31. 	for (auto& str : v2)
    32. 	{
    33. 		if (bf.Test(str)) // 误判
    34. 		{
    35. 			++n2;
    36. 		}
    37. 	}
    38. 	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
    39.  
    40. 	// 不相似字符串集
    41. 	std::vector v3;
    42. 	for (size_t i = 0; i < N; ++i)
    43. 	{
    44. 		//string url = "zhihu.com";
    45. 		string url = "孙悟空";
    46. 		url += std::to_string(i + rand());
    47. 		v3.push_back(url);
    48. 	}
    49.  
    50. 	size_t n3 = 0;
    51. 	for (auto& str : v3)
    52. 	{
    53. 		if (bf.Test(str))
    54. 		{
    55. 			++n3;
    56. 		}
    57. 	}
    58. 	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
    59. }

    我们来看一看

    根据上面的测试结果来看，只要你舍得开空间，误判率是可以降低很多的，另外数据样本也是会有影响的，我们用了猪八戒这个字符串来测试，如果用上面很长的网址又是另一个结果，不过差别不会太大，而且只要我们把空间变大，误判率就会下降，一般推荐5到10倍左右

    海量数据面试题

    哈希切割
    给一个超过 100G 大小的 log file, log 中存着 IP 地址 , 设计算法找到出现次数最多的 IP 地址？
    与上题条件相同，如何找到 top K 的 IP ？如何直接用 Linux 系统命令实现？
    位图应用
    1. 给定 100 亿个整数，设计算法找到只出现一次的整数？
    2. 给两个文件，分别有 100 亿个整数，我们只有 1G 内存，如何找到两个文件交集？
    3. 位图应用变形： 1 个文件有 100 亿个 int ， 1G 内存，设计算法找到出现次数不超过 2 次的所有整数
    布隆过滤器
    1. 给两个文件，分别有 100 亿个 query ，我们只有 1G 内存，如何找到两个文件交集？分别给出
    精确算法和近似算法
    2. 如何扩展 BloomFilter 使得它支持删除元素的操作

     这些题我们讲过了部分，我们来看过滤器的1，要求给出精确算法，这里就需要用到哈希切分

    假设平均一个query（查询）是30byte，100亿是3000亿字节，1G大约是10亿字节，也就是说一共是300G左右，而且还是两个这样的文件，现在我们只有1G内存

    我们可以把文件切成一个一个的小文件，但是切成小文件后，交集该怎么找呢？一个一个的再去组合测试吗？这样太慢了

    我们可以用哈希切分，比如我们把文件切成1000分，但不是平均切分，i = Hash(query) % 1000

    i是多少，query就进入第i个小文件，两个文件都用这样的方式来处理

    画出来大概就是这样，此时我们只需要对应编号的找即可，比如A0和B0找，A1和B1找即可

    哈希切分的效果是，A和B中相同的query一定会分别进入Ai和Bi编号相同的小文件，比如一个query在文件A里经过hash，然后%1000，得到了500，那么如果B里面也有这个query，它也会经过一样的步骤，所以得到的i是相同的，进入小文件的编号也就是一样的，这里有点像哈希桶，同一个桶里就是冲突的，但是也有不冲突的，大多数的这种问题都是可以用哈希切分来解决

    这里其实还有一个问题没有解决，找交集，是从Ai中读出来，然后放到set里，再从Bi中读取query，看在不在set，如果在，就是交集，就是可以找到Ai和Bi的交集，这里的切分，如果是平均切分就是一个文件300M，但我们是哈希切分，如果冲突太多，会导致某个Ai文件过大，甚至超过1G（别忘了set也要消耗内存），那该怎么办？

    这里会有两个场景，比如Ai有5G，场景1，4G都是相同，1G是冲突，场景2，大多数是冲突

    这里场景2我们可以换个哈希函数再次切分，一直切，是可以解决的，但是场景1不可以，相同的是切不开的，并且我们是无法区别到底是场景1还是场景2的

    解决方案：1.先把Ai的query读到一个set，如果set的insert报错抛异常（bad_alloc），那么就说明大多数query是冲突，如果能全部读出来，insert到set里面，那么说明Ai中有大量相同的query（set自己可以去重）

    2.如果抛异常，说明有大量冲突，我们换一个哈希函数，进行二次切分

    我们再看下一个问题

    这道题还可以扩展成出现次数最多的K个ip地址

    同样的，我们还是使用哈希切分，比如我们切成300份，i = Hash(query) % 300

    相同的ip一定会进入同一个小文件，之后我们用map分别统计每个小文件中ip出现的次数即可，出现次数最多的K个我们建小堆即可

    全部代码

    1. #pragma once
    2. #include
    3. using namespace std;
    4. //bitset.h
    5. namespace bai
    6. {
    7. 	template<size_t N>
    8. 	class bitset
    9. 	{
    10. 	public:
    11. 		bitset()
    12. 		{
    13. 			size_t num = N / 32 + 1;
    14. 			_a.resize(num);
    15. 		}
    16. 		//x映射的位置标记位1
    17. 		void set(size_t x)
    18. 		{
    19. 			size_t i = x / 32;
    20. 			size_t j = x % 32;
    21. 			_a[i] |= (1<
    22. 		}
    23. 		//x映射的位置标记位0
    24. 		void reset(size_t x)
    25. 		{
    26. 			size_t i = x / 32;
    27. 			size_t j = x % 32;
    28. 			_a[i] &= (~(1 << j));
    29. 		}
    30. 		bool test(size_t x)
    31. 		{
    32. 			size_t i = x / 32;
    33. 			size_t j = x % 32;
    34. 			return _a[i] & (1 << j);
    35. 		}
    36. 	private:
    37. 		vector<int> _a;
    38. 	};
    39.  
    40. 	template<size_t N>
    41. 	class twobitset
    42. 	{
    43. 	public:
    44. 		void set(size_t x)
    45. 		{
    46. 			//00 -> 01
    47. 			if (!_bs1.test(x) && !_bs2.test(x))
    48. 			{
    49. 				_bs2.set(x);
    50. 			}//01 -> 10
    51. 			else if(!_bs1.test(x) && _bs2.test(x))
    52. 			{
    53. 				_bs1.set(x);
    54. 				_bs2.reset(x);
    55. 			}
    56. 			// 本身是10代表出现2次及以上，就不变
    57. 		}
    58.  
    59. 		bool is_once(size_t x)
    60. 		{
    61. 			return !_bs1.test(x) && _bs2.test(x);
    62. 		}
    63.  
    64. 	private:
    65. 		bitset _bs1;
    66. 		bitset _bs2;
    67. 	};
    68. }
    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. //BloomFilter.h
    9. struct BKDRHash
    10. {
    11.     size_t operator()(const string& str)
    12.     {
    13.         register size_t hash = 0;
    14.         for (auto ch : str)
    15.         {
    16.             hash = hash * 131 + ch;
    17.         }
    18.         return hash;
    19.     }
    20. };
    21.  
    22. struct APHash
    23. {
    24.     size_t operator()(const string& str)
    25.     {
    26.         register size_t hash = 0;
    27.         size_t ch;
    28.         for (size_t i = 0; i < str.size(); i++)
    29.         {
    30.             size_t ch = str[i];
    31.             if ((i & 1) == 0)
    32.             {
    33.                 hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
    34.             }
    35.             else
    36.             {
    37.                 hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
    38.             }
    39.         }
    40.         return hash;
    41.     }
    42.  
    43. };
    44.  
    45. struct DJBHash
    46. {
    47.     size_t operator()(const string& str)
    48.     {
    49.         register size_t hash = 5381;
    50.         for (auto ch : str)
    51.         {
    52.             hash += (hash << 5) + ch;
    53.         }
    54.         return hash;
    55.     }
    56. };
    57.  
    58. template<size_t N,
    59.     class K = string,
    60.     class Hash1 = BKDRHash,
    61.     class Hash2 = APHash,
    62.     class Hash3 = DJBHash>
    63. class BloomFilter
    64. {
    65. public:
    66. 	void Set(const K& key)
    67. 	{
    68.         size_t hash1 = Hash1()(key) % N;
    69.         _bs.set(hash1);
    70.  
    71.         size_t hash2 = Hash2()(key) % N;
    72.         _bs.set(hash2);
    73.  
    74.         size_t hash3 = Hash3()(key) % N;
    75.         _bs.set(hash3);
    76. 	}
    77.  
    78.     bool Test(const K& key)
    79.     {
    80.         size_t hash1 = Hash1()(key) % N;
    81.         if (_bs.test(hash1) == false)
    82.             return false;
    83.  
    84.         size_t hash2 = Hash2()(key) % N;
    85.         if (_bs.test(hash2) == false)
    86.             return false;
    87.  
    88.         size_t hash3 = Hash3()(key) % N;
    89.         if (_bs.test(hash3) == false)
    90.             return false;
    91.  
    92.         return true;//存在误判
    93.     }
    94. private:
    95. 	bitset _bs;
    96. };

    以上即为本期全部内容，希望大家可以有所收获

    如有错误，还请指正

  • 相关阅读:
    RocketMQ快速入门_2. rocketmq 的应用场景、与其他mq的差异
    Spring Cloud Feign面试题
    时间序列预测中的数据分析-＞周期性、相关性、滞后性、趋势性、离群值等特性的分析方法
    优化理论12---- 既约梯度法
    基于springboot基于会员制医疗预约服务管理系统项目【项目源码+论文说明】计算机毕业设计
    复合类型(自定义类型)
    【NLP入门教程】二十二、深度学习与NLP简介
    2022年全球市场保偏带通滤波器总体规模、主要生产商、主要地区、产品和应用细分研究报告
    Dubbo启动时检查依赖
    Python在WRF模型自动化运行及前后处理中的应用
  • 原文地址：https://blog.csdn.net/KLZUQ/article/details/133604605