《用 Python 实现布隆过滤器：为什么我们需要多个哈希函数？》

本文介绍了布隆过滤器的原理及其Python实现。布隆过滤器通过位数组和多个哈希函数，以低内存代价提供"可能存在/一定不存在"的判断能力。文章详细讲解了为何需要多个哈希函数（降低误判率），并给出了误判率公式和最优哈希函数数量计算方法。通过爬虫URL去重的实战案例，展示了布隆过滤器的应用场景。最后提出了哈希函数选择、位数组持久化等优化建议，并探讨了布隆过滤器在AI、大数据等领域的应

清水白石008

499人浏览 · 2026-01-13 07:34:16

清水白石008 · 2026-01-13 07:34:16 发布

《用 Python 实现布隆过滤器：为什么我们需要多个哈希函数？》

一、引子：从“是否存在”说起

在处理大规模数据时，我们常常面临一个看似简单却至关重要的问题：

“某个元素是否存在于集合中？”

比如：

广告反作弊系统中，判断某个用户 ID 是否已经点击过广告；
爬虫系统中，判断某个 URL 是否已经抓取过；
数据库缓存中，判断某个 key 是否已经存在于 Redis 中。

如果我们用传统的集合（如 Python 的 set）来存储这些信息，内存消耗将随着数据量线性增长。而布隆过滤器（Bloom Filter）正是为了解决这个问题而生的。

它以极低的内存代价，提供了一个“可能存在 / 一定不存在”的判断机制。虽然存在一定的误判率（False Positive），但在很多场景下，这种权衡是完全可以接受的。

二、布隆过滤器的基本原理

布隆过滤器的核心思想是：

使用一个 位数组（bit array） 来表示集合；
使用 多个哈希函数 将元素映射到位数组的多个位置；
插入元素时，将对应位置的比特位设为 1；
查询元素时，检查所有对应位置是否都为 1。

如果某一位为 0，说明元素一定不存在；如果所有位都为 1，说明元素可能存在（但也可能是其他元素碰巧设置了这些位）。

为什么要使用多个哈希函数？

这是本文的核心问题。简而言之：

多个哈希函数可以降低误判率。

如果只使用一个哈希函数，那么两个不同的元素可能会映射到同一个位置，导致误判率迅速上升。而多个哈希函数可以将一个元素映射到多个位置，只有所有位置都为 1 才认为存在，大大降低了误判的概率。

三、Python 实现布隆过滤器：从零开始

我们先来实现一个简化版的布隆过滤器，逐步理解其结构与哈希函数的作用。

1. 准备工作

import hashlib
import math
import bitarray  # pip install bitarray

我们使用 bitarray 来模拟位数组，效率更高。

2. 哈希函数生成器

我们需要多个哈希函数。一个常见做法是使用不同的哈希种子或算法组合：

def hash_i(value, i):
    data = f"{value}_{i}".encode('utf-8')
    return int(hashlib.md5(data).hexdigest(), 16)

3. 布隆过滤器类

class BloomFilter:
    def __init__(self, capacity, error_rate=0.01):
        self.capacity = capacity
        self.error_rate = error_rate
        self.size = self._get_size(capacity, error_rate)
        self.hash_count = self._get_hash_count(self.size, capacity)
        self.bit_array = bitarray.bitarray(self.size)
        self.bit_array.setall(0)

    def _get_size(self, n, p):
        # n: 预期元素数量，p: 误判率
        m = -(n * math.log(p)) / (math.log(2) ** 2)
        return int(m)

    def _get_hash_count(self, m, n):
        # m: 位数组长度，n: 元素数量
        k = (m / n) * math.log(2)
        return int(k)

    def add(self, item):
        for i in range(self.hash_count):
            index = hash_i(item, i) % self.size
            self.bit_array[index] = 1

    def __contains__(self, item):
        return all(self.bit_array[hash_i(item, i) % self.size] for i in range(self.hash_count))

4. 使用示例

bf = BloomFilter(capacity=10000, error_rate=0.01)

bf.add("apple")
bf.add("banana")

print("apple" in bf)   # True
print("banana" in bf)  # True
print("cherry" in bf)  # False（大概率）

四、多个哈希函数的误判率分析

布隆过滤器的误判率公式如下：

$\left(1 - e^{-kn/m}\right)^k$

其中：

( p )：误判率
( k )：哈希函数个数
( n )：插入元素数量
( m )：位数组长度

我们可以通过图示感受一下不同哈希函数数量对误判率的影响：

哈希函数数量 (k)	误判率 §
1	0.158
3	0.067
5	0.047
7	0.045（最优）
10	0.053

结论：哈希函数数量并非越多越好，存在一个最优值，通常为：

$\frac{m}{n} \ln 2$

五、实战案例：去重爬虫 URL

在爬虫系统中，我们常常需要判断 URL 是否已经抓取过。使用布隆过滤器可以极大减少内存占用。

class Crawler:
    def __init__(self):
        self.visited = BloomFilter(capacity=1000000)

    def crawl(self, url):
        if url in self.visited:
            print(f"跳过重复 URL：{url}")
            return
        print(f"抓取：{url}")
        self.visited.add(url)
        # 模拟抓取逻辑...