BloomFilter（布隆过滤器）

        哈希（散列）是在查找时利用到的思想体系。常见的查找思想有：

一、排序+二分查找

二、map和set，本质是AVL树和红黑树的思想

三、哈希思想：使用哈希表、使用位图用于大数据等特殊场景

        而本文要介绍的布隆过滤器也是哈希思想的体现，关于其使用场景会在本文详细介绍。

---

目录

一、概念

 二、代码实现

框架：

set和test

三、场景

---

一、概念

        在位图的使用场景中，局限于必须是大量整型数据，如果现有大量整型数据，通过模运算和除运算对应到位图的比特位中是没有任何问题的。但如果现有大量字符串或其他类型的数据，位图这个数据结构就束手无策了。

        于是，我们很容易想到String To Int，字符串转整型的哈希函数有许许多多，我们不需要担心这个，但是在大量数据的前提下，这些函数处理的结果一定会有大量的冲突，那这种方法到底可不可行呢？！

        因此，布隆提出一个思想，冲突是没有办法彻底避免的，但是可以尽可能降低冲突概率，实际应用场景中也存在允许小概率误判的场景。

        比如，现有字符串“上海”，“北京”，“广州”，使用布隆的思想，通过多个比特位来判断数据是否存在：

北京判断结果为存在：因为对应的多个比特位都存在（为1）

上海，广州同理

深圳判断结果为不存在：虽然深1的结果（为1），但是深2结果（为0），因此判断为不存在。

        这样一来，可以大大降低误判的概率，并且，一个值对应的哈希映射越多，误判的概率越低。

        这就是布隆思想。

---

        布隆思想存在误判的情况，但是生活中存在许许多多的场景允许误判，使用布隆思想是完全可行的。

        而布隆过滤器，通常是用在用户层和数据库之间的一层过滤器。

        用户输入结果被布隆过滤器判断为“不在”，布隆过滤器有权限直接返回结果。

        用户输入结果被布隆过滤器判断为“存在”，需要进一步由数据库判断。

        因为“结果”被误判的前提是“结果=存在”，如果“结果 = 不存在”，就不是误判。

---

 二、代码实现

框架：

template<size_t N,class Hash1 = HashFuncBKDR,class Hash2 = HashFuncAP,class Hash3 = HashFuncDJB>
class BloomFilter
{
private:static const size_t M = N * 5;bitset<M> _bs;
};

        Hash1\2\3都是字符串转整型的哈希函数，数学界对哈希函数有一定研究，选择哈希冲突尽可能小的函数即可。

        由于一个数据映射多个比特位，位图的范围应该较大。

---

set和test

三个哈希函数

struct HashFuncBKDR
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash *= 131;hash += ch;}return hash;}
};struct HashFuncAP
{size_t operator()(const string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0) // 偶数位字符:s[0]\s[2]\s[4]{hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));}else              // 奇数位字符{hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));}}return hash;}
};
struct HashFuncDJB
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};

---

set和test的实现

template<size_t N,class Hash1 = HashFuncBKDR,class Hash2 = HashFuncAP,class Hash3 = HashFuncDJB>
class BloomFilter
{
public:void set(const string& key){size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash2()(key) % M;size_t hash3 = Hash3()(key) % M;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const string& key){size_t hash1 = Hash1()(key) % M;if (_bs.test(hash1) == false)return false;size_t hash2 = Hash2()(key) % M;if (_bs.test(hash2) == false)return false;size_t hash3 = Hash3()(key) % M;if (_bs.test(hash3) == false)return false;return true;//即使这里返回存在，也可能是三个bitset位置都冲突，发生了误判}
private:static const size_t M = N * 5;bitset<M> _bs;
};

---

三、场景

---

         将query插入到set的时候，如果抛异常，说明空间不足了，表明当前Ai或Bi文件太大了，一般是冲突的值太多了，但是重复不多，处理方法是利用递归思想，再换一个哈希函数对这个文件切分找交集。