怎么做属于自己的音乐网站,wordpress页眉置顶,wordpress 大神,ui毕业设计代做网站布隆过滤器是一种空间效率极高的概率数据结构#xff0c;用于测试一个元素是否是集合的成员。如果布隆过滤器返回 False#xff0c;则元素绝对不在集合中。如果返回 True#xff0c;则元素可能在集合中#xff0c;但也可能是一个误报。布隆过滤器利用了多个不同的哈希函数对…布隆过滤器是一种空间效率极高的概率数据结构用于测试一个元素是否是集合的成员。如果布隆过滤器返回 False则元素绝对不在集合中。如果返回 True则元素可能在集合中但也可能是一个误报。布隆过滤器利用了多个不同的哈希函数对元素进行哈希并将结果的位置在一个位数组上设置为 1。
1. redis5.0以上版本的布隆过滤器实现RedisBloom
RedisBloom 是 Redis 的一个模块提供了 Bloom Filter、Cuckoo Filter、Count-Min Sketch 和 Top-K 这些数据结构。这些数据结构特别适用于处理海量数据的场景因为它们是空间有效和计算高效的。
1.1 安装 RedisBloom:
确保你已经安装了 Redis。然后你可以从 RedisBloom 的 GitHub 存储库下载并构建它。
git clone --recursive https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make这将生成一个名为 redisbloom.so 的共享对象文件。
1.2 运行 Redis 与 RedisBloom 模块:
redis-server --loadmodule ./redisbloom.so1.3 使用 Bloom Filter:
接下来你可以使用 redis-cli 或任何 Redis 客户端库与 Redis 交互。
例如使用 redis-cli
redis-cli添加元素到 Bloom Filter:
127.0.0.1:6379 BF.ADD myfilter item1
(integer) 1检查元素是否存在:
127.0.0.1:6379 BF.EXISTS myfilter item1
(integer) 1
127.0.0.1:6379 BF.EXISTS myfilter item2
(integer) 01.4 Python 示例:
要在 Python 中使用 RedisBloom你需要安装 redis-py 和 redisbloom 客户端库。
pip install redis redisbloom然后你可以这样使用
import redis
from redisbloom.client import Clientclient Client(hostlocalhost, port6379)
client.bfCreate(myfilter, errorRate0.01, capacity10000)
client.bfAdd(myfilter, item1)
print(client.bfExists(myfilter, item1)) # True
print(client.bfExists(myfilter, item2)) # False2. redis5.0以下版本的布隆过滤器实现手写实现
2.1 安装必要的库:
pip install redis bitarray2.2 布隆过滤器实现:
from datetime import datetime
import redis
from hashlib import md5class SimpleHash(object):def __init__(self, cap, seed):self.cap capself.seed seeddef hash(self, value):ret 0for i in range(len(value)):ret self.seed * ret ord(value[i])return (self.cap - 1) retclass BloomFilter(object):def __init__(self, host10.9.50.171, port6379, db1, passwordasmd888, keybloomfilter)::param host: the host of Redis:param port: the port of Redis:param db: witch db in Redis:param blockNum: one blockNum for about 90,000,000; if you have more strings for filtering, increase it.:param key: the keys name in Redisself.server redis.Redis(hosthost, portport, dbdb, passwordpassword, decode_responsesTrue)self.bit_size 1 25 # Redis的String类型最大容量为512M现使用4M误报率为(九/一百万)self.seeds [5, 7, 11, 13, 31, 37, 61]# self.seeds [5, 7, 11, 13, 31]self.key keyself.hashfunc []for seed in self.seeds:self.hashfunc.append(SimpleHash(self.bit_size, seed))def isContains(self, str_input):# 判断是否存在:param str_input::return:if not str_input:return Falsem5 md5()m5.update(str_input.encode())str_input m5.hexdigest()ret Truefor f in self.hashfunc:loc f.hash(str_input)bit_name self.server.getbit(self.key, loc)ret ret bit_namereturn retdef insert(self, str_input):添加新的值:param str_input::return:m5 md5()m5.update(str_input.encode())str_input m5.hexdigest()for f in self.hashfunc:loc f.hash(str_input)self.server.setbit(self.key, loc, 1)if __name__ __main__: 第一次运行时会显示 not exists!之后再运行会显示 exists! bf BloomFilter()old datetime.now()name www.baidusasdfasf.asdd4564asdif bf.isContains(name): # 判断字符串是否存在print(exists!)else:print(not exists!)bf.insert(name)new datetime.now()print(new - old)
