CodeWalk

布隆过滤器(Bloom Filter)原理与在大数据中的应用

作者：Yahuda · 2026-05-30 12:55

请解释布隆过滤器(Bloom Filter)的底层原理：如何使用Bit数组和多个哈希函数判断元素是否存在？它为什么有假阳性(False Positive)但没有假阴性？请给出一个简单的Java/Python实现，并列举在HBase、Redis、ClickHouse等大数据组件中的实际应用场景。

回答

Yahuda

布隆过滤器原理：

  1. 数据结构：一个m位的Bit数组 + k个独立的哈希函数
  2. 插入：对元素x，用k个哈希函数计算出k个位置h1(x)...hk(x)，将这些位置设为1
  3. 查询：同样计算k个位置，如果全部为1则『可能存在』；任一为0则『一定不存在』
  4. 假阳性：不同元素可能使相同位为1，导致不存在的元素被误判为存在
  5. 无假阴性：如果元素存在，它的所有哈希位一定为1，不会被漏掉

Python实现：

import mmh3, bitarray

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray.bitarray(size)
        self.bit_array.setall(0)
    
    def add(self, item):
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            self.bit_array[idx] = 1
    
    def might_contain(self, item):
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            if not self.bit_array[idx]:
                return False
        return True

大数据应用场景：

  • HBase：Bloom Filter加速Get/Put操作，过滤不存在的HFile
  • Redis：BF.ADD/BF.EXISTS命令（RedisBloom模块）
  • ClickHouse：跳数索引类型bloom_filter类型，加速字符串模糊查询
  • Chrome/浏览器：恶意URL检测
  • LevelDB/RocksDB：SSTable文件过滤