布隆过滤器(Bloom Filter,简写为BF)

Source: Jiuzhang's Tutorial: https://www.jiuzhang.com/tutorial/big-data-interview-questions/238

BF是一个更省空间的哈希表。在海量数据处理类问题中,我们经常需要用到哈希表,也经常会碰到内存不够的问题。那么 BF 就是一个很好的选择。

Bloom Filter一般有两个作用

  1. 检测一个元素在不在一个集合中
  2. 统计一个元素的出现次数

BF能做的事情确实就是哈希表能做的事情,但是BF 相比哈希表,耗费更少的存储空间。既然节省了空间,同样也有一个副作用:存在 False Positive

什么是False Positive? 简单的说就是,如果是 Hash 的话,他说这个元素在集合里,那就是在集合里。

但BF不会有False Negative。BF 说这个元素不在集合里,那就一定不在集合里。

根据要处理的问题的不同,BF(BloomFilter的专业简称)可以分为:

  1. 标准型布隆过滤器(Standard Bloom Filter,简写为 SBF,对应到 Java 里的 HashSet)
  2. 计数型布隆过滤器(Counting Bloom Filter,简写为 CBF,对应到 Java 里的 HashMap)
k个独立的哈希函数

可以使用几个不同的算法,来获得不同的哈希函数。一个比较通用的哈希函数的写法是这样:

def hashfunc(string, hashsize):
    code = 0
    for c in string:
        code = code * 31 + ord(c)
        code = code % hashsize

    return code

在 LintCode 上练习这个知识点:
http://www.lintcode.com/problem/hash-function/

如果需要设计 k 个独立的哈希函数,只需要简单的修改上面的函数中的 Magic Number31即可,比如换成 37,41 这样。

Magic Number 31 是什么?

上面的这个算法,相当于把一个字符串当做了 31 进制,然后转换为整数。一遍转换的过程中一遍对 hashsize 取模,避免溢出。

这个 31 并不是唯一的选择,但是有一些基本的法则我们需要遵循:

  1. 不能太小。太小的话,容易出现 hashfunc 算出来的值在字符串比较短的时候出现扎堆的情况。增加了哈希碰撞的几率。
  2. 不能太大。太大的话,影响了计算效率。
  3. 尽量不要是合数。合数也可能会增加哈希碰撞的几率。

标准布隆过滤器 Standard Bloom Filter

标准布隆过滤器的作用相当于一个 HashSet,即提供了这样一个数据结构,他支持如下操作:

  1. 在集合中加入一个元素
  2. 判断一个元素是否在集合中(允许 False Positive)

实现步骤

  1. 初始化:开一个足够大的 boolean 数组,初始值都是 false。
  2. 插入一个元素:通过k个哈希函数,计算出元素的k个哈希值,对 boolean 数组的长度取模之后,标记对应的k个位置上的值为 true。
  3. 查询一个元素:通过同样的k个哈希函数,在 boolean 数组中取出对应的k个位置上的值。如果都是 true,则表示该元素可能存在,如果有一个 false,则表示一定不存在

伪代码 Pseudo Code

class StandardBloomFilter:

    def __init__(self, capacity, hash_functions):
        # capacity is the initial size of the SBF
        # it should be as big as possible to contains all
        # of the keys
        self.capacity = capacity
        self.bitset = [False] * capacity 

        # k hash functions
        self.hash_functions = hash_functions

    def add(self, key):
        for func in self.hash_functions:
            position = func(key) % self.capacity
            self.bitset[position] = True

    def contains(self, key):
        for func in self.hash_functions:
            position = func(key) % self.capacity
            if self.bitset[position] is False:
                return False

        return True

http://www.lintcode.com/problem/standard-bloom-filter/

空间优化

具体实现的时候,为了更好的节省空间,可以用位运算的方式来取代 boolean 数组。Java 中可以直接用 BitSet 这个结构。

Q: 如果空间不够了怎么办呢?一开始开的 boolean 数组不够的话,如果全部都被赋为 true 了,contains 不就每次都返回 true 了么?

A: 实际运用中,我们通常需要进行预估,也就是估算一下大概需要用到多少的空间,开多大比较合适。另外一个解决办法,是采用 Extended Bloom Filter。具体的解决方案是,当一个 BloomFilter 满了的时候,开一个新的,capacity 更大的(两倍) BloomFilter。原来的 Bloom Filter 依旧保留,这样插入的时候,总是插入到新的 BloomFilter 里,而查询的时候,所有的 BloomFilter 都要查一遍。

Q: 如何定义一个 BloomFilter 是不是满了?

A: 如果哈希函数用4个的话,boolean 数组的大小和实际能够存储的元素个数之间的比例,在 40: 1 比较合适。这是一个经验值。


计数布隆过滤器 Counting Bloom Filter

基于标准的 BloomFilter 稍加改动,把存储所用的 boolean 数组改为 int 数组,就成为了可以计数的 BloomFilter -> Counting Bloom Filter(简写为CBF)。这种数据结构类似 Java 中的 HashMap,但只能用作计数。提供如下的几种操作:

  1. O(1)时间内,在集合中加入一个元素
  2. O(1)时间内,统计某个元素在该集合中出现的次数 - 但是可能会比实际出现次数要大一些

实现步骤

  1. 初始化:开一个足够大的 int 数组,初始值都是 0。
  2. 插入一个元素:通过k个哈希函数,计算出元素的k个哈希值,对 int 数组的长度取模之后,将对应的k个位置上的值都加一
  3. 查询一个元素的出现次数:通过同样的k哈希函数,在 int 数组中取出对应的k个位置上的值。并取其中的最小值来作为该元素的出现次数预估。

伪代码

class CountingBloomFilter:

    def __init__(self, capacity, hash_functions):
        # capacity is the initial size of the SBF
        # it should be as big as possible to contains all
        # of the keys
        self.capacity = capacity
        self.bitset = [0] * capacity 

        # k hash functions
        self.hash_functions = hash_functions

    def add(self, key):
        for func in self.hash_functions:
            position = func(key) % self.capacity
            self.bitset[position] += 1

    def contains(self, key):
        count = sys.maxint
        for func in self.hash_functions:
            position = func(key) % self.capacity
            count = min(count, self.bitset[position])

        return count

LintCode 练习地址

http://www.lintcode.com/problem/counting-bloom-filter/

Q & A

Q: 为什么要取最小值?
A: 比如我们使用两个哈希函数,key1 算出来的两个下标是 0, 1, key2 算出来的 两个下标是 1, 2。这里 counts[1] 会等于 2,他被 2个 key 都影响到了。所以取最小值,能够让这个计数尽可能的毕竟真实计数。

Q: 为什么说是预估的出现次数?而不是精确的出现次数?
A: 承接上面问题的解答,如果还有一个 key3 算出来的下标是 0 和 2。那么 counts[0~2] 都会是 2,无论对 key1~3 的任何一个 key 取计数,都得到的是 2,要比实际的出现次数大。

Q: CBF算出来的计数,有可能比实际出现次数小么?
A: 不可能

results matching ""

    No results matching ""