布隆过滤器

算法

布隆过滤器是一种空间效率高的概率性数据结构,用于判断一个元素是否在集合中。它可能误判元素存在,但不会误判元素不存在。

空间复杂度:O(m)

算法讲解

布隆过滤器教程

介绍

布隆过滤器(Bloom Filter)是一种空间效率很高的概率型数据结构,它用于判断一个元素是否在一个集合中。布隆过滤器的特点是:对于一个元素,如果布隆过滤器说它不存在,那么它一定不存在;如果布隆过滤器说它存在,那么它可能存在(有一定的误判率)。

布隆过滤器的核心组成部分包括:

  • 位数组(Bit Array):一个由二进制位(0或1)组成的数组,初始时所有位都设为0
  • 哈希函数(Hash Functions):多个不同的哈希函数,用于将元素映射到位数组的不同位置
  • 误判率(False Positive Rate):表示不在集合中的元素被误判为在集合中的概率

核心特性

  1. 高效的空间利用率:相比于传统的存储方式,布隆过滤器使用的空间非常小
  2. 常数时间复杂度:判断元素是否存在的操作时间复杂度为O(k),k为哈希函数的个数,通常很小
  3. 可能存在误判:布隆过滤器可能会将不在集合中的元素误判为在集合中(假阳性),但不会将在集合中的元素误判为不在(没有假阴性)
  4. 不可移除元素:标准的布隆过滤器不支持删除元素的操作

基本操作

布隆过滤器支持两种基本操作:

  1. 添加元素(Add):
    • 使用k个哈希函数计算元素的k个哈希值
    • 将位数组中对应的k个位置设为1
  2. 查询元素(Query):
    • 使用k个哈希函数计算元素的k个哈希值
    • 检查位数组中对应的k个位置是否都为1
    • 如果都为1,返回"可能存在";如果有一个不为1,返回"一定不存在"

基础实现

代码实现

Java

▼
Java
复制代码
import java.util.BitSet; import java.util.function.Function; public class BloomFilter<T> { private BitSet bitSet; private int size; private int numberOfHashFunctions; // 哈希函数数组 private Function<T, Integer>[] hashFunctions; @SuppressWarnings("unchecked") public BloomFilter(int size, int numberOfHashFunctions) { this.size = size; this.numberOfHashFunctions = numberOfHashFunctions; this.bitSet = new BitSet(size); this.hashFunctions = new Function[numberOfHashFunctions]; // 创建多个哈希函数(这里用简单方式模拟多个哈希函数) for (int i = 0; i < numberOfHashFunctions; i++) { final int seed = i + 1; hashFunctions[i] = item -> Math.abs((item.hashCode() * seed) % size); } } // 添加元素 public void add(T item) { for (Function<T, Integer> hashFunction : hashFunctions) { int hash = hashFunction.apply(item); bitSet.set(hash); } } // 查询元素 public boolean mightContain(T item) { for (Function<T, Integer> hashFunction : hashFunctions) { int hash = hashFunction.apply(item); if (!bitSet.get(hash)) { return false; // 如果有一个位是0,则元素一定不存在 } } return true; // 所有位都是1,元素可能存在 } // 获取当前设置为1的位的数量 public int getBitCount() { return bitSet.cardinality(); } // 清空过滤器 public void clear() { bitSet.clear(); } // 示例使用 public static void main(String[] args) { // 创建一个大小为1000,使用3个哈希函数的布隆过滤器 BloomFilter<String> filter = new BloomFilter<>(1000, 3); // 添加元素 filter.add("apple"); filter.add("banana"); filter.add("orange"); // 测试元素是否存在 System.out.println("apple 可能存在: " + filter.mightContain("apple")); // 应该返回 true System.out.println("banana 可能存在: " + filter.mightContain("banana")); // 应该返回 true System.out.println("grape 可能存在: " + filter.mightContain("grape")); // 很可能返回 false } }

Python

▼
Python
复制代码
import hashlib import math from bitarray import bitarray # 需要安装: pip install bitarray class BloomFilter: def __init__(self, size, hash_count): """ 初始化布隆过滤器 :param size: 位数组大小 :param hash_count: 哈希函数数量 """ self.size = size self.hash_count = hash_count self.bit_array = bitarray(size) self.bit_array.setall(0) def _hash(self, item, seed): """生成哈希值""" item_str = str(item).encode('utf-8') h = hashlib.md5(item_str) for i in range(seed): h = hashlib.md5((h.hexdigest()).encode('utf-8')) return int(h.hexdigest(), 16) % self.size def add(self, item): """添加元素到布隆过滤器""" for seed in range(self.hash_count): position = self._hash(item, seed) self.bit_array[position] = 1 def might_contain(self, item): """检查元素是否可能在集合中""" for seed in range(self.hash_count): position = self._hash(item, seed) if not self.bit_array[position]: return False return True def clear(self): """清空过滤器""" self.bit_array.setall(0) # 示例使用 if __name__ == "__main__": bloom = BloomFilter(1000, 3) # 添加元素 bloom.add("apple") bloom.add("banana") bloom.add("orange") # 测试元素是否存在 print(f"apple 可能存在: {bloom.might_contain('apple')}") # 应该返回 True print(f"banana 可能存在: {bloom.might_contain('banana')}") # 应该返回 True print(f"grape 可能存在: {bloom.might_contain('grape')}") # 很可能返回 False

JavaScript

▼
Javascript
复制代码
class BloomFilter { constructor(size, hashCount) { this.size = size; this.hashCount = hashCount; this.bitArray = new Uint8Array(Math.ceil(size / 8)); // 使用Uint8Array实现位数组 } // 设置位数组的某一位 _setBit(position) { const byteIndex = Math.floor(position / 8); const bitPosition = position % 8; this.bitArray[byteIndex] |= (1 << bitPosition); } // 获取位数组的某一位 _getBit(position) { const byteIndex = Math.floor(position / 8); const bitPosition = position % 8; return (this.bitArray[byteIndex] & (1 << bitPosition)) !== 0; } // 哈希函数 - 使用简单哈希方法 _hash(item, seed) { let h = 0; const str = String(item); for (let i = 0; i < str.length; i++) { h = Math.imul(31 + seed, h) + str.charCodeAt(i) | 0; } return Math.abs(h % this.size); } // 添加元素 add(item) { for (let i = 0; i < this.hashCount; i++) { const position = this._hash(item, i); this._setBit(position); } } // 查询元素 mightContain(item) { for (let i = 0; i < this.hashCount; i++) { const position = this._hash(item, i); if (!this._getBit(position)) { return false; // 如果有一个位是0,则元素一定不存在 } } return true; // 所有位都是1,元素可能存在 } // 清空过滤器 clear() { this.bitArray.fill(0); } } // 示例使用 const filter = new BloomFilter(1000, 3); // 添加元素 filter.add("apple"); filter.add("banana"); filter.add("orange"); // 测试元素是否存在 console.log(`apple 可能存在: ${filter.mightContain("apple")}`); // 应该返回 true console.log(`banana 可能存在: ${filter.mightContain("banana")}`); // 应该返回 true console.log(`grape 可能存在: ${filter.mightContain("grape")}`); // 很可能返回 false

Go

▼
Go
复制代码
package main import ( "fmt" "hash/fnv" "math" ) // BloomFilter 布隆过滤器结构 type BloomFilter struct { bitArray []bool size int hashCount int } // NewBloomFilter 创建一个新的布隆过滤器 func NewBloomFilter(size, hashCount int) *BloomFilter { return &BloomFilter{ bitArray: make([]bool, size), size: size, hashCount: hashCount, } } // 生成哈希值 func (bf *BloomFilter) hash(item string, seed int) int { h := fnv.New32a() h.Write([]byte(item)) h.Write([]byte{byte(seed)}) return int(h.Sum32()) % bf.size } // Add 添加元素到布隆过滤器 func (bf *BloomFilter) Add(item string) { for i := 0; i < bf.hashCount; i++ { position := bf.hash(item, i) bf.bitArray[position] = true } } // MightContain 检查元素是否可能在集合中 func (bf *BloomFilter) MightContain(item string) bool { for i := 0; i < bf.hashCount; i++ { position := bf.hash(item, i) if !bf.bitArray[position] { return false // 如果有一个位是0,则元素一定不存在 } } return true // 所有位都是1,元素可能存在 } // Clear 清空过滤器 func (bf *BloomFilter) Clear() { bf.bitArray = make([]bool, bf.size) } func main() { // 创建一个大小为1000,使用3个哈希函数的布隆过滤器 filter := NewBloomFilter(1000, 3) // 添加元素 filter.Add("apple") filter.Add("banana") filter.Add("orange") // 测试元素是否存在 fmt.Printf("apple 可能存在: %t\n", filter.MightContain("apple")) // 应该返回 true fmt.Printf("banana 可能存在: %t\n", filter.MightContain("banana")) // 应该返回 true fmt.Printf("grape 可能存在: %t\n", filter.MightContain("grape")) // 很可能返回 false }

C++

▼
C++
复制代码
#include <iostream> #include <vector> #include <string> #include <functional> class BloomFilter { private: std::vector<bool> bitArray; int size; int hashCount; // 简单的哈希函数生成器 size_t hash(const std::string& item, int seed) const { std::hash<std::string> hasher; size_t h = hasher(item); // 混合哈希值和种子 h ^= seed + 0x9e3779b9 + (h << 6) + (h >> 2); return h % size; } public: BloomFilter(int size, int hashCount) : size(size), hashCount(hashCount) { bitArray.resize(size, false); } // 添加元素 void add(const std::string& item) { for (int i = 0; i < hashCount; i++) { size_t position = hash(item, i); bitArray[position] = true; } } // 查询元素 bool mightContain(const std::string& item) const { for (int i = 0; i < hashCount; i++) { size_t position = hash(item, i); if (!bitArray[position]) { return false; // 如果有一个位是0,则元素一定不存在 } } return true; // 所有位都是1,元素可能存在 } // 清空过滤器 void clear() { std::fill(bitArray.begin(), bitArray.end(), false); } }; int main() { // 创建一个大小为1000,使用3个哈希函数的布隆过滤器 BloomFilter filter(1000, 3); // 添加元素 filter.add("apple"); filter.add("banana"); filter.add("orange"); // 测试元素是否存在 std::cout << "apple 可能存在: " << (filter.mightContain("apple") ? "true" : "false") << std::endl; // 应该返回 true std::cout << "banana 可能存在: " << (filter.mightContain("banana") ? "true" : "false") << std::endl; // 应该返回 true std::cout << "grape 可能存在: " << (filter.mightContain("grape") ? "true" : "false") << std::endl; // 很可能返回 false return 0; }

注意,在实际开发中我们一般不会自己实现布隆过滤器,而是使用一些工具包中提供的现成实现,这里上述的实现只是方便大家学习,所以可能并不够完善(比如哈希函数的设计)。

优缺点

优点

  1. 空间效率高:相比于存储元素本身,布隆过滤器只需要很小的空间
  2. 查询速度快:O(k)的时间复杂度,k为哈希函数个数
  3. 隐私保护:不存储元素本身,只存储元素的哈希映射结果
  4. 适合处理大规模数据:当数据量巨大时,布隆过滤器的优势更加明显

缺点

  1. 存在误判:可能会将不在集合中的元素误判为在集合中
  2. 不支持删除:标准布隆过滤器不支持删除元素(有计数布隆过滤器等变种可以支持)
  3. 需要预估数据量:需要在创建时预估元素数量和期望的误判率

应用场景

布隆过滤器在很多领域都有广泛的应用:

  1. 网络爬虫:用于检测URL是否已经被爬取过,避免重复爬取
  2. 数据库优化:在数据库查询前,使用布隆过滤器快速判断记录是否可能存在,减少不必要的磁盘访问
  3. 缓存穿透防护:判断一个key是否在缓存或数据库中存在,防止恶意请求大量不存在的key导致系统压力
  4. 网络安全:判断一个IP地址是否在黑名单中
  5. 推荐系统:快速判断用户是否已经看过某内容,避免重复推荐

以缓存穿透防护为例,当有请求访问一个不存在的数据时,请求会先经过布隆过滤器的检查。如果布隆过滤器判断这个数据"一定不存在",就可以直接返回"不存在"的结果,避免对缓存和数据库的无效查询,提高系统的性能和安全性。

扩展:布隆过滤器的变种

  1. 计数布隆过滤器(Counting Bloom Filter):为每个位置使用一个计数器而不是一个位,支持元素的删除操作
  2. 稳定布隆过滤器(Stable Bloom Filter):随机重置部分计数器以保持误判率的稳定
  3. 可扩展布隆过滤器(Scalable Bloom Filter):可以动态增长以适应更多的元素
  4. 布谷鸟过滤器(Cuckoo Filter):布隆过滤器的一种替代方案,支持删除操作,并且可能具有更低的误判率

测验

  1. 如果布隆过滤器表明一个元素"可能存在",这个元素一定在集合中吗?为什么?
  2. 如果布隆过滤器表明一个元素"一定不存在",这个元素有可能在集合中吗?为什么?
  3. 当向布隆过滤器中添加更多的元素时,假阳性(误判)的概率会如何变化?为什么?
  4. 如果增加布隆过滤器中哈希函数的数量,会对过滤器的性能产生什么影响?
  5. 一个公司需要检查新用户注册的密码是否在常见密码列表中。该列表包含一百万个常见密码。你认为布隆过滤器适合这个场景吗?为什么?

测验答案

  1. 不一定。布隆过滤器可能会有假阳性(误判),即它可能会将不在集合中的元素误判为在集合中。这是由于哈希冲突导致的。
  2. 不可能。如果布隆过滤器说元素"一定不存在",那么这个元素确实不在集合中。布隆过滤器不会出现假阴性。
  3. 添加更多元素会增加假阳性的概率。因为随着添加的元素增多,位数组中被设置为1的位也会增多,导致哈希冲突的可能性增加。
  4. 哈希函数数量k对假阳性率的影响不是单调的:k较小时,增加k会降低假阳性率(因为需要更多的位都为1才会判定元素存在);但k越大,每次插入置为1的位越多,位数组被填满得越快,超过最优值k = (m/n)·ln2(m为位数组大小,n为元素个数)后,假阳性率反而会上升。此外,增加k还会增加计算开销和内存访问次数,需要在准确性和性能之间找到平衡。
  5. 非常适合。理由:密码列表较大(一百万个);只需要判断密码是否可能在列表中,允许少量误判;相比存储完整密码列表,布隆过滤器可以大大节省空间;密码检查需要快速响应;不需要删除操作。

相关的 LeetCode 热门题目

  1. 705. 设计哈希集合 - 虽然这道题目直接要求实现哈希集合,但你也可以使用布隆过滤器的思想来实现一个简化版的哈希集合。
  2. 146. LRU 缓存 - 在实现LRU缓存时,可以使用布隆过滤器来快速判断一个key是否可能存在,减少不必要的查找操作。
  3. 432. 全O(1)的数据结构 - 在设计高效数据结构时,布隆过滤器的思想可以提供参考。
  4. 1032. 字符流 - 这个问题可以使用布隆过滤器来优化解决方案,快速判断是否有可能匹配。