布隆过滤器是一种空间效率高的概率性数据结构,用于判断一个元素是否在集合中。它可能误判元素存在,但不会误判元素不存在。
布隆过滤器(Bloom Filter)是一种空间效率很高的概率型数据结构,它用于判断一个元素是否在一个集合中。布隆过滤器的特点是:对于一个元素,如果布隆过滤器说它不存在,那么它一定不存在;如果布隆过滤器说它存在,那么它可能存在(有一定的误判率)。
布隆过滤器的核心组成部分包括:
布隆过滤器支持两种基本操作:
▼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复制代码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复制代码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复制代码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++复制代码#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的位也会增多,导致哈希冲突的可能性增加。
- 哈希函数数量k对假阳性率的影响不是单调的:k较小时,增加k会降低假阳性率(因为需要更多的位都为1才会判定元素存在);但k越大,每次插入置为1的位越多,位数组被填满得越快,超过最优值k = (m/n)·ln2(m为位数组大小,n为元素个数)后,假阳性率反而会上升。此外,增加k还会增加计算开销和内存访问次数,需要在准确性和性能之间找到平衡。
- 非常适合。理由:密码列表较大(一百万个);只需要判断密码是否可能在列表中,允许少量误判;相比存储完整密码列表,布隆过滤器可以大大节省空间;密码检查需要快速响应;不需要删除操作。