C++之哈希 --- 哈希的应用（位图布隆过滤器)

一、位图

1.1 位图的基本概念

在如今网络交通高度发达的时代，网购已经成为我们日常生活中的一部分。没当双11到来，各大平台都会迎来一次网购的高潮。这就会让服务器短时间内获得高达几十亿上百亿的数据，那我们该如何去处理这海量的数据呢？这里给大家上一个腾讯的面试题。

面对如此海量的数据，我们传统的容器（如unordered_map，map，vector等）似乎都无法驾驭这如此庞大的数据量。那我们该如何解决这个问题呢？
先给出两种常规的思路：

第三种方法当然是采用我们的位图啦，那什么是位图呢？其又是如何解决这个问题的呢？

位图概念

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

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

判断一个数是否存在，我们只用了一个比特位就可以判断，这大大降低了我们的内存消耗。原本40亿数据要占用16GB的空间。现在只需要0.5G的内存就能处理了。

2.2 位图的模拟实现

其实C++的库里也有对应的位图

这里我们主要实现3个功能：

set(size_t x) ：将对应数字位置为1
reset(size_t x) ：将对应数字位置清0
test(size_t x) ：查找该数字是否存在

实现位图我们主要要解决的问题就是，处理好位置映射的问题，这里我用一张图来好好解释解释：

那么接下来直接上代码：

template<size_t N>  //需要多少比特位class bitmap {public:bitmap() {_bits.resize((N >> 5) + 1, 0);}void set(size_t x)//将一位置为1{int i = x / 32;int j = x % 32;_bits[i] |= (1 << j);}void reset(size_t x)//将一位置为0{int i = x / 32;int j = x % 32;_bits[i] &= (~(1 << j));}bool test(size_t x)//查找该数字是否存在{if (x > N) return false;int i = x / 32;int j = x % 32;return (_bits[i]>>j)&1;}~bitmap(){}private:vector<int> _bits;};

二、布隆过滤器

2.1 布隆过滤器的基本概念

我们先来了解一下布隆过滤器的背景：

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

这里举一个具体的例子来说明布隆过滤器的插入操作：

要是我想查找香蕉在不在，只需要根据不同的hash算法，算出对应的红色位置是否都为1就可以了
同时根据这张图，要给大家传递的一个概念是：

可以发现香蕉和菠萝有一个映射位置重合了，那么也就是说在之后插入数据的过程中，有可能该数据的所有hash位置都与其他数据的hash位置重合，导致这个数据并没有加入到我们的布隆过滤器中。由此我们可以得出一个结论：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

2.2 布隆过滤器的模拟实现

这块话不多说直接上代码（这里的布隆过滤器复用了刚刚的位图代码）

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 ,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash,class K = string>class BloomFilter{public:BloomFilter() {}void set(const K& key){size_t index1 = HashFunc1()(key) % (_ratio * N);size_t index2 = HashFunc2()(key) % (_ratio * N);size_t index3 = HashFunc3()(key) % (_ratio * N);_bt.set(index1);_bt.set(index2);_bt.set(index3);}bool test(const K& key){size_t index1 = HashFunc1()(key) % (_ratio * N);if (_bt.test(index1) == false) return false;size_t index2 = HashFunc2()(key) % (_ratio * N);if (_bt.test(index2) == false) return false;size_t index3 = HashFunc3()(key) % (_ratio * N);if (_bt.test(index3) == false) return false;return true;}~BloomFilter() {}private:const static size_t _ratio = 5;bitmap<_ratio * N> _bt;};