布隆过滤器与 Swift 4.2

作者：Soroush Khanlou， 原文链接 ，原文日期：2018-09-19

译者： WAMaker ；校对： numbbbbb ， 小铁匠Linus ；定稿： Forelax

Swift 4.2 为哈希的实现带来了一些新的变化。在此之前，哈希交由对象本身全权代理。当你向对象索取 哈希值（hashValue） 时，它会把处理好的整型值作为哈希值返回。而现在，实现了 Hashable 协议的对象则描述了它的参数是如何组合，并传递给作为入参的 Hasher 对象。这样做有以下几点好处：

• 写出好的哈希算法很难。Swift 的使用者不需要知道如何组合参数来获得更好的哈希值。
• 出于不提倡用户以任何形式存储哈希值，以及 一些安全方面因素 的考虑，哈希值在程序每次运行的时候都应该有所不同。描述性的哈希允许哈希函数的种子在每次程序运行的时候发生改变。
• 能实现更多有意思的数据结构，这也是我们这篇文章接下来会聚焦的。

我之前写过一篇关于 如何使用 Swift 的 Hashable 协议从零实现 Dictionary 的文章（先阅读它会帮助你阅读本文，但这不是必须的）。今天，我想谈论一种不同类型的，基于概率性而非明确性的数据结构：布隆过滤器（Bloom Filters）。我们会使用 Swift 4.2 的新特性，包括新的哈希模型来构建它。

布隆过滤器很怪异。想象这样一种数据结构：

• 你能够往里插入数据
• 你能够查询一个值是否存在
• 只需要少量存储资源就能存储大量对象

但是：

• 你不能枚举其中的对象
• 它有时会出现误报（但不会出现漏报）
• 你不能从中移除数据

什么时候会想要这种数据结构呢？Medium 使用它们来 跟踪博文的阅读状态 。必应使用它们做 搜索索引 。你可以使用它们来构建一个缓存，在无需访问数据库的情况下就能判断用户名是否有效（例如在 @-mention 中）。像服务器这样可能拥有巨大的规模，却不一定有巨大资源的场景中，它们会非常有用。

（如果你之前做过图形方面的工作，可能好奇它是如何与 高光过滤器 ) 产生联系的。答案是没有联系。高光过滤器（bloom filters）是小写的 b，而布隆过滤器（Bloom Filters）是由一个叫布隆的人命名的。完全是个巧合。）

那它们是如何运作的呢？

将对象放入布隆过滤器如同将它放入集合或字典：计算对象的哈希值，并根据存储数组的大小对哈希值求余。就这点而言，使用布隆过滤器只需要修改该索引处的值：将 false 改为 true，而不用像使用集合或字典那样，把对象存放到索引位置。

我们先通过一个简单的例子来理解过滤器是如果运作的，之后再对它进行扩展。想象一个拥有 8 个 false 值的布尔数组（或称之为 比特数组 ）：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   |   |   |   |   |

它代表了我们的布隆过滤器。我想要插入字符串“soroush”。它的哈希值是 9192644045266971309，当这个值余 8 时得到 5。我们修改那一位的值。

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   |   | * |   |   |

接下来我想要插入字符串“swift”，它的哈希值是 7052914221234348788，余 8 得 4，修改索引 4 的值。

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   | * | * |   |   |

要测试布隆过滤器是否包含“soroush”，我再次计算它的哈希值并求余，仍旧得到余数 5，对应值是 true。“soroush”确实在布隆过滤器中。

然而仅仅测试能够通过的用例是不够的，我们需要写一些会导致失败的用例。测试字符串“khanlou”取余得到的索引值是 2，因此我们知道它不在布隆过滤器中。到此为止一切都好。接下去一个测试：对“hashable”字符串取余得到的索引值是 5，这就发生了一次冲突！即使这个值从来没有被加入过，过滤器仍返回了 true。这便是布隆过滤器会发生误报的例子。

有两个主要的策略可以尽可能减少误报。第一个策略，也是两个策略中相对有趣的：我们可以使用不同的哈希函数计算两次或三次哈希值而非一次。只要它们都是表现良好的哈希函数（均匀分布，一致性，最小的碰撞几率），我们就能为每个值生成多个索引改变布尔值。这次，我们计算两次“soroush”的哈希值，生成 2 个索引并改变布尔值。这时，当我们检查“khanlou”是否在布隆过滤器中，其中一个哈希值可能会和“soroush”的一个哈希值冲突，但两个值同时发生冲突的可能性就会变得很小。你可以把这个数字扩大。在下面的代码我会做 3 次哈希计算，但你可以做更多次。

当然，如果你计算更多次哈希值，每个元素在布尔数组中会占据更多的空间。事实上，现在的数据几乎不占用空间。8 个布尔值的数组对应 1 字节。所以第二个减小误报的策略是扩大数组的规模。我们能将数组变得足够大而不用担心它的空间消耗。下面的代码中我们会默认使用 512 比特大小的数组。

现在，即使同时使用这些策略，你依然会得到冲突，即误报，但冲突的几率会减小。这是布隆过滤器的一个缺陷，但在合适的场景用它来节省速度与空间是一笔不错的交易。

在开始具体的代码之前我有另外三点想要谈谈。首先，你不能改变布隆过滤器的大小。当你对哈希值取余时，这是在破坏信息，在不保留原始哈希值的情况下你不能回溯之前的信息 —— 保留原始值相当于否决了这个数据结构节约空间的优势。

其次，你能看到想要枚举布隆过滤器所有的值是多么异想天开。你不再拥有这些值，只是它们以哈希形式存在的替代品。

最后，你同样能看到想要从布隆过滤器中移除元素是不可能的。如果想将布尔值变回 false，你并不知道是哪些值将它变为 true。是准备移除的值还是其它值？这样做会造成漏报和误报。（这对你来说可能是值得权衡的）你可以在每个索引上保留计数而非布尔值来解决这个问题，虽然保留计数还是会带来存储问题，但根据使用场景的不同，这样做或许是值得的。

废话不多说，让我们开始着手编码。我在这里做的一些决策和你可能会做的有所不同，第一个不同就是要不要让对象支持范型。我认为让对象包含更多关于它需要存储内容的元数据是有意义的，但如果你发现这样做限制太多，你可以改变它。

struct BloomFilter<Element: Hashable> {
	// ...
}

我们需要存储两种主要的数据。第一个是 data ，用于表示比特数组。它存储了所有和哈希值有关的标记：

private var data: [Bool]

接下来，我们需要不同的哈希函数。一些布隆过滤器确实会使用不同的方法计算哈希值，但我觉得使用相同的算法，同时混入一个随机生成的值会更简单。

private let seeds: [Int]

当初始化布隆过滤器时，我们需要初始化这两个实例变量。比特数组会简单的重复 false 值来初始化，而种子值则使用 Swift 4.2 的新 API Int.random 来生成我们需要的种子值。

init(size: Int, hashCount: Int) {
	data = Array(repeating: false, count: size)
	seeds = (0..<hashCount).map({ _ in Int.random(in: 0..<Int.max) })
}

同时，创建一个带有默认值的便利构造器。

init() {
	self.init(size: 512, hashCount: 3)
}

我们要实现两个主要的方法： insert 和 contains 。它们都需要接收元素作为参数并为每一个种子值计算出对应的哈希值。私有的帮助方法会很有用。由于种子值代表了“不同的”哈希函数，我们就需要为每一个种子生成对应的哈希值。

private func hashes(for element: Element) -> [Int] {
	return seeds.map({ seed -> Int in
		// ...
	})
}

要实现函数主体，我们需要创建一个 Hasher 对象（Swift 4.2 新特性），将想要进行哈希计算的对象传给它。带上种子确保了生成的哈希值不会冲突。

private func hashes(for element: Element) -> [Int] {
	return seeds.map({ seed -> Int in
		var hasher = Hasher()
		hasher.combine(element)
		hasher.combine(seed)
		let hashValue = abs(hasher.finalize())
		return hashValue
	})
}

同时，注意哈希值的绝对值。哈希计算有可能产生负数，这会导致我们的数组访问崩溃。取绝对值操作减少了 1 比特的信息熵，对我们来说是有益的。

理想的情况是你能够使用种子来初始化 Hasher 而不是把它混合进去。Swift 的 Hasher 会在每次程序启动的时候被分配一个不同的种子（除非你 设置固定的环境变量 让种子在不同启动间保持一致，而这样做通常是一些测试目的），意味着你不能把这些值写到磁盘上。如果我们控制了 Hasher 的种子，我们就能将这些值写到磁盘上了。而就像这个布隆过滤器展示的那样，它应该只被用于内存缓存。

hashes(for:) 方法完成了很多繁重的工作，让 insert 方法非常简洁：

mutating func insert(_ element: Element) {
	hashes(for: element)
		.forEach({ hash in
			data[hash % data.count] = true
		})
}

生成所有的哈希值，分别余上 data 数组的长度，并设置对应索引位的值为 true 。

contains 方法也同样简单，同时也给了我们使用 Swift 4.2 另一个新特性 allSatisfy 的机会。这个新方法可以判断序列中的所有对象是否都通过了某项用 block 表示的测试：

func contains(_ element: Element) -> Bool {
	return hashes(for: element)
		.allSatisfy({ hash in
			data[hash % data.count]
		})
}

因为 data[hash % data.count] 的结果已经是布尔值了，它与 allSatisfy 十分契合。

你也可以添加 isEmpty 方法用来检测 data 中的所有值是否都是 false。

布隆过滤器是一种奇怪的数据结构。我们接触的大多数数据结构都是明确性的。当把一个对象放入字典中时，你知道那个值之后一直在那儿。而布隆过滤器是概率性的，牺牲确定性来换取空间和速度。布隆过滤器不是你会每天用的数据结构，但当你确实需要它时，就会感受到有它真好。

本文由 SwiftGG 翻译组翻译，已经获得作者翻译授权，最新文章请访问http://swift.gg。