【C++进阶】位图和布隆过滤器

位图

位图概念

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

位图使用场景

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

这就是位图的使用场景。
那么我们如何判断一个数在不再为图里面呢？
我们只要看这个某个数对应的bit位是不是1就好了。
那么我们如何在位图里删除一个数呢？
比如我们要删除1呢？

我们要删除一个数也是如此，直接把这个数对应的bit位置成0就好。

位图的结构

位图的模板参数和成员变量：

构造

set

reset

test

完整代码

#pragma once
#include<vector>template<size_t N>
class BitSet
{
public:BitSet(){_bits.resize(N / 8 + 1, 0);}void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] |= (1 << j);}void reset(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] &= (~(1 << j));}bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);}
private:vector<char> _bits;
};void testbitset()
{BitSet<100> bs;bs.set(10);bs.set(15);bs.set(20);bs.set(31);cout << bs.test(10) << endl;cout << bs.test(11) << endl;cout << bs.test(31) << endl;
}

布隆过滤器

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

布隆过滤器概念

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

布隆过滤器结构

三个效率较高哈希函数：

布隆过滤器的模板参数和成员变量：


其中N是要存的数据个数，X为碰撞因子，碰撞因子越大，误判概率越小。当然不是越大越好，越大空间浪费也会越大，所以要始终5~10皆可以。

构造

因为布隆过滤器是对位图的封装，所以可以不用实现构造函数。

set

一个值映射多个位置

reset

布隆过滤器不支持实现reset因为，会影响其它值的判断。
举个例子：

比如上图已经存在了一些字符串，如果我们把其中的bit删除了会怎么样？

我们这时候可以看到，bit已经删除了，left、reset和bit有一块共同的空间，bit被删除了，这个共同的空间也被置成0，那么下次我们要判断left和reset存不存在的时候就会出错。所以不能实现删除操作。

test

所有映射位置都为1，才能表示存在

完整版代码

#pragma once
#include <bitset>
#include <string>
#include <time.h>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 = 8,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;_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;  // е}
private:bitset<X* N> _bs;
};