快花滤池
LessHash-BloomFilter的Python项目详细描述
更少的哈希bloom筛选器
少哈希bloom filter是一种适用于大数据量的快速bloomfilter。
计算散列函数和检查元素的存在是一个主要的计算开销。 此外，bloom filter需要多个独立的散列函数，而精心设计的散列函数是计算密集型的，如md5、sha-1[1]。
在这个实现中，我们使用一种不同的技术，只从两个函数生成k散列函数。因此，布卢姆过滤器是快速的。
安装
使用pip安装更少的hash bloom过滤器，如下所示：
$ pip install LessHash-BloomFilter
使用量
lhbf需要知道bloom过滤器的大小和散列函数的数目。
注意：应该使用highm来避免哈希函数的冲突。两个随机字符串碰撞的概率为~1/m
fromlhbfimportBloomFilter# Create a bloom filter bf=BloomFilter(m=200,k=2)# Add an elementbf.add("a")# Check if element existsbf.might_contain("a")# Estimate flase positive probability bf.estimate_fpp()# Combine two bloom filtersbf2=BloomFilter(m=200,k=2)bf.combine(bf2)
详细信息
使用的哈希函数：
- 对于整数，我们使用knuth乘法哈希[2]
- 对于字符串，我们使用多项式滚动哈希函数[3]
k散列函数：
使用两个散列函数，我们计算k个散列函数如下：
gi（x）=h1（x）+i x h2（x）mod m，其中0≤i≤k-1
已经证明，使用该方法不会增加渐近误报概率[4]。
贡献
欢迎随时提交对此存储库的任何更改的拉取请求。我很高兴看到有什么贡献。
参考文献
- [1]罗，来龙，等.优化bloom过滤器：挑战、解决方案和比较。IEEE通信调查和教程（2018年）。
- [2]克努特，唐纳德·欧文。计算机程序设计的艺术：排序和搜索。第三卷。皮尔逊教育，1997年。
- [3]卡普，理查德M.和迈克尔O.拉宾。有效的随机模式匹配算法。IBM研究与发展杂志31.2（1987）：249-260.
- [4]基尔希，亚当，迈克尔·米岑马赫。更少的散列，同样的性能：构建更好的bloom过滤器。欧洲算法研讨会。斯普林格，柏林，海德堡，2006年。
欢迎加入QQ群-->： 979659372
