C++--哈希思想的应用--位图--布隆过滤器的介绍--1112

位图

位图解决的问题

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

分析：如果把每个数都放进来，需要的空间就是40亿*4字节，大概是16G空间。需要的空间过大，以至于用前几篇博客实现的哈希表、二叉树搜索树等都不能完整存储下来。

位图思想

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一 个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

即“开辟”一个可以容纳所有无符号数的的“数组”，该数组下标对应的就是数字，为1证明大小为下标的数字存在。

 位图的模拟实现

准备工作

位图本质上就是为了节省空间，用bit位来表示一个数存在与否。一个char类型是一个字节，其中有八个比特位，我们选用char来表示。

namespace chy
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			//一个字节有8个比特位 
			_bits.resize(N/8+1,0);//要把所有位数都包含进来 如果有22个数 要开 22/8+1个字节
		}
        //开始画饼
		void set(size_t x);//把x插入到 位图里面
		void reset(size_t x);//把x从位图里面删除
		bool test(size_t x);//测试x在不在位图里面
	private:
		vector<char> _bits;
	};
}

 具体功能的实现

        bitset()
		{
			//一个字节有8个比特位 
			_bits.resize(N/8+1,0);//要把所有位数都包含进来 如果有22个数 要开 22/8+1个字节
		}
		void set(size_t x)//把x插入到 位图里面
		{
			size_t i = x / 8; //找到在第几个字节
			size_t j = x % 8;//找到在该字节的第几位
			_bits[i] |= (1 << j); // |= 该为有1就1 符合要求
		}
		void reset(size_t x)//把x从位图里面删除
		{
			size_t i = x / 8; //找到在第几个字节
			size_t j = x % 8;//找到在该字节的第几位
 
			_bits[i] &= ~(1 << j);// ~(1<
		}
		bool test(size_t x)//测试x在不在位图里面
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}

测试用例

void test_bit_set1()
	{
		bitset<100> bs1;
		bs1.set(8);
		bs1.set(9);
		bs1.set(20);
 
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
 
		bs1.reset(8);
		bs1.reset(9);
		bs1.reset(20);
 
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
	}

用两个位的位图

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

如果用1个bit位来表示该数存在与否，那怎样才能表示出现的次数呢？——用两个bit位

零次 两个比特位分别为00 一次 两个比特位分别为01 两次及以上 两个比特位分别为10

两个位的位图的模拟实现

我们采用复用的写法。（因为bitset是库里面有的）

template<size_t N>
	class twobits
	{
	public:
		void set(size_t x)
		{
			bool flag = _bs1.test(x);//看看在位图一是否存在
			bool flag2 = _bs2.test(x);//看看在位图二里是否存在
			//第一次 两个flag都是false
			if (flag == false && flag2 == false)
			{
				//把00改成01
				_bs2.set(x);//用哪个位图插入都行 保持一致即可
			}
			else if (flag == false && flag2 == true)//把01变成11
			{
				//因为我从00变01是在_bs2中插入的
				_bs1.set(x);
				_bs2.reset(x);
			}
			else if (flag == true && flag2 == false)//从10变11
			{
				_bs2.set(x);
			}
		}
		void print_once()
		{
			for (int i = 0; i < N; i++)
			{
				if (_bs1.test(i) == false && _bs2.test(i) == true) cout << i << endl;
			}
		}
	private:
		//用两个以一位位图的成员变量来实现
		bitset_bs1;
		bitset_bs2;
	};

测试用例

void test_bit_set3()
	{
		int a[] = { 3, 4, 5, 2, 3, 4, 4, 4, 4, 12, 77, 65, 44, 4, 44, 99, 33, 33, 33, 6, 5, 34, 12 };
 
		twobits<100> bs;
		for (auto e : a)
		{
			bs.set(e);
		}
 
		bs.print_once();
	}

 布隆过滤器

大数据给我们不停的推荐新的内容，每次推荐时要去重，去掉已经看过的内容。这种模式如何实现呢？

如果我们使用哈希表存储用户记录，内存空间的使用是大问题。

如果使用位图，位图只能表示两种情况，针对于两态。对于字符串而言无法表示。

布隆过滤器：哈希与位图相结合。

布隆过滤器的概念

它是用多个哈希函数，将一个数据映射到位图结构中

 详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)

 

现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此可以很确定 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。

因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。

 布隆过滤器的查找

布隆过滤器就是将一个元素，采用多种映射方式到同一个位图里面，只要存在该比特位就为1，所以说如果该位的值是0，该元素就一定不存在！相反的，总会有极个别情况两个元素的映射方式刚好完全相同，这样即使通过过滤器表示该元素存在，也有一定可能是因为误判。

布隆过滤器的删除

布隆过滤器不能直接支持删除操作。因为一个元素有多个映射位，这些映射位有可能是相同的，如果直接在该位置上置0，一定会影响其他映射到该位的元素。

布隆过滤器的缺陷

1. 有误判率，不能准确判断元素是否在集合中

(补救方法：再建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题