位图在处理海量数据如 40 亿个整数时传统的哈希表、set容器等等会消耗大量内存这显然是不划算的。如果能用40亿个比特位来表示从0到40亿是否存在0不存在1存在就能节省大量空间这就涉及到了位图所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常用于判断某个数据是否存在。位图原理我们通常使用一个int数组来实现位图。一个int有 32 个比特位所以1个int可以表示32个数字的状态。于是可按下面方式进行映射。第 0 个 int (bits[0])负责管理数字0 ~ 31第 1 个 int (bits[1])负责管理数字32 ~ 63第 N 个 int (bits[N])负责管理数字 **N*32 ~ (N1)*32 - 1**关键算法定位与操作按上述方式若要在位图中增删数字x还得解决两个问题它在数组的哪个下标确定是第几个int它在 int 的第几个比特位确定是第几位这就用到了简单的数学运算数组下标i x / 32比特位j x % 32比如78应被下标2上的数字表示位于第12个比特位。确定第几位后实际中还需要通过位移和位运算实现更改下面演示在位图中插入3定位数组下标3 / 32 0所以操作bits[0]。比特位置3 % 32 3所以操作第 3 位。操作将数字1左移 3 位0000...00001000与bits[0]进行按位或|运算。结果位图数组下标0位置处变成了8用于表示0-31中只有3存在。操作流程简略图插入函数的代码实现void set(size_t input) { //确认在数组的的哪个位置 size_t pos input / 32;// //确认在第几个比特位,同时进行或等运算 _table[pos] | (1 (input % 32)); }如果要在位图中删除某数字定位方法和插入一致但1左移后要取反再用取反的结果和原数据做按位与运算从而保证其它数字的状态不被改变删除代码的函数实现void reset(size_t input) { size_t pos input / 32; _table[pos] ~(1 (input % 32)); }如果要查询位图中某个数字是否存在定位方法不变根据按位与运算得到的结果是否为0判断检查是否存在的函数实现bool test(size_t input) { size_t pos input / 32; size_t temp _table[pos]; if (temp (1 (input % 32))) {//如果不为0说明存在 return true; } return false; }位图应用找出整形数组中仅出现一次的数用两个位图AB表示数据存在状况遍历数组并做以下操作数据第一次在数组中被找到时在位图A中插入该数字位图B不做变动第二次出现时将位图A中删除该数字在位图B中插入该数字第三次及以后出现不做任何改动最后在位图A中存在的数字表明只出现过一次下面给出解决方案//找仅出现一次的数 template size_t N class twoBitmap { public: twoBitmap(const vectorsize_t input) { _input input; } void set(size_t input){ //判断数据在两个位图中的标记状态从而进行状态更改 if (!_bm1.test(input) !_bm2.test(input)) { _bm1.set(input); } else if (_bm1.test(input) !_bm2.test(input)) { _bm1.reset(input); _bm2.set(input); } else { return; } } //所有答案要输出到一个数组里面 void test() { for (auto i : _input) { if (_bm1.test(i) !_bm2.test(i)) { cout i endl; } } } private: vectorsize_t_input; BitmapN _bm1; BitmapN _bm2; };寻找两个数组的交集将两个数组分别映射到两个位图上然后遍历这两个位图如果都为1说明在这两个数组中都存在布隆过滤器位图针对整数操作而布隆过滤器则是以位图为底层的可将多种类型存入到位图中的一种结构实现原理布隆过滤器需要用户指定哈希函数通过哈希函数将数据转换成关键码再将关键码存入位图中即可。如何能避免两个不同数据关键码相同时引发的误判如下图所示解决方法使用三个哈希函数把同一个数据转换成三个关键码再将关键码在位图中分别标记在判断是否存在时如果检测到位图这三个关键码下标存放的都是1说明该数据存在。下图演示一个非整形如何存放到布隆过滤器中。注意这种方法不能完美解决重复的问题但大幅降低重复的概率三个哈希函数对不同数据计算出相同的三个关键码概率低通过增加哈希函数的数量可进一步减小误判的概率。此外使用布隆过滤器验证数据的存在有可能引发误判但验证数据不存在是完全没有问题的。布隆过滤器的实现以string类型为例给出三个针对string的哈希函数1. DJB2 Hash //公式 hash hash * 33 struct DJB2Hash { size_t operator()(const std::string str) const { unsigned long hash 5381; // 初始种子值 for (char c : str) { // hash * 33 可以写成 (hash 5) hash位运算更快 hash ((hash 5) hash) c; } return hash; } }; // 2. SDBM Hash // 公式 hash hash * 65599 c (65599 是一个质数) struct SDBMHash { size_t operator()(const std::string str) const { unsigned long hash 0; for (char c : str) { hash c (hash 6) (hash 16) - hash; // 等价于 hash c hash * 65599 } return hash; } }; // 3. BKDR Hash // 公式 hash hash * 131 c struct BKDRHash { size_t operator()(const std::string str) const { unsigned long long hash 0; const int seed 131; for (char c : str) { hash hash * seed c; } return (size_t)(hash 0x7FFFFFFF); // 确保返回非负数视具体需求而定 } };下面给出针对string类型的布隆过滤器的不完全实现注布隆过滤器有固定大小而关键码计算结果可能远大于这个大小所以每次得到的关键码需要模大小。templatesize_t N,class T string,class hash1DJB2Hash,class hash2SDBMHash,class hash3BKDRHash class Bloomfilter { public: //思路 //在位图中分别标记相应的关键码 void set(const T input) { _bloomfilter.set(hash1()(input) % N) ; _bloomfilter.set(hash2()(input) % N) ; _bloomfilter.set(hash3()(input) % N) ; } //在位图中分别删除相应的关键码实际上这样行不通见下文 void reset(const T input) { _bloomfilter.reset(hash1()(input) % N) ; _bloomfilter.reset(hash2()(input) % N) ; _bloomfilter.reset(hash3()(input) % N) ; } //若要检测某个值存在与否在位图中分别检测相应的关键码全在则该值存在 bool test(const T input) { if(_bloomfilter.test(hash1()(input) % N) _bloomfilter.test(hash2()(input) % N) _bloomfilter.test(hash3()(input) % N) ) { return true; } return false; } private: BitmapN _bloomfilter; };注意上面代码的删除其实并不正确比如a和b都映射到了位图上同一个位置删除a的时候导致b的映射也被删除了真正的删除需要用计数器记录位图每个位置被标记了几次但计数本身需要占用内存又和位图减少内存消耗的初衷相悖。这里不做代码演示。关于布隆过滤器的容量设置已知布隆过滤器一个数据要在位图上标注三个位置容量不大的情况下误判概率高如下图所示于是有人研究了位图容量和数据量的大小指定多少较优一般来说大小是元素个数的五倍左右误判的概率大幅降低。