python & redis 布隆过滤器

0 背景

什么是布隆过滤器

布隆过滤器（Bloom Filter）是一种空间效率高、用于快速判断一个元素是否属于一个集合的数据结构。它可以用于解决在大规模数据集中判断某个元素是否存在的问题，具有快速查询和低内存占用的特点。

实现原理

布隆过滤器的主要思想是使用多个哈希函数将元素映射到一个位数组中的多个位置，并将这些位置标记为1。当查询一个元素时，通过相同的哈希函数将查询元素映射到位数组上的相同位置，如果所有对应的位置都是1，则可能存在于集合中，如果有任何一个位置是0，则可以确定元素不存在于集合中。

应用场景

布隆过滤器在一些应用场景中非常有用，例如爬虫抓取中的URL去重、缓存系统中的数据过滤等。由于其高效的空间利用和快速查询的特性，它在处理大规模数据集时可以起到很好的加速作用。

1 使用

python自实现一个布隆过滤器

首先为了了解其原理, 我们使用python创建一个布隆过滤器, 在此, 我们分别选择md5和mmh3(一个非加密哈希函数库)作为哈希函数.

pip install mmh3

import mmh3


class MyFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bytearray(hash_count)

    def add(self, string):
        for seed in range(self.hash_count):
            result = mmh3.hash(string, seed) % self.size
            self.bit_array[result] = 1

    def lookup(self, string):
        for seed in range(self.hash_count):
            result = mmh3.hash(string, seed) % self.size
            if self.bit_array[result] == 0:
                return 'Nope'
        return 'Probably'


bf = BloomFilter(1000, 3)  


bf.add("orange")

# 返回 "Probably"
print(bf.lookup("orange"))

# 可能返回 "Nope" 或 "Probably"
print(bf.lookup("apple"))

其中:

hash_count 是用于指定在生成布隆过滤器时将使用多少个不同的哈希函数。每个哈希函数都将元素映射到一个唯一的位数组索引。通过使用多个哈希函数，可以确保元素在布隆过滤器中的存在性检测更加准确和可靠。

size 是指位数组的大小。位数组是布隆过滤器的基础数据结构，用于存储元素哈希值的位。每个位数组元素只能是一个布尔值（0 或 1），表示对应的哈希值是否存在于集合中。因此，size 的大小将直接影响到布隆过滤器的准确性和空间效率。

pip install bitarray

from bitarray import bitarray  
from hashlib import md5  
  
class BloomFilter:  
    def __init__(self, size, hash_num):  
        self.size = size  
        self.hash_num = hash_num  
        self.bit_array = bitarray(size)  
        self.bit_array.setall(0)
        
 def add(self, string):  
        for seed in range(self.hash_num):  
            result = md5((string + str(seed)).encode()).digest()  
            self.bit_array[int(result[0]) % self.size] = 1
            
 def lookup(self, string):  
        for seed in range(self.hash_num):  
            result = md5((string + str(seed)).encode()).digest()  
            if self.bit_array[int(result[0]) % self.size] == 0:  
                return "Nope"
        return "Probably"

bf = BloomFilter(1000, 3)  


bf.add("orange")

# 返回 "Probably"
print(bf.lookup("orange"))

# 可能返回 "Nope" 或 "Probably"
print(bf.lookup("apple"))

python使用redis的布隆过滤器

首先开启redis服务, 并在python中安装redis库

pip install redis

import redis  


r = redis.Redis(host='localhost', port=6379, db=0)  
  
# 创建布隆过滤器，预计存储10000个元素，错误率设置为0.01  
r.bf.reserve('urls', 10000, 0.01)  
  
# 添加元素到布隆过滤器  
r.bf.add('urls', 'some_key')  
  
# 检查元素是否存在于布隆过滤器中  
exists = r.bf.exists('my_bloom_filter', 'some_key')  
if exists:  
    print("元素可能存在于布隆过滤器中")  
else:  
    print("元素不存在于布隆过滤器中")

r.close()