12.3 开发过程

12.3.1 了解“布隆过滤器”的基本原理


1．什么是布隆过滤器

布隆过滤器是一种基于概率进行验重的数据结构。它的基本原理是：小概率事件不容易同时发生。

下面用生活中的例子来形象地描述一下布隆过滤器的实现原理。例如，要从100 000个人里通过以下指标寻找一个从没有见过的目标人物：

● 上衣是红色的。

● 裤子是黑色的。

● 鞋子是咖啡色的。

● 衣服左边口袋别了一个胸针。

● 背了一个绿色的双肩包。

● 双手捂着肚子。

● 脸上全是汗水。

● 表情痛苦。

虽然没有见过目标人物，但由于这些寻找的指标都比较独特，虽然每一个指标都会有一部分人满足，但是能同时满足这些指标的人非常少。所以，当看到一个满足所有指标的人时，这个人就是目标人物的概率非常大。如果这种检测指标足够多、足够随机，一个人能同时满足所有检测指标，则认错人的概率会小到可以容忍，此时就可以认为这种检测是足够准确的。

布隆过滤器使用多个哈希函数把同一个字符串转换成多个不同的哈希值，并记录这些哈希值的特征。下次再面对一个字符串时，布隆过滤器再次使用这些哈希函数把这个字符串转换为多个哈希值。如果这些哈希值全部符合原先的那个字符串对应的各个哈希值的特征，则认为这两个字符串是相同的。

2．哈希函数

哈希算法不是一种加密算法，而是一种不可逆的摘要算法。不同的哈希函数可实现不同的哈希算法。哈希函数能把一个字符串不可逆地转换为一个十六进制值，这个值可能是32位，也可能是64位戓128位，甚至更高。这个值叫作哈希值。

使用同一个哈希算法，能够把同一个字符串转成同一个哈希值。例如，在Python中，可以使用hashlib这个自带的模块计算哈希值，见下方的代码：

>>> import hashlib

>>> code = ’我叫青南’

>>> result = hashlib.sha256(code.encode()).hexdigest()

>>> print(result)

be30e0fe9d27d045ca730f0ca38cf4956c93e08a553e20e3db2856aeedb936cc

>>>

可以看出，使用 sha256算法计算“我叫青南”这个字符串的哈希值，得到的结果是be30e0fe9d27d045ca730f0ca38cf4956c93e08a553e20e3db2856aeedb936cc。这个结果虽然有数字又有字母，但实际上它是一个16进制的数，它是数字。

哈希函数对输入字符串的变化非常敏感，即使输入的字符串只有微小的改变，计算出来的哈希值也完全不同。例如在“我叫青南”后面加一个点，变成“我叫青南．”，继续使用sha256算法，得到的值为：8ea769251f0dae54547e0943aa2196b5161c1cb60a325860f488cb6cd9317a0d。

3．布隆过滤器的原理

假设选择K个哈希函数，对同一个字符串计算哈希值，就可以得到K个完全不同的哈希值。由于哈希值是数字，可以进行数学运算。那么让这K个哈希值同时除以一个数M，可以得到K个余数。记录下这K个余数。

对于一个新的字符串，重复这个过程，如果新字符串获得的K个余数与原来的字符串对应的K个余数完全相同，那么就可以说，这两个字符串“很有可能”是同一个字符串。

这个可能性，可以通过需要检查的字符串的总数N、哈希函数的个数K和被除数M这三个数计算出来。

提示：

这个可能性的计算公式为：

其中的e为自然对数的底，它是一个无理数，约等于2.718281828459045。

4．如何压缩数据容量

K个余数如何保存呢？无论是保存在Python的变量，还是在Redis的列表、集合或者哈希表中，占用的内存都非常可观。如何解决空间限制的问题呢？

举一个例子：一个人有两只手，一般情况下是10根手指，所以能够数0～10一共11个数字。那有没有办法用两只手准确数出100甚至1000个数字呢？答案就是使用二进制的方式。一根手指代表一个二进制位，10根手指就是10个二进制位，一共可以表示0～1023一共1024个数字。原本需要103人一起用10根手指才能数出1024个数，现在一个人就能全部数完。这就是数据的压缩。

在Redis的字符串中，一个字符是8个二进制位，8个二进制位可以储存256个数，见表12-1。

表12-1 8位二进制与十进制的对应关系

Redis的字符串的两个字符就是16个二进制位，可以存储65536个数，3个字符就是24个二进制位，可以存储224 个数。

Redis内部限制一个字符串最多存储232 个字符，那么就对应了 （232 的值作为指数）个数。这个数字，比整个宇宙中的所有细菌还多得多得多。而这么多的数，仅仅需要512MB内存。

5．如何把布隆过滤器与Redis结合起来

具体实现比原理简单。使用Redis字符串的位操作，记录K个余数的位置即可。要对Redis的字符串进行位操作，用到的两个命令为“setbit”和“getbit”。使用方法如下：

client.setbit('key', offset, value)

client.getbit('key', offset)

其中，Key就是字符串的Key,offset就是第几位二进制位。value可以为0或1。例如：

01 import redis

02 client = redis.Redis()

03 client.setbit('test', 100, 1)

04 client.setbit('test', 988, 0)

05 client.getbit('test', 100)

其中，主要说明如下。

● 第3行代码：把名为test的字符串对应的二进制位中的第100位设为1。

● 第4行代码：把名为test的字
m.qiduwx.com提示您，本章没有阅读完，点击下一页进入下一页阅读！