什么是布隆过滤器

大耗子 2021年02月16日 17次浏览

1. 什么是布隆过滤器

本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。

2. 实现原理

实现的结构是bitmap结构,通过对数据进行多次hash得到的结果,对其对应的bitmap位置置为1。

例如数据A三次hash的结果为1,5,7。那么会在bitmap的1,5,7三个位置置为1。如果数据B的三次hash结果是1,5,8。有前两个一样,但是最后一个8不一样,那么可以判断为不一致。

而布隆过滤器就是通过对数据进行hash,判断hash结果位置是否置1为依据进行判断。如果没有匹配中,那么必定不在过滤数据中,反之则有可能存在过滤数据中。 但要注意,只是可能!!!! 因为如果数据过于庞大,bitmap结构较小,会出现大量的重叠位置,导致误判。

例如:

过滤数据有:
数据A:1,5,7。
数据B:2,5,8。
数据C:3,5,13。
数据D:0,6,9。

此时有数据E,hash结果为:3,6,7

过滤的数据中没有数据E,但是hash得到的bitmap位置出现了重叠。造成了误判。但是存在的数据一定命中,不存在的数据有概率误判。

解决办法:扩大布隆过滤器的长度。