• 哈希切割+布隆过滤器

    目录

    布隆过滤器

    布隆过滤器的提出

    布隆过滤器的概念

    布隆过滤器的实现

    插入

    set函数

    布隆过滤器长度的设置

    测试布隆误判率

    布隆过滤器删除

    布隆过滤器的实现场景

    布隆过滤器的扩展以及哈希切分

    布隆过滤器

    布隆过滤器的提出

    位图对于map/set这些的最大好处是，位图节省空间，效率高，但是位图也有局限性，它只能处理整数。那么当我们不想处理整数了，又想节省空间，这种方案就是布隆过滤器。布隆过滤器的特点还是节省空间，它可以处理自定义类型。

    布隆过滤器的概念

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

    比如说有“sort”,"left","right"着三个单词，有没有一种方法将这三个单词不用存储的方法，用最节省空间的方法来标记它们呢？可以将字符串转换成一个对应的整数，跟哈希表的方法一样。

    假设这三个字符串转换成20，30，45。当遇到sort，它对应的是20，去找它在不在，在就是1，不在就是0。

    用这种方法，比起红黑树这种有附带消耗的，非常节省空间。但是这种方案同样存在一个问题，相比于位图，位图是直接定址法，我们可以在可控范围内开辟空间并进行定位。但是字符串这种，比如说10个由小写字母构成的字符串，有26^10种可能性。这只是小写字母，还有大写字母，特殊符号，数字等等这些。字符串的数量非常大，如果不限定长度，字符串是无限的，整数是有限的。这样也就造成不同的字符串可能对应同一个数字，就会误判，本来还没有出现过的字符串，由于跟别的字符串使用同一个整数，而那个整数出现过，造成了误判。

    而这个误判：当字符串在的时候会误判，也就是说，假设abb和abaa这两个字符串映射同一个整数，abb出现过了，abaa没有出现过，会误判abaa也存在。而abb和abaa两个都不在的时候，不会造成误判，二者对应的整数都是0。而位图没有误判，因为位图没有哈希冲突，每个值一定有唯一的位置，因为它处理的是整数，如果所有的整数都在，也就42亿多。但是字符串太多一定存在冲突。

    1. 在。存在误判
    2. 不在，准确的

    我们想到了这个问题，布隆也会想到这个问题。布隆也允许哈希冲突，一个整数对应好几个字符串，但是需要降低误判率，那么如何降低误判率？当映射一个位置容易冲突，那么我们映射多个位置，假设一个字符串影射了三个位置。

    sort映射了三个位置，有一个位置和right冲突了，但是没关系。这时候每个值都映射三个位置，现在要冲突没那么容易，一个位置容易冲突，但是三个位置不容易冲突，即便三个位置也冲突，那么可以设置一个字符串映射八个位置。这样误判率就被降低了。

    但是这里映射的位置也不能太多，映射的多，占的空间也多，找的次数也多，我们使用位图这样的方式就是为了提高效率并且节省空间。映射的多了也就没那么节省空间了。

    布隆过滤器的实现

    插入

    这里用了模板class K,并给了默认值string，因为布隆过滤器最常见的是string类型。默认情况下是给string类型用的，这里也可以变成自定义类型，如果有Person类这样的，我们从中提取唯一信息，如身份证号，这样的能转成唯一数字的方式。

    还要给一个非类型模板参数N，因为给布隆开比特位。我们的字符串要映射三个比特的位置，所以要写三个仿函数方法:HashFunc1,HashFunc2,HashFunc3。因为模板参数的缺省值要从右往左缺省，所以class K=string要写在后面。

    对于字符串转整形的哈希函数有很多，具体的实现可以参考这篇文章：

    各种字符串Hash函数

    其中里面对哈希的各种算法效率做了排序，其中排列前3的算法分别是：BKDRHash,APHash,DJBHash。所以我们使用这几种算法就可以将同一个字符串转换成不同的整数值。

    1. struct BKDRHash
    2. {
    3. 	size_t operator()(const string& s)
    4. 	{
    5. 		size_t value = 0;
    6. 		for (auto ch : s)
    7. 		{
    8. 			value *= 31;
    9. 			value += ch;
    10. 		}
    11. 		return value;
    12. 	}
    13. };
    14.  
    15. struct APHash
    16. {
    17. 	size_t operator()(const string& s)
    18. 	{
    19. 		size_t hash = 0;
    20. 		for (long i = 0; i < s.size(); i++)
    21. 		{
    22. 			if ((i & 1) == 0)
    23. 			{
    24. 				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
    25. 			}
    26. 			else
    27. 			{
    28. 				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
    29. 			}
    30. 		}
    31. 		return hash;
    32. 	}
    33. };
    34.  
    35. struct DJBHash
    36. {
    37. 	size_t operator()(const string& s)
    38. 	{
    39. 		size_t hash = 5381;
    40. 		for (auto ch : s)
    41. 		{
    42. 			hash += (hash << 5) + ch;
    43. 		}
    44. 		return hash;
    45. 	}
    46. };

     我们来测试一下这三种哈希算法转换的情况，我们给出三个string值。

    1. template<size_t N,
    2. 	class K=string,
    3. 	class HashFunc1=BKDRHash,
    4. 	class HashFunc2=APHash,
    5. 	class HashFunc3=DJBHash>
    6. class BloomFilter
    7. {
    8. public:
    9. 	void Set(const K& key)
    10. 	{
    11. 		cout << HashFunc1()(key) << endl;
    12. 		cout << HashFunc2()(key) << endl;
    13. 		cout << HashFunc3()(key) << endl<<endl;
    14. 	}
    15. private:
    16. 	bitset<N> _bs;
    17. };
    18.  
    19. void TestBloomFilter()
    20. {
    21. 	BloomFilter<100> bm;
    22. 	bm.Set("sort");
    23. 	bm.Set("left");
    24. 	bm.Set("right");
    25. }

    结果：

    3536286
    1642402878
    2090731117

    3317767
    2264270545
    2090468272

    108511772
    2471782732
    273236323

    不同的哈希算法算出来的是不同的整数。

    set函数

    set函数将string映射的三个位置都设置成1，分别用三个哈希算法算出映射的三个整数后，因为成员变量是一个位图，所以直接用位图的set函数即可，set函数直接将对应位置由0变1。

    这样初步布隆过滤器的set我们就写好了。

    1. 	void Set(const K& key)
    2. 	{
    3. 		size_t index1 = HashFunc1()(key);
    4. 		size_t index2 = HashFunc2()(key);
    5. 		size_t index3 = HashFunc3()(key);
    6.  
    7. 		_bs.set(index1);
    8. 		_bs.set(index2);
    9. 		_bs.set(index3);
    10. 	}

    布隆过滤器长度的设置

    但是这里又出现一个问题，我们在实际测试的时候需要先将位图的比特位开好，但是我们并不知道到底要开多大，也不能每次都开到整数的最大位，BloomFilter<0xffffffff> bm;难道说每次用多少就开多少吗，也不完全是。

    可以看这篇文章

    如何算则哈希函数个数和布隆过滤器的长度

    如何选择适合业务的哈希个数和布隆过滤器的长度，可以推出一个公式，我们用这个公式来进行实践。

    这里n我们是知道的，假设k是3，ln2约等于0.7，最后带入3=m/n*0.7,最后得到4.2*n=m。所以布隆过滤器多一个数据要开大约4.2个比特位。所以我们直接按加入一个数据开4个比特位算。那么开100个数据，要开400个比特位。最后将string用哈希函数变换的整数就要模一下布隆过滤器的长度。开了400个比特位就要模400。

    1. void Set(const K& key)
    2. 	{
    3. 		size_t len = 4 * N;
    4. 		size_t index1 = HashFunc1()(key) % len;
    5. 		size_t index2 = HashFunc2()(key) % len;
    6. 		size_t index3 = HashFunc3()(key) % len;
    7. 		cout << index1 << " " << index2 << " " << index3 << endl;
    8. 	}
    9. private:
    10. 	bitset<N*4> _bs;

    我们来看看此时的string对应的三个哈希值是多少。

    测试布隆误判率

    从当前测试结果来看，误判率不是很高，当值大的时候，字符串长的时候，这样的方法冲突多不多呢，误判率大不大呢，需要我们写一个程序来测试一下。

    测试string字符串在不在

    这里先判断一个string在不在，因为写了三个哈希函数，如果三个都是1，都在了，并不能判断这个string是在的。而如果有一个不在了，那么这个string肯定是不在的。

    所以我们先算string对应三个哈希函数的位置，判断这个位置是不是1，在不在。如果分别测试了index1，index2,index3都是false，就说明这个string不在了。如果三个位置都是1，就可能存在误判，可能这三个位置都冲突了。

    1. 	bool Test(const K& key)
    2. 	{
    3. 		size_t len = 4 * N;
    4. 		size_t index1 = HashFunc1()(key) % len;
    5. 		if (_bs.test(index1) == false)
    6. 		{
    7. 			return false;
    8. 		}
    9. 		size_t index2 = HashFunc2()(key) % len;
    10. 		if (_bs.test(index2) == false)
    11. 		{
    12. 			return false;
    13. 		}
    14. 		size_t index3 = HashFunc3()(key) % len;
    15. 		if (_bs.test(index3) == false)
    16. 		{
    17. 			return false;
    18. 		}
    19.  
    20. 		//存在误判
    21. 		return true;
    22. 	}

    那么我们用一个字符串测试，我们将一个字符串加上一个值，我们将这个字符串加100次整数值，测试100次，然后到设置一个位图中。首先测试相同字符串的误判率，将第一个字符串加上另一个基准值6789来测试，测试这些值在不在位图中，同样也将这个字符串加上100次整数值。

    1. void TestBloomFilter2()
    2. {
    3. 	BloomFilter<100> bf;
    4. 	size_t N = 100;
    5. 	vector<string> v1;
    6. 	for (size_t i = 0; i < N; ++i)
    7. 	{
    8. 		//把这个字符串加上一个值，加100次
    9. 		string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
    10. 		url += to_string(1234 + i);
    11. 		v1.push_back(url);
    12. 	}
    13.  
    14. 	for (auto& str : v1)
    15. 	{
    16. 		bf.Set(str);
    17. 	}
    18.  
    19. 	for (auto& str : v1)
    20. 	{
    21. 		cout << bf.Test(str) << endl;
    22. 	}
    23. 	cout << endl << endl;
    24.  
    25. 	vector<string> v2;
    26. 	for (size_t i = 0; i < N; i++)
    27. 	{
    28. 		string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
    29. 		url += to_string(6789 + i);
    30. 		v2.push_back(url);
    31. 	}
    32. 	size_t n2 = 0;
    33. 	for (auto& str : v2)
    34. 	{
    35. 		if (bf.Test(str))
    36. 		{
    37. 			++n2;
    38. 		}
    39. 	}
    40. 	cout << "相似字符串误判率" << (double)n2 / (double)N << endl;
    41. }

     当我们使用不相似的字符串测试：相似字符串可以不能使用随机值来测试，可能会一样，造成误判率极高，但是不相似字符串可以用随机值来测试。

    1. 	vector<string> v3;
    2. 	for (size_t i = 0; i < N; i++)
    3. 	{
    4. 		string url = "zhihu.com";
    5. 		//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";
    6. 		//std::string url = "https://zhidao.baidu.com/question/1945717405689377028.html?fr=iks&word=ln2&ie=gbk&dyTabStr=MCw0LDMsMiw2LDEsNSw3LDgsOQ==";
    7. 		//std::string url = "https://www.cnblogs.com/-clq/archive/2012/01/31/2333247.html";
    8.  
    9. 		url += to_string(rand());//加上随机值
    10. 		v3.push_back(url);
    11. 	}
    12.  
    13. 	size_t n3 = 0;
    14. 	for (auto& str : v3)
    15. 	{
    16. 		if (bf.Test(str))
    17. 		{
    18. 			++n3;
    19. 		}
    20. 		cout << "不相似字符串误判率：" << (double)n3 / (double)N << endl;
    21. 	}

    我们发现，4*N的时候误判率基本在0.2以下。当开的空间大一点点，布隆过滤器的长度是插入元素的5倍。所以我们可以再添加一个非类型模板参数的模板，非类型模板参数都是常量。我们给到这个非类型模板参数X的默认值是4，插入一个数据开四个比特位的空间。现在作为测试布隆过滤器的误判率，我们将X改为5，看一下误判率

     通过第一个不相似字符串可以看出，误判率明显降低了。所以影响布隆过滤器的误判率的是X因子，X越大，误判率越小。所以布隆过滤器减少误判的最佳方法就是增加比率，基本上比率到达20，误判率就会极大的降低。

    布隆过滤器删除

    布隆过滤器一般不支持删除，如果一个string要删除，可能将哈希冲突的地方也给销毁掉，这样，本来存在的string也变得不存在，删除可能会影响其它值。

    那么我们就想支持它删除，应该怎么做呢？

    这里我们不适用一个比特位标记一个值，我们采用多个比特位标记一个值，其本质上还是引用计数。当这个值有多个string的一个哈希冲突了，那么我们记录这个值冲突的数量，当删除一个string就-1。

    每个标记位使用多个比特位，存储引用计数（有几个值影射了当前位置）。那么两个比特位最大映射值返回是0-3，最大到3；4个比特位映射范围是0-15，也就是说最多有15个值冲突了这个标记位；8个比特位映射个数范围是0-255；32位最大映射范围是42亿9千万。

     如果冲突个数超过3，那么可以改成更大的比特位来存储。这种方法支持删除，但整体消耗而言，布隆过滤器节省空间的优势下降了。

    布隆过滤器的实现场景

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

    场景一：

    比如说写一个注册系统，注册信息包括昵称，电话号码。这些信息都会被写入数据库中，那么怎么判断昵称有没有人用过呢？这里我们就可以采用布隆过滤器，因为可以存在误判，并且不在是准确的。当昵称没有被使用的时候，它一定是准确的；当昵称显示存在的时候，第一这个昵称确实被使用过了，第二有可能存在误判，本来昵称不存在，但是三个哈希位置都冲突了，导致误判存在。但是昵称误判了并没有很大的影响。如果这个电话号码注册过了，那么就显示“该号码已经注册”，如果这个号码不存在，那么就在后面打一个绿色的对勾。

    因为布隆过滤器中如果存在可能会不判，可以到数据库中再次查询昵称号码存不存在，那么有人说此时布隆过滤器还有价值吗？布隆过滤器依旧是有价值的，因为不在的场景已经被过滤掉，不用去查了，第二即便误判存在了，用户也不知道，那么不使用这个昵称也是可以的。

     场景二：

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

    如果数据存储在远程的服务器中，或是本地磁盘上。我们知道，访问本地磁盘很慢，访问远程服务器更慢，你还要走网络。所以我们可以在前端置一个布隆过滤器，要先查布隆过滤器在不在的场景，如果它在，它是不准确的，如果在，那么再去磁盘或者服务器上查看到底在不在，然后再返回；如果不在的话，直接在布隆过滤器上查看到不在，不在是准确的，直接返回。

    布隆过滤器的扩展以及哈希切分

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

    query就是sql语句，可以理解为一个字符串。，也可能是网络请求url，也就是网址。

    近似算法：布隆过滤器

    这里的近似就是让我们用布隆过滤器去做这道题。将一个文件的query语句放进布隆过滤器里，然后另一个文件查找在不在就是交集，但是这样的交集可能导致误判情况，不存在的也会算成交集。所以会存在不是交集的query会被当作交集。作为近似算法，这种方法是可行的。

    精确算法：哈希切分

    精确算法中，内存是放不下query的。假设每个query是10byte，那么100亿个query需要100G的空间。这个时候就不能用set存储了，并且set还有附带消耗，set的底层是红黑树，需要存储三叉链，颜色，这样代价非常大。

    这时候就可以用一个叫哈希切分的方法。

    100G我们处理不了，那么我们切成100份，一份就是1G。但是仅仅这样我们把一块A0放进set中，需要跟B0的每个模块都比较一下，因为相同的值可能在B0,或者B1，或者B99等等，都不确定。这样的话本质上还是没有提高效率。

    那么应该怎么哈希切分？读取query,然后使用一个哈希算法，假设使用BKDRHash，用BKDRHash算query字符串所对应的整数，然后用这个整数模上哈希切分个数的大小，假设我们切分200份，i=BKDRHash(query)%200,这个query就进入Ai号的小文件。B文件的query同理。

    这样A0跟B0找，上面的方法需要A0跟B0-199找，但是这次的方法只需要A0跟B0找，因为同一个query语句用BKDRHash(query)%200这个算法算出来的一定是同一个下标。所以Ai和Bi找交集即可。

    这道题中因为只有1G内存，100G的文件切成200份，一个小块就是500M，可以存放500M个整数，这样可以有个上下浮动，有的i下标的模块可能存的多一点，存了将近1G，有的少一点可能只存200M，如果觉得200份还是太大，可以切分500份都是可以的，但是且多少份是要根据自己的内存，所以要算一下总的大小，才能在这里有一个预估。

    那么如果Ai和Bi两个都太大，超过内存，可以考虑换个哈希算法，再切分一次

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

    因为这个log file大小已经超过100G，放进set中不现实，太大了，所以这道题还是要哈希切分。切200份出来，用BKDRHash算出ip所对应下标，再模200，算出0-199对应的的数。i=BKDRHash(ip)%200;然后同一个ip一定出现在同一个下标处，这样对每个小文件再用map来统计ip出现的次数，就是它准确的次数。pair<string,int> maxCountIP;

    扩展：

    找出出现次数最多的10个ip，这里我们就需要用堆了，先建立一个10个数据的小堆，然后每个pair数据跟堆顶比较，大的就会沉到堆下面，这样最后就找出10个出现次数最多的ip。

    我们可以用优先级队列建10个数据的堆，priority_queue<pair<string,int>,...> minHeap。这里就需要自己写仿函数来写小堆，最后出现次数最多的都进堆了。 

  • 相关阅读:
    CF750C (1600)
    Yapi idea插件使用
    攻不下dfs不参加比赛（九）
    Vue 商场首页头部布局
    [量化投资-学习笔记002]Python+TDengine从零开始搭建量化分析平台-MA均线的多种实现方式
    open-spider开源爬虫工具：抖音数据采集
    Android实现动态换肤-原理篇
    UGUI交互组件ScrollView
    ThingsBoard处理设备上报的属性并转换为可读属性
    mybatis
  • 原文地址：https://blog.csdn.net/qq_53413129/article/details/125380504