C++——位图和布隆过滤器

在C++中，哈希这种思想的应用场景有很多，位图就是其中的一种。

位图

位图：位图是一种哈希思想的产物，可以通过它来对数据进行快速的查找的方法，在位图中，有2种状态来表示在或者不在，即1/0。

位图应用场景

设想一下，如果给定10000个数据，让你判断其中的元素存不存在，你有几种方法？

1.用unordered_map来进行元素和个数的映射，如果存在就返回true
2. 排序+二分的思想
3. set + find

这时，我们发现1w个数据好像都可以用这种方式来查找，内存放得下，但是当数据量足够大的时候，我们就不能将数据直接放到内存中，这时我们就需要用到位图了。

一个字节 = 8bit，用每一个bit来表示存不存在，这大大减少了空间。

在这里插入图片描述

下面看bitset的简单定义

template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 32 + 1, 0);
		}
		
		//将元素对应的下标标志为1
		void set(size_t x)
		{
			assert(x <= N);

			size_t i = x / 32;
			size_t j = x % 32;

			_bits[i] |= (1 << j);
		}
		
		void reset(size_t x)
		{
			assert(x <= N);

			size_t i = x / 32;
			size_t j = x % 32;

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

		bool test(size_t x)
		{
			assert(x <= N);

			size_t i = x / 32;
			size_t j = x % 32;

			return _bits[i] & (1 << j);
		}


	private:
		vector<size_t> _bits;
	};

面试题：

给定100亿个整数，设计算法找到只出现一次的整数？

10亿字节 == 1GB
100亿个整数 == 400亿字节 == 40GB
可以发现，内存存放不下海量数据，用bitset就可以解决了。
我们定义2个位图，00 来表示出现了0次的元素，01表示出现了1次的元素，10表示2次及以上的元素

	template<size_t N>
	class two_bit_set
	{
	public:
		void set(size_t x)
		{
			// 00 -> 01
			if (_bs1.test(x) == false
				&& _bs2.test(x) == false)
			{
				_bs2.set(x);
			}
			else if (_bs1.test(x) == false
				&& _bs2.test(x) == true)
			{
				// 01 -> 10
				_bs1.set(x);
				_bs2.reset(x);
			}
		}
		//判断元素是否存在
		bool test(size_t x)
		{
			if (_bs1.test(x) == false
				&& _bs2.test(x) == true)
			{
				return true;
			}

			return false;
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};

布隆过滤器

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

实现原理：

布隆过滤器的结构：其实一个数组，如下图
在这里插入图片描述

当我们向布隆过滤器中插入baidu的时候，需要我们使用多个哈希函数来生成多个哈希值，将对应的位置置为1。baidu就是将1、4、7的位置设置为了1.
在这里插入图片描述

tencent就是将通过hash1、hash2、hash3函数来将对应的3、4、8设置为了1.
在这里插入图片描述

当我们去查询的时候，meituan的时候，如果通过布隆过滤器映射的位置是2、4、8，由于4是两个哈希值都将这个bit位设置为了1，8这个bit位在tencent中设置为了1，就只有2这个bit位没有设置为1，这是我们就可以说meituan这个值不存在。

随着增加的值越多，被设置为1的位置也就越多，如果这是出现了一个“taobao”，即使它没有被存储过，但是对应的位置也有可能被其他存储的值通过映射设置为了1。所以不能判断是存在的。

总结：
布隆过滤器：可以准确的判断一个值是不是不存在，但是不能肯定一个值存在

布隆过滤器的删除

布隆过滤器不能直接支持删除操作，因为在删除一个元素的时候，可能会影响其他元素

比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作