位图与布隆过滤器

前言

在前面两个章节中我们详细讲解了哈希表的实现，今天我们就来看一看哈希的应用，也就是位图与布隆过滤器。我将与题目相结合来分别实现这两种应用。

位图

题目

 比如说有一个数33，该如何考虑存放呢？

1.首先应该先找到在这个数组的第几个整形中。

2.找到在这个整形的第几位。

这类似于进制问题，找到在第几个整形，只需要用33/32，得到1，也就是下标为一的整形

找到在第几位只需要33%32便查到了在第几位。

这就是 33的位置，通过这个例子，我们知道每一个数字都能一一对应一个比特位，这样我们就能准确找到该位置，判断是0还是1来确定存不存在。现在的问题就是如何让那个比特位变成0或者1，通常我们都采用逻辑与和逻辑或来实现。

1.将该位置变为1：

---

 

我们只需要将此位置与1进行或等，其余部分为0即可，该如何实现呢？其实也很简单，前面我们算出了他在第几个比特位，如在第j位，现在我们只需要将该位置所的整形或等上（1<<j）便可以实现该位置为1，其他位置保持不变。

2.将该位置变为0：

要想让此位置变成0，我们只需要将此位置与0进行与运算，其他位置全为1，不影响其他位，具体方法是将该位置所的整形与等上~（1<<j）。

---

依照上面的方法将所有数据存入到位图中后，当查找时，只需要在位图中找到该位置，看比特位是否为1即可。需要注意的是，开空间时应该开N/32+1个大小的空间，因为c++中/号是整数除法向下取整。

概念

实现

 具体代码如下：

	template<size_t N>class bitset{public:bitset(){//_bits.resize(N/32+1, 0);_bits.resize((N>>5) + 1, 0);}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1<<j);}private:vector<int> _bits;};

这是简单的位图的实现，有时候还需要进行变形，如，找出海量数据中出现不超过两次的数字。

其实和这题道理一样，还是通过比特位来进行查找，我们可以开两个位图，那么在位图的相应位置会出现00 01 10 11四种情况，插入所有数据后再遍历一遍就可以找到这些数字。

布隆过滤器

解析

位图这个思想可以适用于整形，但是如果数据是字符串string就不太好实现，那么我们在哈希表中的用到的字符串哈希算法便可以很好的起到作用，我们把string通过算法转换为整形就能很好的映射到位图中，但是不同于整形的是，整形是一一对应的，而字符串转换后的值可能还是出现哈希冲突的情况，我们说过，哈希冲突是无法消除的，只能尽可能避免。

比如这种情况apple并不存在，但再查询时发现该位置为1，就会出现误判的情况。（insert的插入导致了该位置为1，但正好apple通过转换后也是映射到这个位置） 

这时布隆便想到了一种方法，我们可以把string通过算法转换为多个不同的整形，实现一对多的映射关系，这样就能大大提高准确率。实际中，通常用三个不同的算法进行转换。

在这种方法下，即使出现了交叉，还可以通过其他的位置来进行判断，这样就能提高准确率。

现在我们来想一个问题，我查询一个值，得到的结果有两种：

一个是存在，一个是不存在，那么在结果的角度看哪种结果是可靠的呢？

 还是拿这个图片来鞭尸，我们发现返回存在这种情况是不可靠的，因为它可能出现映射位置相同的情况，但该字符串并没有在位图中。返回不存在是可靠的，因为如果不存在，查找该位置的比特位为0，说明不可能有值在这里存在过。

实现

现在我们来进行实现，我们用三个比较优秀的算法来对字符串进行处理。如下：

struct BKDRHash
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};struct APHash
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); i++){char ch = key[i];if ((i & 1) == 0){hash ^= ((hash << 7) ^ ch ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string& key){size_t hash = 5381;for(auto ch : key){hash += (hash << 5) + ch;}return hash;}
};

 下面开始我们的过滤器实现

template<size_t N, class K = string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash ,class HashFunc3 = DJBHash>
class BloomFilter
{
public:void Set(const K& key){size_t hash1 = HashFunc1()(key) % N;size_t hash2 = HashFunc2()(key) % N;size_t hash3 = HashFunc3()(key) % N;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);/*cout << hash1 << endl;cout << hash2 << endl;cout << hash3 << endl << endl;*/}// 一般不支持删除，删除一个值可能会影响其他值// 非要支持删除，也是可以的，用多个位标记一个值，存引用计数void Reset(const K& key);bool Test(const K& key){// 判断不存在是准确的size_t hash1 = HashFunc1()(key) % N;if (_bs.test(hash1) == false)return false;size_t hash2 = HashFunc2()(key) % N;if (_bs.test(hash2) == false)return false;size_t hash3 = HashFunc3()(key) % N;if (_bs.test(hash3) == false)return false;// 存在误判的return true;}private:bit::bitset<N> _bs;
};

判断时，如果有一个位为0，直接返回false，而且是准确的，都不为0返回true，但存在误判。

这就是位图和布隆过滤器的实现，创作不易，恳求点赞关注谢谢谢谢谢谢谢谢