【数据结构取经之路】布隆过滤器BloomFilter原理、误判率推导、代码实现

背景介绍

简介

布隆过滤器的实现思路

布隆过滤器的作用

布隆过滤器误判率推导过程

布隆过滤器的实现

布隆过滤器的删除问题

布隆过滤器的优缺点

布隆过滤器的应用

背景介绍

在一些场景下面，有大量数据需要判断是否存在，而这些数据不是整形，导致位图就派不上用场。这时，时代无比呼唤一种新的解决方案，布隆过滤器也就应运而生了。

简介

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(哈希函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好得多，缺点是有一定的误判率和删除困难。

布隆过滤器的实现思路

BloomFilter的实现思路就是把key通过哈希函数转换成整型后在映射一个二进制位。也就是说，BloomFilter = bitset(位图) + Hash函数。考虑到只映射一个位的话哈希冲突的概率较大，所以可以通过几个哈希函数转换出几个整型，然后映射多个二进制位，降低冲突率。

布隆过滤器的作用

布隆过滤器可以告诉我们“某样东西一定不存在或者可能存在”。换句话说，它判断一个值key在是不准确的，但是判断一个值key不在是准确的。下面对这句话做出解释。

判断一个值在是不准确的。原因在于布隆过滤器存在误判，也就是说不同的key映射的3个位置上都恰好与其他元素冲突，而且这些位置都被置为了1，返回结果就是在——这就是误判。

判断一个值不在是准确的。首先，导致返回结果为不存在有两种情况，第一：元素key本来就存在，但是由于误判，导致返回结果为不存在。第二：元素key本来就不存在，然后返回结果为不存在。针对第一种情况，因为布隆过滤器保证元素不被错误的删除，元素存在的话它映射的3个二进制位一定为1，所以这种情况不可能发生。只能是第二种情况，即只有不存在的值返回结果才是不存在，证明了判断一个值不在是准确的。

布隆过滤器误判率推导过程

数据量：n

误判率：p

bit数组的大小：m

哈希函数的个数：k

针对某个二进制位：

经过1次哈希函数映射后，不被置为1的概率： $1 - \frac{1}{m}$

经过k个哈希函数映射后该bit位仍未被置为1的概率： $(1 - \frac{1}{m})^{k}$ （某一个二进制位被置为1后，后面还是有可能会再次映射到该位置，故总的二进制位数还是m）

该二进制位在插入n个值后依旧未被置为1的概率： $(1 - \frac{1}{m})^{kn}$

则某个二进制位在插入n个值后被置为1的概率： $1 - (1 - \frac{1}{m})^{kn}$

故误判的概率： $(1 - (1 - \frac{1}{m})^{kn})^{k}$ ①

根据 $lim(1 + \frac{1}{x})^{x}= e(x\rightarrow \Join )$

①式可化为： $(1 - (1 - \frac{1}{m})^{kn})^{k}=$ $(1 - (1 + \frac{1}{-m})^{-m\cdot \frac{kn}{-m}})^{k}= (1 - e^{-\frac{kn}{m}})^{k}$ ②

令 $b= e^{\frac{n}{m}}$ ，则②式可化为： $(1 - b^{-k})^{k}$

误判率为k的函数，有 $f(k)= (1 - b^{-k})^{k}$

两边同时取对数，有 $lnf(k)= kln(1 - b^{-k})$

两边同时求导，有 $\frac{1}{f(k)}\cdot {f(k)}'= ln(1 - b^{-k})+k\cdot \frac{1}{1-b^{-k}}\cdot b^{-k}\cdot lnb$ ③

当 $f(k)$ 取最值时， ${f(k)}'= 0$ （最值点的导数为0，除了端点），则③式可化为： $ln(1 - b^{-k})+k\cdot \frac{1}{1-b^{-k}}\cdot b^{-k}\cdot lnb= 0$ ④

下面对④式进行化简：

$ln(1 - b^{-k})+k\cdot \frac{1}{1-b^{-k}}\cdot b^{-k}\cdot lnb= 0$

$(1 - b^{-k})ln(1 - b^{-k})+kb^{-k}lnb= 0$ （两边同时乘 $(1 - b^{-k})$ ）

$(1 - b^{-k})ln(1 - b^{-k})= -kb^{-k}lnb$ （移项）

$(1 - b^{-k})ln(1 - b^{-k})= b^{-k}lnb^{-k}$ （把-k移到lnb内）

观察等式两边的形式，可以得到 $1 - b^{-k}= b^{-k}$ ⑤

从⑤式中，推出 $b^{-k}= \frac{1}{2}$ ⑥

在⑥式中，把b换成 $e^{\frac{n}{m}}$ ，有 $e^{-\frac{n}{m}k}= \frac{1}{2}$

两边同时取对数，推出最佳的哈希函数个数 $k= ln2 \frac{m}{n}$

根据上述描述，误判概率也可写成 $p= (1-b^{-k})^{k}$ ⑦

把⑥式代入⑦式，有 $p= 2^{-k}$

上面已推出 $k= ln2 \frac{m}{n}$ ，则 $p=2^{-ln2\frac{m}{n}}$

两边同时取对数，有 $lnp=ln2^{-ln2\frac{m}{n}}$

可化简为 $lnp={-ln2\frac{m}{n}}ln2$

进一步化简 $lnp={-\frac{m}{n}}(ln2)^{2}$

进而推出bit数组的大小 $m=-\frac{nlnp}{(ln2)^{2}}$

$\frac{}{}$ 由误判率公式可知，在k⼀定的情况下，当n增加时，误判率增加，m增加时，误判率减少。

布隆过滤器的实现

经过上述大篇幅的推导，终于得于推出BloomFilter的误判率，接下来我们着手实现。

各种字符串Hash函数——这是一篇关于各种字符串Hash函数分析的博客，我们选出3个效率较好的来作为我们布隆过滤器的Hash函数。前面在BloomFilter的实现思路中提到，BloomFilter = bitset(位图) + Hash函数，我们的BloomFilter将基于标准库里的位图(当然，你也可以基于自己实现的位图)。

#pragma once
#include <bitset>
#include <string>
#include <iostream>

//字符串Hash函数
struct HashFuncBKDR
{
	size_t operator()(const std::string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash += hash * 31 + ch;
		}
		return hash;
	}
};

//字符串Hash函数
struct HashFuncAP
{
	size_t operator()(const std::string& str)
	{
		size_t hash = 0;
		for (size_t i = 0; i < str.size(); i++)
		{
			if ((i & 1) == 0)
				hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3));
			else
				hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5)));
		}
		return hash;
	}
};

//字符串Hash函数
struct HashFuncDJB
{
	size_t operator()(const std::string& str)
	{
		size_t hash = 5381;
		for (auto ch : str)
		{
			hash = hash * 33 ^ ch;
		}
		return hash;
	}
};

template <size_t N,
	size_t X = 6,
	class K = std::string,
	class Hash1 = HashFuncBKDR,
	class Hash2 = HashFuncAP,
	class Hash3 = HashFuncDJB>
	class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t hash1 = HashFuncBKDR()(key) % M;
		size_t hash2 = HashFuncAP()(key) % M;
		size_t hash3 = HashFuncDJB()(key) % M;

		//映射多个位
		_bs->set(hash1);
		_bs->set(hash2);
		_bs->set(hash3);
	}

	bool test(const K& key)
	{
		//有一个为0，则不存在
		size_t hash1 = HashFuncBKDR()(key) % M;
		if (_bs->test(hash1) == 0)
			return false;

		size_t hash2 = HashFuncAP()(key) % M;
		if (_bs->test(hash2) == 0)
			return false;

		size_t hash3 = HashFuncDJB()(key) % M;
		if (_bs->test(hash3) == 0)
			return false;

		return true;
	}
private:
	static const size_t M = X * N;
	std::bitset<M>* _bs = new std::bitset<M>;
};

void TestBloomFilter()
{
	BloomFilter<10> bf;
	std::string arr[] = { "百度", "字节", "腾讯" };
	for (auto& str : arr)
	{
		bf.set(str);
	}
	std::cout << bf.test("百度") << std::endl;
	std::cout << bf.test("摆度") << std::endl;
	std::cout << bf.test("摆渡") << std::endl;
}

布隆过滤器的删除问题

先说结论，布隆过滤器默认是不支持删除的。下面我们来分析原因。

请看上图，我们发现，obj1和obj2都映射到了3号位上（哈希冲突），当我们删除obj1时，3号位会被置为0，导致我们再去查找obj2时会找不到，这就相当于间接的把obj2删除了。关于这个问题，有这样一个解决方案：引用计数！一个位置用多个位标记，记录映射这个位的计数值，删除时仅仅减减计数值。我们思考一下，这个方案能完美解决布隆过滤器不好删除的问题吗？这个问题不着急回答，我们先来看看下面的场景。

当我们删除一个值key时，本来key是不在布隆过滤器里的，但由于误判（假设其中冲突的一个位置为上图的4号位），结果认为是key在，然后我们删除它。此时， 4号位的计数值减减，由1减为了0，这样也间接删除了tencent。上述问题的答案就不言而喻了。还有人提出这样一种思路，支持计数方式删除，但是定期重建布隆过滤器。