【C++布隆过滤器和哈希切分】

目录

1.布隆过滤器概念

2.布隆过滤器优点

3.哈希切分

---

 

位图储存的类型只能是整形，有没有储存自定义类型或者是字符串类型的“位图”呢？

1.布隆过滤器概念

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

简单一点的说就是：把字符串转化为整形存储在位图中，当时转化后的整形会和数组的比特位数量取模，取模的结果可能相同然后互相影响，那我们可以映射多个位置，来减少冲突的概率；

 
//不同的字符串用得到整形不一样
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
 
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};
 
struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};
 
template<size_t N,
	size_t X = 8,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
//x=8,char有8个比特位，N是char的数量
class BloomFilter
{
public:
	//映射3个位置
	void Set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;
 
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	//映射3个位置，有一个位置不在说明就不在，如果都在也有可能是误判
	bool Test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false;
 
		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false;
 
		size_t index3 = HashFunc3()(key) % len;
 
		if (_bs.test(index3) == false)
			return false;
 
		return true;  // 存在误判的
	}
 
	// 不支持删除，删除可能会影响其他值。
	void Reset(const K& key);
private:
	bitset _bs;
};

为什么布隆过滤器的特性： 某一个元素一定不存在或者可能存在

 

当插入元素和过滤器长度的比例越大于下面公式的结果，越误判率会小；但是开太多浪费，比例+1就好；

• 例如:插入元素个数是100；那么过滤器的长度开500；当时开空间的类型是char（字节），所以传模板参数应该/8，为50；BloomFilter<50> bft;

2.布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
3. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
4. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白 名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素

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

3.哈希切分

• 先算出文件大小，好切成多份准确数目的小文件
• 同一个元素映射的小文件的编号一定相同