布隆过滤器(Bloom Filter)

当判断某个数据是否存在时,经常会容易想到HashTable,将值映射到HashTable的key中,通过查找,使用O(1)的时间复杂度判断,数据是否存在。在数据量很小时,可以这样做,但若是数据量很大,成千上亿条数据,HashTable就会十分浪费空间。

采用bitset的方式,也可判断某个数据是否存在。但位图一般只处理整形,如字符串就无法处理。

布隆过滤器是采用:Hash和bitse相结合的方式

布隆过滤器概念

布隆过滤器是由布隆在1970年提出的一种紧凑型,比较巧妙的概率性数据结构,其特点是高效的插入和查找由多个HashFunc,将一个数据映射到位图中,该方式可以提升查找的效率,且节省大量的内存空间。

如:

布隆过滤器(Bloom Filter)_第1张图片
Bloom通过HashFunc1()映射到位置8,通过HashFunc2()映射到24;
Filter通过HashFunc1()映射到位置24,通过HashFunc2()映射到11;

类模型:
这里的借用了位图结构,可参考:https://blog.csdn.net/w903414/article/details/113999327

class BloomFilter
{
     
public:
	BloomFilter(size_t size = 100)//比特位数
		:_bit(5 * size)
		,_size(0)
	{
     }
	void Insert(const T& key)//插入数据
	{
     
		size_t bitcount = _bit.Size();//求出比特位数
		size_t index1 = DToInt1()(key) % bitcount;//哈希计算位置,这里使用的是仿函数
		size_t index2 = DToInt2()(key) % bitcount;
		size_t index3 = DToInt3()(key) % bitcount;

		_bit.Set(index1);//设置为1
		_bit.Set(index2);
		_bit.Set(index3);
		++_size;//元素个数增加
	}
private:
	BitSet _bit;
	size_t _size;//元素个数
};

布隆过滤器的查找

分别计算该值每个HashFunc()对应的比特位置是否都为1,如果都为1,则数据可能存在,如果有一个为0,那么数据一定不存在。

即:布隆过滤器判断某个数据不存在时,则数据一定不存在,判断数据存在时,该数据可能存在,因为布隆过滤器存在误判的情况。

就如上图,若有一个数据“bloger”,通过HashFunc(),分别映射到了8号位置和24号位置。此时就会存在误判,该数据其实不存在,但结果返回的是存在。

	bool IsInBloomFilter(const T& key)
	{
     
		size_t bitcount = _bit.Size();//求出比特位数
		size_t index1 = DToInt1()(key) % bitcount;//哈希计算位置
		size_t index2 = DToInt2()(key) % bitcount;
		size_t index3 = DToInt3()(key) % bitcount;

		//同时存在为1时,则数据可能存在
		if (_bit.Test(index1) && _bit.Test(index2) && _bit.Test(index3))//存在误判
			return true;

		return false;
	}

布隆过滤器的删除

布隆过滤器不能直接删除,因为删除一个数据时,会影响其它元素的判断。

如上图中,删除“Bloom”,会同时删除位置8和24,就会影响“Filter”数据的判断,位置24被删除了,则为0;

有大佬又引入了 Counting Bloom Filter,它将标准布隆过滤器的每一位扩展为一个小的计数器(Counter),在插入数据时给对应的HashFunc()求得的位置Counter 的值分别加 1,删除元素时给对应的Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价, 给 Bloom Filter 增加了删除操作。
布隆过滤器(Bloom Filter)_第2张图片
缺陷:

  1. Counting Bloom Filter解决了标准BloomFilter不能删除数据的问题,但引入计数器就会造成资源的浪费。
  2. 同BloomFilter无法确定数据是否真正存在;
  3. 选取的计数器位数的问题,当数据很大,同时映射到一个位置数很多时,就会出现计数回绕。

布隆过滤器的优缺点

优点:

  1. 插入和查询数据的时间复杂度为O(K),K为哈希函数的个数,与数据量大小无关;
  2. 哈希函数之间没有关系,方便并行计算;
  3. 布隆过滤器不需要存储数据本身,在对某些数据严格保密的场景下有很大优势;
  4. 能够承受一定误判,布隆过滤器比其它数据结构有很大空间优势;
  5. 数据很大时,布隆过滤器可以表示全部数据;
  6. 使用同一组哈希函数的布隆过滤器可以进行交、并、差运算。

缺点:

  1. 存在误判率,不能准确判断数据是否存在;
  2. 不能获取数据本身;
  3. 不能删除数据;
  4. 采用计数删除,会存在计数回绕。

完整代码:

#include "BitSet.hpp"
struct HashStr1
{
     
	//BKDRHash
	size_t operator()(const std::string& str)
	{
     
		size_t ret = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
     
			ret = ret * 131 + str[i];
		}
		return ret;
	}
};

struct HashStr2
{
     
	//DJBHash
	size_t operator()(const std::string& str)
	{
     
		size_t ret = 5381;
		for (size_t i = 0; i < str.size(); ++i)
		{
     
			ret += (ret << 5) + str[i];
		}
		return ret;
	}
};

struct HashStr3
{
     
	//SDBMHash
	size_t operator()(const std::string& str)
	{
     
		size_t ret = 5381;
		for (size_t i = 0; i < str.size(); ++i)
		{
     
			ret = str[i] + (ret << 6) + (ret << 16) - ret;
		}
		return ret;
	}
};

template<class T, class DToInt1 = HashStr1, class DToInt2 = HashStr2, class DToInt3 = HashStr3>
class BloomFilter
{
     
public:
	BloomFilter(size_t size = 100)
		:_bit(5 * size)
		,_size(0)
	{
     }

	void Insert(const T& key)
	{
     
		size_t bitcount = _bit.Size();//求出比特位数
		size_t index1 = DToInt1()(key) % bitcount;//哈希计算位置
		size_t index2 = DToInt2()(key) % bitcount;
		size_t index3 = DToInt3()(key) % bitcount;

		_bit.Set(index1);//设置为1
		_bit.Set(index2);
		_bit.Set(index3);
		++_size;//元素增加
	}

	bool IsInBloomFilter(const T& key)
	{
     
		size_t bitcount = _bit.Size();//求出比特位数
		size_t index1 = DToInt1()(key) % bitcount;//哈希计算位置
		size_t index2 = DToInt2()(key) % bitcount;
		size_t index3 = DToInt3()(key) % bitcount;

		if (_bit.Test(index1) && _bit.Test(index2) && _bit.Test(index3))//存在误判
			return true;

		return false;
	}
private:
	BitSet _bit;
	size_t _size;//元素个数
};

部分参考:
[1]:https://zhuanlan.zhihu.com/p/43263751
[2]:https://cloud.tencent.com/developer/article/1136056
[3]:https://www.cnblogs.com/liyulong1982/p/6013002.html

你可能感兴趣的