0

我最近开始玩布隆过滤器，我有一个用例，这个计算器建议使用 15 个不同且不相关的哈希函数。对一个字符串进行 15 次散列运算会占用大量计算资源，因此我开始寻找更好的解决方案。

很高兴，我遇到了Kirsch-Mitzenmacher 优化，它提出了以下建议：hash_i = hash1 + i * hash2, 0 ≤ i ≤ k - 1，其中 K 是建议的哈希函数的数量。

在我的具体情况下，我正在尝试创建一个 0.5MiB 的布隆过滤器，它最终应该能够有效地存储 200,000 (200k) 条信息。使用 15 个哈希函数，这将导致p = 0.000042214, 或 23,689 (23k) 中的 1。

我尝试在python中实现优化如下：

import uuid
import hashlib
import mmh3

m = 4194304 # 0.5 MiB in bit
k = 15

bit_vector = [0] * m

data = str(uuid.uuid4()).encode()

hash1 = int(hashlib.sha256(data).hexdigest(), base=16)
hash2 = mmh3.hash(data)

for _ in range(0, k-1):
    hash1 += hash2

bit = hash1 % m

bit_vector[bit] = 1

但与创建只有两个哈希值的经典布隆过滤器相比，它的结果似乎要差得多（就误报而言，它的性能要差 10 倍）。

我在这里做错了什么？我是完全误解了优化 - 因此以错误的方式使用公式 - 还是我只是使用了错误的哈希“部分”（这里我在计算中使用了完整的哈希，也许我应该使用前 32 位在一个和另一个的后 32 位上）？或者问题是我在散列之前对数据进行了编码？

我还发现了这个 git 存储库，它讨论了 Bloom Filters 和优化，使用它时的结果在计算时间和误报数量方面都非常好。

*在示例中，我使用 python，因为这是我最熟悉的编程语言来测试，但在我的项目中，我实际上将使用 JavaScript 来执行整个过程。无论如何，非常感谢您选择的任何编程语言的帮助。

4

0 回答 0