数据结构——位图布隆过滤器

一、位图

1.1 概念

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

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

1.2 实现

namespace bitmap
{// N是需要多少比特位template<size_t N>class bitset{public:bitset(){_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;};template<size_t N>class twobitset{public:void set(size_t x){if (_bs1.test(x) == false && _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}else if (_bs1.test(x) == true && _bs2.test(x) == false){_bs1.set(x);_bs2.set(x);}}void Print(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){cout << "1->" << i << endl;}else if (_bs1.test(i) == true && _bs2.test(i) == false){cout << "2->" << i << endl;}}cout << endl;}private:bitset<N> _bs1;bitset<N> _bs2;};
}

1.3 应用

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

二、布隆过滤器

2.1 引出

用哈希表存储用户记录，缺点：浪费空间
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理
将哈希与位图结合，即布隆过滤器

2.2 概念

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

2.3 实现

namespace bloomfilter
{struct BKDRHash{size_t operator()(const string& s){// BKDRsize_t value = 0;for (auto ch : s){value *= 31;value += ch;}return value;}};struct APHash{size_t operator()(const string& s){size_t hash = 0;for (long i = 0; i < s.size(); i++){if ((i & 1) == 0){hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));}}return hash;}};struct DJBHash{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}};template<size_t N,size_t X = 5,class K = string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash>class BloomFilter{public:void Set(const K& key){size_t len = X * N;size_t index1 = HashFunc1()(key) % len;size_t index2 = HashFunc2()(key) % len;size_t index3 = HashFunc3()(key) % len;/* cout << index1 << endl;cout << index2 << endl;cout << index3 << endl<<endl;*/_bs.set(index1);_bs.set(index2);_bs.set(index3);}bool Test(const K& key){size_t len = X * N;size_t index1 = HashFunc1()(key) % len;if (_bs.test(index1) == false)return false;size_t index2 = HashFunc2()(key) % len;if (_bs.test(index2) == false)return false;size_t index3 = HashFunc3()(key) % len;if (_bs.test(index3) == false)return false;return true;}// 不支持删除，删除可能会影响其他值。void Reset(const K& key);private:bitset<X* N> _bs;};
}