当前位置：首页 > news >正文

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

news 2026/3/27 5:53:38

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

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

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

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

比如：

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

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

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

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

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

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

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

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

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

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

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

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

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

1. 准备工作

importhashlibimportmathimportbitarray# pip install bitarray

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

2. 哈希函数生成器

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

defhash_i(value,i):data=f"{value}_{i}".encode('utf-8')returnint(hashlib.md5(data).hexdigest(),16)

3. 布隆过滤器类

classBloomFilter: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)returnint(m)def_get_hash_count(self,m,n):# m: 位数组长度，n: 元素数量k=(m/n)*math.log(2)returnint(k)defadd(self,item):foriinrange(self.hash_count):index=hash_i(item,i)%self.size self.bit_array[index]=1def__contains__(self,item):returnall(self.bit_array[hash_i(item,i)%self.size]foriinrange(self.hash_count))

4. 使用示例

bf=BloomFilter(capacity=10000,error_rate=0.01)bf.add("apple")bf.add("banana")print("apple"inbf)# Trueprint("banana"inbf)# Trueprint("cherry"inbf)# False（大概率）

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

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

p = ( 1 − e − k n / m ) k p = \left(1 - e^{-kn/m}\right)^kp=(1−e−kn/m)k

其中：

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

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

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

结论：哈希函数数量并非越多越好，存在一个最优值，通常为：
k = m n ln ⁡ 2 k = \frac{m}{n} \ln 2k=nmln2

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

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

classCrawler:def__init__(self):self.visited=BloomFilter(capacity=1000000)defcrawl(self,url):ifurlinself.visited:print(f"跳过重复 URL：{url}")returnprint(f"抓取：{url}")self.visited.add(url)# 模拟抓取逻辑...