布隆过滤器(Bloom Filter)

2019/03/22 Redis

要解决的问题

当集合元素数量非常大时,如何判断一个元素是否存在一个集合中?

常规思路利用普通数据结构(数组、链表、树、哈希表)存储集合,再对每一个需要判断的元素进行比对。

对于元素数量非常大的集合,普通计算机无法提供如此大的内存进行存储。

布隆过滤器介绍

  • 巴顿布隆于1970年提出。
  • 一个很长的二进制位数组。
  • 一系列哈希函数。
  • 空间效率和查询效率很高。
  • 有一定的误判率。

常规思路下,对于超大数据量,哈希表是空间复杂度比较好的数据结构,不需要存储元素值。可以利用哈希函数将一个元素映射到一个位数组中的一个位,如果该位不为1,则集合中肯定不存在该值。(如果该位为1,则集合中不一定存在该值)。

如何进一步降低空间占用率?使用多个哈希函数

一个Bloom Filter是基于一个m位的位向量(b1,…bm),这些位向量的初始值为0。另外,还有一系列的hash函数(h1,…hk),这些hash函数的值域属于1~m。

对每个要查询的元素,都经过k个哈希函数映射到位向量,如果==有一个位置不为1,则该元素一定不在集合中。如果每个位置都为1,则该元素可能在集合中。==

举例

下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图:

image

上图中,m=18,k=3;插入x是,三个hash函数分别得到蓝线对应的三个值,并将对应的位向量改为1,插入y,z时,类似的,分别将红线,紫线对应的位向量改为1。查找时,当查找x时,三个hash值对应的位向量都为1,因此判断x在此数据集中。y,z也是如此。但是查找w时,w有个hash值对应的位向量为0,因此可以判断不在此集合中。但是,假如w的最后那个hash值比上图中的大1,这是就会认为w在此集合中,而事实上,w可能不在此集合中,因此可能出现误报。显然的,插入数据越多,1的位数越多,误报的概率越大。

删除

如果使用位数组,则只支持add和isExist操作。

要支持删除可以将位数组改为计数值,增加一个值就是对应索引槽的值加一,删除就是减一。但是删除前必须确保被删除的元素之前被加入过。

特点

因为布隆过滤器能够用较少的内存占用==过滤出绝对不存在的值==,适用于过滤查询中不存在的值,减少磁盘IO或网络请求。

本文地址:https://cheng-dp.github.io/2019/03/22/bloom-filter/

Search

    Table of Contents