【C++杂货铺】海量数据处理（位图、布隆过滤器）

本文主要是介绍【C++杂货铺】海量数据处理（位图、布隆过滤器），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🌈前言🌈

📁 位图

📂 概念

📂 模拟实现

📂 C++中位图

📂 位图的优缺点

📁 布隆过滤器

📂 概念

📂 模拟实现

📂 应用场景

📁 海量数据处理

📁 总结

🌈前言🌈

本期【C++杂货铺】，将介绍关于哈希表的扩展内容，即位图和布隆过滤器，以及如何通过位图和布隆过滤器解决海量数据处理问题。

哈希表作为一种数据结构，可以达到O(1)的时间复杂度内找到数据，但是C++中哈希表作为一种数据结构，是在内存中处理数据，如何解决上亿数据的查找问题呢？因此就引入了位图和布隆过滤器。

本期内容需要你了解一定哈希表的内容，可以阅览下面这篇文章：

【C++杂货铺】unordered系列容器_unordered c++-CSDN博客

📁 位图

📂 概念

我们使用哈希表就是为了来查找数据，那我们转换一下思想，哈希表不在用来存储数据，而是通过一个标记位，来标识该数据是否存在。

我们可以使用一个二进制比特位来表示是否存在数据。设计一个用位置表示数据是否存在的数据结构，这个结构就是位图。

位图本质就是一个直接定址法的哈希表，每一个整形映射一个bit位，位图提供了bit位的操作接口。

一个int类型4字节，32位bit，就可以表示32个数据的有无。C/C++没有提供位的类型，我们就可以通过对整形进行位运算来控制对应的位。

例如一个数据X，通过 X / 32确定存储在哪一个整形，X % 32 确定在整型的那一个位，这样就将X值映射成vector的第i个整形数据的第j位。

我们只需要开除2^32大小（计算机内整形的最大取值范围）的位图就可以表示出上百亿数据的有无。

📂 模拟实现

    template<size_t N = -1>class BitSet{public:BitSet(){_bitset.resize(N / 32 + 1,0);}void Set(size_t n){int i = n / 32;int j = n % 32;_bitset[i] |= (1 << j);}void Reset(size_t n){int i = n / 32;int j = n % 32;_bitset[i] &= ~(1 << j);}bool Test(size_t n){	int i = n / 32;int j = n % 32;return _bitset[i] & (1 << j);}size_t Size(){return  _bitset.size();}private:std::vector<size_t> _bitset;};

📂 C++中位图

bitset - C++ Reference

📂 位图的优缺点

优点：增删查改速度快，节省空间。

缺点：只能适用于整形数据。

📁 布隆过滤器

📂 概念

如果不是整形数据，我们就要使用布隆过滤器了。

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

布隆过滤器复用了位图，首先将数据通过多个哈希函数映射成不同的值，将对应的值映射到特定的位上，只要映射的位全部为1，就可以确定该数据是存在的。

我们可以看到通过哈希函数可能产生哈希冲突，但是布隆过滤器并不用来存储数据，而是用来判断数据是否存在的，因此不需要解决冲突，而是想办法降低冲突。

布隆过滤器降低冲突的目的就是最大程度上确定该数据是否存在，判断数据是否存在就是看是否有0的存在，如果映射值1中有一个为0，就说明该数据不存在。

但是最坏情况下，可能存在不存在的数据，通过哈希函数，得到的映射值在整型所在位上的值为1，这就可能导致误判，即不存在的数据在映射值的位上没有找到0。

误判推导：

这里不再过多介绍公式推导流程，我们只需要知道结论即可。即

布隆过滤器（Bloom Filter）- 原理、实现和推导_布隆过滤器原理-CSDN博客

删除问题：

布隆过滤器默认是不支持删除的，因为比如"猪八戒“和”孙悟空“都映射在布隆过滤器中，他们映射的位有⼀个位是共同映射的(冲突的)，如果我们把孙悟空删掉，那么再去查找“猪⼋戒”会查找不到，因为那么“猪八戒”间接被删掉了。

解决方案：可以考虑计数标记的方式，⼀个位置用多个位标记，记录映射这个位的计数值，删除时，仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果⼀个值不在布隆过滤器中，我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，⼀个确定存在的值，可能会变成不存在，这里就很坑。当然也有人提出，我们可以考虑计数方式支持删除，但是定期重建⼀下布隆过滤器，这样也是⼀种思路。

📂 模拟实现

struct HashFuncBKDR
{/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》// ⼀书被展⽰⽽得 名，是⼀种简单快捷的hash算法，也是Java⽬前采⽤的字符串的Hash算法累乘因⼦为31。size_t operator()(const std::string& s){size_t hash = 0;for (auto ch : s){hash *= 31;hash += ch;}return hash;}
};
struct HashFuncAP
{// 由Arash Partow发明的⼀种hash算法。size_t operator()(const std::string& s){size_t hash = 0;for (size_t 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 HashFuncDJB
{// 由Daniel J. Bernstein教授发明的⼀种hash算法。size_t operator()(const std::string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};template<size_t N,size_t X = 5,class K = std::string,class Hashfunc1 = HashFuncBKDR,class Hashfunc2 = HashFuncAP,class Hashfunc3 = HashFuncDJB>class BloomFilter{public:void Set(const K& key){size_t bit1 = Hashfunc1()(key) % M;size_t bit2 = Hashfunc2()(key) % M;size_t bit3 = Hashfunc3()(key) % M;_bits.Set(bit1);_bits.Set(bit2);_bits.Set(bit3);}bool Test(const K& key){size_t bit1 = Hashfunc1()(key) % M;if (!_bits.Test(bit1))	return false;size_t bit2 = Hashfunc2()(key) % M;if (!_bits.Test(bit2))	return false;size_t bit3 = Hashfunc3()(key) % M;if (!_bits.Test(bit3))	return false;return true;}private:static const size_t M = N * X;BitSet<M> _bits;};void TestBloomFilter1(){std::string strs[] = { "百度","字节","腾讯" };BloomFilter<10> bf;for (auto& s : strs){bf.Set(s);}for (auto& s : strs){std::cout << bf.Test(s) << std::endl;}for (auto& s : strs){std::cout << bf.Test(s + 'a') << std::endl;}std::cout << bf.Test("摆渡") << std::endl;std::cout << bf.Test("百度") << std::endl;}
}