初识布隆过滤器(Bloom Filiter)

一个网站有 100 亿 url 存在一个黑名单中,每条 url 平均 64 字节。这个黑名单要怎么存?若此时随便输入一个 url,你如何快速判断该 url 是否在这个黑名单中?

问题解析

这是一道经常在面试中出现的算法题。凭借着题目极其容易描述,电面的时候也出现过。

不考虑细节的话,此题就是一个简单的查找问题。对于查找问题而言,使用散列表来处理往往是一种效率比较高的方案。

但是,如果你在面试中回答使用散列表,接下来面试官肯定会问你:然后呢?如果你不能回答个所以然,面试官就会面无表情的通知你:今天的面试到此结束,我们会在一周内给你答复,然后你就gg了。

为什么不能用散列表

100 亿是一个很大的数量级,这里每条 url 平均 64 字节,全部存储的话需要 640G 的内存空间。又因为使用了散列表这种数据结构,而散列表是会出现散列冲突的。为了让散列表维持较小的装载因子,避免出现过多的散列冲突,需要使用链表法来处理,这里就要存储链表指针。因此最后的内存空间可能超过 1000G 了。在实际生产环境中,用1000G来存储 url 显然不太现实。

位图(BitMap)

这个时候就需要拓展一下思路。首先,先来考虑一个类似但更简单的问题:现在有一个非常庞大的数据,比如有 1 千万个整数,并且整数的范围在 1 到 1 亿之间。那么如何快速查找某个整数是否在这 1 千万个整数中呢?

需要判断该数是否存在,也就是说这个数存在两种状态:存在( True )或者不存在(False)。

因此这里可以使用一个存储了状态的数组来处理。这个数组特点是大小为 1 亿,并且数据类型为布尔类型( True 或者 False )。然后将这 1 千万个整数作为数组下标,将对应的数组值设置成 True,比如,整数 233 对应下标为 233 的数组值设置为 True,也就是 array [233] = True。

这种操作就是位图法:就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。

另外,位图法有一个优势就是空间不随集合内元素个数的增加而增加。它的存储空间计算方式是找到所有元素里面最大的元素(假设为 N ),因此所占空间为:

$$S = \frac{N}{8}Byte$$

因此,当 N 为 1 亿的时候需要 12MB 的存储空间。当 N 为 10 亿的时候需要 120MB 的存储空间了。也就是说:位图法的所占空间随集合内最大元素的增大而增大。这就会带来一个问题,如果查找的元素数量少但其中某个元素的值很大,比如数字范围是 1 到 1000 亿,那消耗的空间不容乐观。

因此,出于性能和内存占用的考虑,在这里使用布隆过滤器才是最好的解决方案:布隆过滤器是对位图的一种改进。

布隆过滤器(Bloom Filter)

简介*

看不太懂的建议看完后再返回看本部分

布隆过滤器(Bloom Filter)是 1970 年由 Burton Bloom 提出的。

布隆过滤器本质上是一个固定长度的位向量,一个位数组。

布隆过滤器是一种节省空间的数据结构,可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。

对于布隆过滤器而言,它的本质是一个固定长度的位向量位数组

位数组就是数组的每个元素都只占用 1 bit ,并且每个元素只能是 0 或者 1。

布隆过滤器除了一个位数组,还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候,会进行如下操作:

  • 使用 K 个哈希函数对元素值进行 K 次计算,得到 K 个哈希值。
  • 根据得到的哈希值,在位数组中把对应下标的值置为 1。

举个例子,假设布隆过滤器有 3 个哈希函数:f1, f2, f3 和一个位数组 arr。现在要把 2333 插入布隆过滤器中:

  • 对值进行三次哈希计算,得到三个值 n1, n2, n3。
  • 把位数组中三个元素 arr [n1], arr [n2], arr [3] 都置为 1。

当要判断一个值是否在布隆过滤器中,对元素进行三次哈希计算,得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,说明该元素不在布隆过滤器中。

169a878fc1c67913.gif

很明显,数组的容量即使再大,也是有限的。那么随着元素的增加,插入的元素就会越多,位数组中被置为 1 的位置因此也越多,这就会造成一种情况:当一个不在布隆过滤器中的元素,经过同样规则的哈希计算之后,得到的值在位数组中查询,有可能这些位置因为之前其它元素的操作先被置为 1 了

所以,有可能一个不存在布隆过滤器中的会被误判成在布隆过滤器中。这就是布隆过滤器的一个缺陷。但是,如果布隆过滤器判断某个元素不在布隆过滤器中,那么这个值就一定不在布隆过滤器中。总结就是:

  • 布隆过滤器说某个元素在,可能会被误判
  • 布隆过滤器说某个元素不在,那么一定不在

注意: 与哈希表不同,布隆过滤器不存储实际对象。 它只会记住你看过的物体(有一定程度的不确定性)以及你没有看过的物体。

将对象插入集合中

布隆过滤器本质上是一个固定长度的位向量,一个位数组。 当我们插入对象时,我们将其中一些位设置为 1,当我们查询对象时,我们检查某些位是 0 还是 1。 两个操作都使用哈希函数。要在过滤器中插入元素,可以使用多个不同的哈希函数对元素进行哈希。 每个哈希函数返回一个我们映射到数组中索引的值。 然后,我们将这些索引处的位设置为 1

例如,假设这是我们的位数组。 我们有 17 位,最初它们都是 0

1
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

现在我们要在布隆过滤器中插入字符串 "Hello world!"。 我们对此字符串应用两个自定义哈希函数。第一个给出值 1999532104120917762。我们通过取数组长度的模数将此哈希值映射到数组的索引:1999532104120917762 % 17 = 4。 这意味着我们将索引 4 处的位设置为 1

1
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

然后我们再次散列原始字符串,但这次使用不同的散列函数。 它给出哈希值 9211818684948223801。模数 17 为 12,我们也将索引 12 处的位设置为 1

1
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ]

这两个 1 位足以告诉布隆过滤器它现在包含字符串 "Hello world!"。 当然,它不包含实际的字符串,所以你不能要求布隆过滤器,“给我一个你包含的所有对象的列表”。 所有它都是一堆零和零。

查询集合

类似于插入,查询是通过首先对期望值进行哈希来实现的,该期望值给出几个数组索引,然后检查这些索引处的所有位是否为 1。 如果其中一个位不是 1,则无法插入该元素,并且查询返回 false。 如果所有位都是 1,则查询返回 true

例如,如果我们查询字符串 "Hello WORLD",那么第一个哈希函数返回 5383892684077141175,其中模 17 是 12. 该位是 1。但是第二个哈希函数给出 5625257205398334446,它映射到数组索引 9. 该位为 0。 这意味着字符串 "Hello WORLD" 不在过滤器中,查询返回 false

第一个哈希函数映射到 1 位的事实是巧合(它与两个字符串以 "Hello " 开头的事实无关)。 太多这样的巧合可能导致 “碰撞”。 如果存在冲突,即使未插入元素,查询也可能错误地返回 true

假设我们插入了一些其他元素,"Bloom Filterz",它设置了第 7 位和第 9 位。现在数组看起来像这样:

1
[ 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0 ]

如果再次查询 "Hello WORLD",则过滤器会看到第 12 位为真,第 9 位现在也为真。 它报告说 "Hello WORLD" 确实出现在集合中,即使它不是…… 因为我们从未插入过那个特定的字符串。这是误报。这个例子说明了为什么布隆过滤器永远不会说 “绝对是”,只有“可能是”

您可以通过使用具有更多位的数组并使用其他哈希函数来解决此类问题。 当然,使用的哈希函数越多,布隆过滤器就越慢。 所以你必须取得平衡。

使用布隆过滤器无法删除,因为任何一个位都可能属于多个元素。 一旦你添加了一个元素,它就在那里。

布隆过滤器的性能是 O (k) 其中 k 是哈希函数的数量。

代码

代码非常简单。 内部位数组在初始化时设置为固定长度,初始化后不能进行突变。

1
2
3
4
public init(size: Int = 1024, hashFunctions: [(T) -> Int]) {
self.array = [Bool](repeating: false, count: size)
self.hashFunctions = hashFunctions
}

应在初始化时指定几个哈希函数。 你使用哪些哈希函数将取决于您将添加到集合的元素的数据类型。 你可以在测试中看到一些例子 ———字符串的 djb2sdbm 哈希函数。

insert只是将所需的位翻转为 true

1
2
3
4
5
public func insert(_ element: T) {
for hashValue in computeHashes(element) {
array[hashValue] = true
}
}

这使用 computeHashes() 函数,它循环遍历指定的 hashFunctions 并返回索引数组:

1
2
3
private func computeHashes(_ value: T) -> [Int] {
return hashFunctions.map() { hashFunc in abs(hashFunc(value) % array.count) }
}

并查询检查以确保哈希值处的位为 true

1
2
3
4
5
6
public func query(_ value: T) -> Bool {
let hashValues = computeHashes(value)
let results = hashValues.map() { hashValue in array[hashValue] }
let exists = results.reduce(true, { $0 && $1 })
return exists
}

如果你来自另一种命令式语言,你可能会注意到 exists 赋值中的不寻常语法。 当 Swift 使代码更加简洁和可读时,Swift 使用函数范例,在这种情况下,reduce 是一种更加简洁的方法来检查所有必需的位是否为 true 而不是 for 循环。

另一种方法

通过上面的例子,您了解了如何使用多个不同的哈希函数来帮助减少布隆过滤器中发生冲突的可能性。但是,良好的散列函数是很难设计的。多个散列函数的简单替代方法是使用一组随机数。

举个例子,假设一个布隆过滤器想要在插入过程中对每个元素进行 15 次哈希处理。您可以只使用一个哈希函数,而不是使用 15 种不同的哈希函数。然后可以将散列值与 15 个不同的值组合以形成用于翻转的索引。此布隆过滤器将提前初始化一组 15 个随机数,并在每次插入期间使用这些值。

1
2
hash("Hello world!") >> hash(987654321) // would flip bit 8
hash("Hello world!") >> hash(123456789) // would flip bit 2

自 Swift 4.2 以来,Hasher现在包含在标准库中,该库旨在以有效的方式将多个哈希值减少到单个哈希值。这使得哈希的组合变得微不足道。

1
2
3
4
5
6
7
8
9
private func computeHashes(_ value: T) -> [Int] {
return randomSeeds.map() { seed in
let hasher = Hasher()
hasher.combine(seed)
hasher.combine(value)
let hashValue = hasher.finalize()
return abs(hashValue % array.count)
}
}

如果您想了解有关此方法的更多信息,可以阅读Hasher 文档或 Soroush Khanlou 的Swift 4.2 Bloom 过滤器实现。

BloomFilter.swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class BloomFilter<T> {
fileprivate var array: [Bool]
private var hashFunctions: [(T) -> Int]
public init(size: Int = 1024, hashFunctions: [(T) -> Int]) {
self.array = [Bool](repeating: false, count: size)
self.hashFunctions = hashFunctions
}
private func computeHashes(_ value: T) -> [Int] {
return hashFunctions.map { hashFunc in abs(hashFunc(value) % array.count) }
}
public func insert(_ element: T) {
for hashValue in computeHashes(element) {
array[hashValue] = true
}
}
public func insert(_ values: [T]) {
for value in values {
insert(value)
}
}
public func query(_ value: T) -> Bool {
let hashValues = computeHashes(value)
let results = hashValues.map { hashValue in array[hashValue] }
let exists = results.reduce(true, { $0 && $1 })
return exists
}
public func isEmpty() -> Bool {
return array.reduce(true, { prev, next in prev && !next} )
}
}
func djb2(x: String) -> Int {
var hash = 5381
for char in x {
hash = ((hash << 5) &+ hash) &+ char.hashValue
}
return Int(hash)
}
func sdbm(x: String) -> Int {
var hash = 0
for char in x {
hash = char.hashValue &+ (hash << 6) &+ (hash << 16) &- hash
}
return Int(hash)
}

使用场景

布隆过滤器的最大的用处就是,能够迅速判断一个元素是否在一个集合中。因此它有如下三个使用场景:

  • 网页爬虫对 URL 的去重,避免爬取相同的 URL 地址
  • 进行垃圾邮件过滤:反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(同理,垃圾短信)
  • 有的黑客为了让服务宕机,他们会构建大量不存在于缓存中的 key 向服务器发起请求,在数据量足够大的情况下,频繁的数据库查询可能导致 DB 挂掉。布隆过滤器很好的解决了缓存击穿的问题。

引用

拜托,面试官别问我「布隆」了

swift-algorithm-club/Bloom Filter

Title: 初识布隆过滤器(Bloom Filiter)

Author: Tuski

Published: 03/23/2019 - 18:31:19

Updated: 03/23/2019 - 22:37:16

Link: http://www.perphet.com/2019/03/初识布隆过滤器-Bloom-Filiter/

Protocol: Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Reprinted please keep the original link and author

Thx F Sup