一. 位图

二.布隆过滤器

一. 位图

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

位图的底层是用数组实现的，数组的每一个元素的每一个二进制位都可以表示一个数据在或者不在，0表示数据存在，1表示数据不存在。

我们可以发现其实位图是一种直接定值的哈希，表示一个值在还是不在，只有0和1两种状态 1表示在0表示不在。

当我们探测到25比特位的值为1时，我们就可以判断出136这个数据存在。

位图中主要接口

1.set(置位即将对应比特位置为1）

对应位运算技巧：

1。将X最右边的n位清零：x & (~0 << n)
2.获取x的第n位值：(x >> n) & 1
3.获取x的第n位的幂值：x & (1 << n)
4.仅将第n位置为1：x | (1 << n)
5.仅将第n位置为0：x & (~(1 << n))
6.将x最高位至第n位（含）清零：x & ((1 << n) - 1)
7.将第n位至第0位（含）清零：x & (~((1 << (n + 1)) - 1))

对应代码：

void Set(size_t x){
			assert(x < N);

			// 算出x映射的位在第i个整数
			// 算出x映射的位在这个整数的第j个位
			size_t i = x / 32;
			size_t j = x % 32;

			// _bits[i] 的第j位标记成1，并且不影响他的其他位
			_bits[i] |= (1 << j);
		}

2.reset：将对用的比特位置0

**

**

对应代码：

void Reset(size_t x){
			assert(x < N);

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

			// _bits[i] 的第j位标记成0，并且不影响他的其他位
			_bits[i] &= (~(1 << j));
		}

** 3.Test(判断某个值是否存在）**

bool Test(size_t x)
		{
			assert(x < N);

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

			// 如果第j位是1，结果是非0，非0就是真
			// 如果第j为是0，结果是0，0就是假
			return _bits[i] & (1 << j);
		}

代码汇总：

template<size_t N>
	class BitSet
	{
	public:
		BitSet()
		{
			_bits.resize(N / 32 + 1, 0);
		}

		// 把x映射的位标记成1
		void Set(size_t x)
		{
			assert(x < N);

			// 算出x映射的位在第i个整数
			// 算出x映射的位在这个整数的第j个位
			size_t i = x / 32;
			size_t j = x % 32;

			// _bits[i] 的第j位标记成1，并且不影响他的其他位
			_bits[i] |= (1 << j);
		}

		void Reset(size_t x)
		{
			assert(x < N);

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

			// _bits[i] 的第j位标记成0，并且不影响他的其他位
			_bits[i] &= (~(1 << j));
		}

		bool Test(size_t x)
		{
			assert(x < N);

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

			// 如果第j位是1，结果是非0，非0就是真
			// 如果第j为是0，结果是0，0就是假
			return _bits[i] & (1 << j);
		}
	private:
		vector<int> _bits;
	};

**4.位图的应用 **

1. 快速查找某个数据是否在一个集合中
2. 排序
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记

二.布隆过滤器

1.布隆过滤器的引出
我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查`找呢？
1. 用哈希表存储用户记录，缺点：浪费空间.
2. 用位图存储用户记录，缺点：只能处理整型.
3. 将哈希与位图结合，即布隆过滤器.

** 2.布隆过滤器的概念 **

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

实现原理：

1. 创建一个m位的BitSet，先将所有位初始化为0

**

**

插入数据：

加入字符串，经过k个哈希函数，分别计算出k个范围是0 - m-1的值，将k个值对应的BitSet位 置1

检查流程：

1.将数据经过k个哈希函数，分别计算出k个值

2.若k个位都为1，则判断存在。（可能误判不同的值映射到同一个位置）

3.有任意1位是0，则肯定不存在。

4.布隆过滤器需要提前预定位数组的大小

删除

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

**缺陷：

1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕**

对应代码实现：

struct HashBKDR
{
	// "int"  "insert" 
	// 字符串转成对应一个整形值，因为整形才能取模算映射位置
	// 期望->字符串不同，转出的整形值尽量不同
	// "abcd" "bcad"
	// "abbb" "abca"
	size_t operator()(const std::string& s)
	{
		// BKDR Hash
		size_t value = 0;
		for (auto ch : s)
		{
			value += ch;
			value *= 131;
		}

		return value;
	}
};

struct HashAP
{
	// "int"  "insert" 
	// 字符串转成对应一个整形值，因为整形才能取模算映射位置
	// 期望->字符串不同，转出的整形值尽量不同
	// "abcd" "bcad"
	// "abbb" "abca"
	size_t operator()(const std::string& s)
	{
		// AP Hash
		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
{
	// "int"  "insert" 
	// 字符串转成对应一个整形值，因为整形才能取模算映射位置
	// 期望->字符串不同，转出的整形值尽量不同
	// "abcd" "bcad"
	// "abbb" "abca"
	size_t operator()(const std::string& s)
	{
		// BKDR Hash
		register size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}

		return hash;
	}
};

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

		

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

		// 这里3个位都在，有可能是其他key占了，在是不准确的，存在误判
		// 不在是准确的
		return true; 
	}

private:
	bitSet<N> _bitset;
	

};

布隆过滤器优缺点：

优点：

**1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 **

缺点：

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