哈希的应用(2)——布隆过滤器

2023-12-16 14:25:46

文章目录

布隆过滤器

布隆过滤器的概念

比如说一个论坛要实现注册功能，每个人都有昵称(主码)。现在新用户输入昵称或者修改昵称，提交的时候要如何快速检测一下昵称是否被用过？有人使用，则提示一下，没人使用，则提交成功。

此时就是一个key的模型。比如说此时已经有100亿个用户昵称了。

目前有两种方式：

用哈希表存储用户记录，缺点：浪费空间。
用位图存储用户记录。优点：节省空间、快。缺点：只能处理整数。不能解决哈希冲突。

因此针对字符串等更加复杂的类型，能否设计出一个位图一样的key在不在模型且节省空间的数据结构呢？

字符串可以通过BKDR算法变成整数，但是存在哈希冲突。但是位图只有一个位，也没法存指针形成单链表。

布隆解决方式：这个问题不能解决，那能不能降低误判概率？每个值映射一个位容易冲突，那把一个值映射成多个位。

映射多个位，还是可能存在误判，但是误判的概率低了，因为要映射的多个位都被占用冲突，才会误判。（类似字符串的双哈希、多哈希）

布隆过滤器，出发点是节省空间，效率高，一个值映射的位越多，消耗的空间越大。

将哈希与位图结合，即布隆过滤器，布隆过滤器是位图变形和延伸。

重点：

判断昵称用过：存在误判。当前昵称映射的位置可能被其他给占用了。

判断昵称没用过：准确的。

布隆过滤器的实现

哈希函数个数和布隆过滤器长度

k为哈希函数个数，m为布隆过滤器长度,n为插入的元素的个数,p为误报率。

k = m n l n ( 2 ) k=\frac{m}{n}ln(2) k=nmln(2)

当冲突概率高的时候可以类似控制平衡因子那样对布隆过滤器进行增容。

模拟实现

#pragma once
#include"BitSet.h"

struct HashBKDR
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
}; 

struct HashAP
{
	size_t operator()(const std::string& s)
	{
		register size_t hash = 0;
		size_t ch;
		for (long i = 0; i < s.size(); i++)
		{
			ch = s[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct HashDJB
{
	size_t operator()(const std::string& s)
	{
		register size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}

		return hash;
	}
};

template<size_t N,class K = string ,class Hash1=HashBKDR,class Hash2 = HashAP,class Hash3 = HashDJB>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t i1 = Hash1()(key) % N;//匿名对象
		size_t i2 = Hash2()(key) % N;
		size_t i3 = Hash3()(key) % N;

		cout << i1 << " " << i2 << " " << i3 << endl;
		_bitset.Set(i1);
		_bitset.Set(i2);
		_bitset.Set(i3);
		
	}
	bool Test(const K& key)
	{
		size_t i1 = Hash1()(key) % N;//匿名对象

		if (_bitset.Test(i1) == false)
		{
			return false;
		}
		size_t i2 = Hash2()(key) % N;
		if (_bitset.Test(i2) == false)
		{
			return false;
		}
		size_t i3 = Hash3()(key) % N;
		if (_bitset.Test(i3) == false)
		{
			return false;
		}
		return true;//这里三个位都在，有可能是其他key占的，是不准确的。
	}
private:
	Y::BitSet<N> _bitset;
};


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;
}

布隆过滤器的删除

一般情况下布隆过滤器是不能删除的。

但是有些场景可能只能妥协。

布隆过滤器删除的办法是引用计数。

使用多个位标识一个位置，多个值映射时，++计数；删除时，–计数。比如说4位，那么有16个值同时映射这个位置就不行了。整体还是比哈希好。

真的要实现的时候可以简单点，就实现8bit的，vector<char> _bitset，找位置如果存在就对该位置++，删除就–。

小结

布隆过滤器优点：节省空间(相比于平衡搜索树和哈希表)，效率高。

布隆过滤器缺点：存在误判，判断在是不准确的，判断不在是准确的。布隆过滤器一般不支持删除。

布隆过滤器使用的前提：能够容许他的误判。

实际场景中比如危险网站的检测，可以用布隆过滤器判断是否在危险网站集合中。

数据库是存在硬盘上的，假如系统所有用户的电话号码都存储在数据库的用户表。场景：注册新账号的时候在你没提交的时候提示一下这个手机号是否注册过。然而IO是比较慢的，这种场景可以在前端放一个布隆过滤器，里面放数据库的手机号，先布隆里面判在不在，布隆的判断不存在是准确的，直接就可以了。如果手机号在布隆过滤器中，这时候就要去数据库中找。

海量数据处理相关题

5.1哈希切割

给一个超过100G大小的log file,log中存着IP地址,设计算法找到出现次数最多的IP地址？

与上题条件相同，如何找到top K的IP？

如何直接用Linux系统命令实现？

对于大文件的思路是类似的，大文件不好处理就用哈希切分成小文件。

哈希切分的特点:相同的记录会进入下标相同的文件中。所以我们直接统计小文件中的次数即可。

假设生成A0~A99的100个文件，依次读取大文件中ip，计算每个ip映射的文件号，i=HashBKDR()(ip)%100，这个ip就进入 A i A_i Ai号小文件。

再依次读取A0~A99，读取Ai文件，如果Ai大于2G，可以类似上面切分一下。如果小于2G，可以直接统计每个小文件map<string,int>统计次数获得最多的。最后多个文件比较出最大的那个。

出现次数最多k个ip，用大堆还是小堆？建k个数的小堆。后面来的比top()大就进堆。

linux系统命令可以直接对文件sort然后count。

5.2位图应用

位图应用的题也可以哈希切分。

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

5.3布隆过滤器

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
1. 该query可能是http请求,也可能是sql查询。其实就是一个字符串。
2. 近似算法：将其中一个文件全部映射到布隆过滤器，另一个文件在过滤器中查询，找得到的就是交集。
3. 精确算法：一个文件大小是多少？100亿个query，假设平均每个query是20byte，那么100亿个query就是100亿*20字节,而之前算的1G大约是10亿字节，那么一个文件大约是200G。读取A文件中的100亿个query字符串，进行哈希切分。
  1. 我们有1G内存，哈希切分的每个小文件不一定平均，建议切成400份，创建A0~A399的400个小文件，读取文件中的每一个query，计算i=HashBKDR(query)%400。这个query就写入 A i A_i Ai的小文件中。
  2. 另一边创建B0~B399的400个小文件，读取文件中的每一个query，计算i=HashBKDR(query)%400。这个query就写入 B i B_i Bi的小文件中。
  3. 如果两边存在相同的query，则两者模后是在同一个下标的文件中的。因此可以在每个小文件中比较。哈希切分的特点:A和B文件中相同的query分别进入了下标相同的 A i A_i Ai和 B i B_i Bi文件中。
  5. 如果存在文件大小大于1G。若A0超过B0没超过，则放少的那个。如果两个都超过，可以尝试把整体400份再扩大，不行的话就算下大小把大的两个再切分一次。
如何扩展BloomFilter使得它支持删除元素的操作
1. 见删除一节。

扩展

以后简单扩展：一致性哈希，哈希与加密

关于一致性哈希：

在实际开发应用中，实际场景大致是这样的：

数据量大，单台机器存不下。
只存一台机器，安全性不足，多副本。副本之间物理上也是有很大的间距的，防止不可抗力。

这样就要考虑一个问题，找数据的时候服务器怎么知道要找的数据在哪一台机器。每个服务器相当于一个桶，进行编号，那么对于访问的ip进行取模来知道在哪个机器。这样就会同步产生一个问题，当扩容机器或者减少机器的时候，模的关系就发生变化了，怎么处理数据的问题。这就是一致性哈希处理的问题。

关于哈希与加密：密码学方向。

码农公寓