python实现布隆过滤器及原理解析

from pybloom_live import ScalableBloomFilter, BloomFilter

# 可自动扩容的布隆过滤器
bloom = ScalableBloomFilter(initial_capacity=100, error_rate=0.001)

url1 = 'http://www.baidu.com'
url2 = 'http://qq.com'

bloom.add(url1)
print(url1 in bloom)
print(url2 in bloom)
Copy
# BloomFilter 是定长的
from pybloom_live import BloomFilter

url1 = 'http://www.baidu.com'
url2 = 'http://qq.com'

bf = BloomFilter(capacity=1000)
bf.add(url1)
print(url1 in bf)
print(url2 in bf)

docker pull redislabs/rebloom:latest
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
docker exec -it redis-redisbloom /bin/bash

bf.reserve {key} {error_rate} {size}

127.0.0.1:6379> bf.reserve black_male 0.001 1000
OK

127.0.0.1:6379> bf.add test 123
(integer) 1
127.0.0.1:6379> bf.madd urls baidu google tencent
1) (integer) 0
2) (integer) 0
3) (integer) 1
# 上面已经存在的值再次添加会返回0， 不存在则返回1

127.0.0.1:6379> bf.exists test 123
(integer) 1
127.0.0.1:6379> bf.mexists urls baidu google hello
1) (integer) 1
2) (integer) 1
3) (integer) 0

# 自己的简单使用
from redisbloom.client import Client

# 因为我使用的是虚拟机中docker的redis, 填写虚拟机的ip地址和暴露的端口
rb = Client(host='192.168.12.78', port=6379)
rb.bfAdd('urls', 'baidu')
rb.bfAdd('urls', 'google')
print(rb.bfExists('urls', 'baidu')) # out: 1
print(rb.bfExists('urls', 'tencent')) # out: 0

rb.bfMAdd('urls', 'a', 'b')
print(rb.bfMExists('urls', 'google', 'baidu', 'tencent')) # out: [1, 1, 0]

def _test1(size, key='book'):
 """测试size个不存在的"""
 rb.delete(key) # 先清空原来的key
 insert(size, key)
 select(size, key)


def _test2(size, error=0.001, key='book'):
 """指定误差率和初始大小的布隆过滤器"""
 rb.delete(key)

 rb.bfCreate(key, error, size) # 误差率为0.1%， 初始个数为size

 insert(size, key)
 select(size, key)


if __name__ == '__main__':
 # The default error rate is 0.01 and the default initial capacity is 100.
 # 这个是默认的配置， 初始大小为100， 误差率默认为0.01
 _test1(1000)
 _test1(10000)
 _test1(100000)
 _test2(500000)
Copy
# 输出的结果

插入结束... 花费时间: 0.0409s
size: 1000, 误判元素个数: 14, 误判率1.4000%
查询结束... 花费时间: 0.0060s
******************************
插入结束... 花费时间: 0.1389s
size: 10000, 误判元素个数: 110, 误判率1.1000%
查询结束... 花费时间: 0.0628s
******************************
插入结束... 花费时间: 0.5372s
size: 100000, 误判元素个数: 1419, 误判率1.4190%
查询结束... 花费时间: 0.4318s
******************************
插入结束... 花费时间: 1.9484s
size: 500000, 误判元素个数: 152, 误判率0.0304%
查询结束... 花费时间: 2.2177s
******************************

import redis
from redisbloom.client import Client

# 创建一个连接池来进行使用
pool = redis.ConnectionPool(host='192.168.12.78', port=6379, max_cOnnections=100)


def create_key(key, error, capacity):
 rb = Client(connection_pool=pool)
 rb.bfCreate(key, errorRate=error, capacity=capacity)


def get_item(key, item):
 """判断是否存在"""
 rb = Client(connection_pool=pool)
 return rb.bfExists(key, item)


def add_item(key, item):
 """添加值"""
 rb = Client(connection_pool=pool)
 return rb.bfAdd(key, item)


if __name__ == '__main__':
 # 添加黑名单, 误差为0.001， 大小为1000
 create_key('blacklist', 0.001, 1000)
 add_item('blacklist', 'user:1')
 add_item('blacklist', 'user:2')
 add_item('blacklist', 'user:3')
 add_item('blacklist', 'user:4')
 print('user:1是否在黑名单-> ', get_item('blacklist', 'user:1'))
 print('user:2是否在黑名单-> ', get_item('blacklist', 'user:2'))
 print('user:6是否在黑名单-> ', get_item('blacklist', 'user:6'))