• 中级C++：布隆过滤器

    文章目录

    布隆过滤器

    • 布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，
    • 它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
    • 位图只能解决整数，布隆过滤器解决的是字符串。
    • 还可以将一个数据中的唯一标识，转成字符串，再通过多个哈希函数，映射多个位。
      在这里插入图片描述
    • 对于一个值不存在的状态判定一定是准确的，因为它的多个状态位都是0。
    • 对于一个值存在可能会误判，因为存在冲突，但是可以缓解冲突。

    布隆过滤器设置

    #include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<time.h>
using namespace std;
namespace mybitset  //处理整数  STL容器 bitset
{
	//按位申请空间
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_vc.resize(N / 8 + 1, 0);//多开一个字节，如要开20个比特位，不加一只有2个字节
		}
		//该比特位设置成 1，在
		void set(size_t  x)
		{
			//在第几个char对象里
			size_t i = x / 8;
			//锁定在char对象里第几个比特位。
			size_t j = x % 8;
			_vc[i] |= (1 << j);
		}
		//将该数字设置成不存在
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			_vc[i] &= (~(1 << j));
		}

		//探测该数字在不在
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			return (_vc[i] & (1 << j)) == 0 ? false : true;
		}
	private:
		vector<char> _vc;
	};

	struct HashFunc1
	{
		//BKDR Hash Function 
		size_t operator() (const string& str)
		{
			size_t hash = 0;
			for (size_t i = 0; i < str.size(); i++)
			{
				hash *= 131;
				hash += str[i];
			}
			return hash;
		}
	};
	
	struct HashFunc2
	{
		//SDBM Hash Function  
		size_t operator() (const string& str)
		{
			size_t hash = 0;
			for (size_t i = 0; i < str.size(); i++)
			{
				hash *= 65599;
				hash += str[i];
			}
			return hash;
		}
	};
	struct HashFunc3
	{
		//RS Hash Function  
		size_t operator() (const string& str)
		{
			size_t hash = 0;
			size_t magic = 63689;
			for (size_t i = 0; i < str.size(); i++)
			{
				hash *= magic;
				hash += str[i];
				magic *= 378551;
			}
			return hash;
		}
	};

	//N要插入元素的个数
	template<size_t N
	,class Hash1 = HashFunc1
	,class Hash2= HashFunc2
	, class Hash3 = HashFunc3>
	class Bloomfilter
	{
	public:
		void set(const string& str)
		{
			size_t h1 = Hash1()(str) % len;
			size_t h2 = Hash2()(str) % len;
			size_t h3 = Hash3()(str) % len;
			/*size_t h1 = Hash1()(str);
			size_t h2 = Hash2()(str);
			size_t h3 = Hash3()(str);*/
			cout << h1 << "   " << h2 << "    " << h3 << endl;
			_bf.set(h1);
			_bf.set(h2);
			_bf.set(h3);
		}
	private:
		bitset<6 * N> _bf;
		size_t len = 6 * N;
	};

}

    • 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
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120

    布隆过滤器探测

    	  bool test(const string& str)
		{
			size_t h1 = Hash1()(str) % len;
			size_t h2 = Hash2()(str) % len;
			size_t h3 = Hash3()(str) % len;
			if (_bf.test(h1) == false)
			{
				return false;
			}
			if (_bf.test(h2) == false)
			{
				return false;
			}
			if (_bf.test(h3) == false)
			{
				return false;
			}
			return true;
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    布隆过滤器误判率测试

    • 创建一个字符串数组，对一个字符串进行哈希算法处理，放到数组里。
    • 布隆过滤器对数组的每个元素进行设置，再探测是否都存在。
    • 创建一个字符串数组，对同一个字符串进行另一种哈希算法处理，放到数组里，用原过滤器进行探测。
    • 创建一个字符串数组，换一个字符串进行相同方式算法处理，放到数组里，用原过滤器进行探测。
    void TestBloomFilter()
	{
		/*BloomFilter<100> bf;
		bf.Set("张三");
		bf.Set("李四");
		bf.Set("牛魔王");
		bf.Set("红孩儿");

		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;*/
		
		BloomFilter<100> bf;
		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)
		{
			//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(6789 + i);
			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
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76

    布隆过滤器删除

    • 一般不支持删除，因为可能一个误判的值不在，删除对别的值映射状态造成影响。
    • 一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器（多给几个比特位），插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

    两个100G：query文件，查找交集

    在这里插入图片描述

    思路：

    • 将A大文件分成：A0.txt，A1.txt，…A199.txt；200个小文件。依次取大文件的query，进行字符串哈希算法转换%200，每一个都会进到一个小文件中。
    • 将B大文件分成：B0.txt，B1.txt，…B199.txt；200个小文件。依次取大文件的query，进行字符串哈希算法转换%200，每一个都会进到一个小文件中。
    • A、B大文件中相同的query会进去编号相同的小文件。只需要相同的小文件找交集即可。
    • A0.txt 读进一个setA；B0.txt读进一个setB，一个query在 A 和 B 中都存在就是其交集。
    • 依次类推。

    布隆过滤器应用场景

    • 可以应用在一些对误判要求没那么高的地方：注册昵称，允许误判：最多都用不了这个昵称；但这个昵称不存在就一定可以用。
    • 注册系统，根据手机号判定是否注册过，布隆过滤器标记所有注册过的手机号；不在，可以注册；在的话，再去服务器访问验证。
      在这里插入图片描述

    测试用例

    	void test()
	{
		Bloomfilter<2> bf1;
		bf1.set("https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html");
	}

	void test1()
	{
		Bloomfilter<2> bf1;
		//bf1.set("https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html");
		cout << bf1.test("https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html") << endl;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    课外阅读

    • 一致性哈希
      • 怎么确定用户数据放在哪台服务器上呢？对用户数据的唯一标识进行哈希算法转换% 服务器台数。
      • 服务器有宕机的时候，或者遭到一些不可抗力，用户数据没了，公司就G了的情况：
      • 将一个用户数据多存几份在不同的服务器上；将服务器在不同的地方多建几个。
      • 若增加了服务器，或某些服务器挂了，用户数据该怎么进行重新映射呢？…一致性哈希
    • 哈希与加密
  • 相关阅读:
    【贪心算法】：LeetCode860.柠檬水找零
    通过SOLIDWORKS Composer让自定义视图更智能
    大数据之初识Doris（一）
    麒麟v10安装Redis（ARM架构）
    聊聊自制的探索大全扑克牌
    LeetCode 1465. 切割后面积最大的蛋糕
    Echarts数据分析系统Data Analysis Platform使用说明文档
    Java 变得越来越像 Rust？
    IP地址，子网掩码，默认网关，DNS讲解
    微擎模块 抽奖天天乐1.3.3小程序开源未加密版 前端+后端
  • 原文地址：https://blog.csdn.net/WTFamer/article/details/125553777