python实现bloom filter
原创python实现bloom filter
原创
Bloom Filter是一种空间效率非常高的随机数据结构，用于判断一个元素是否属于一个集合。它的基本原理是使用多个哈希函数将元素映射到一个位数组中，如果一个元素对应的位都为1，则认为这个元素属于集合中。
其主要优点是空间效率非常高，因为它只需要使用一个位数组和多个哈希函数，就可以表示一个非常大的集合。另外，Bloom Filter还具有快速查询的特点，因为它只需要进行多次哈希运算和位操作，就可以判断一个元素是否属于集合中。
它的主要缺点是存在误判率，即有可能将不属于集合中的元素误判为属于集合中。这是因为多个元素可能映射到同一个位上，从而导致误判。误判率取决于位数组的大小和哈希函数的个数，可以通过调整这些参数来控制误判率。
Bloom Filter的应用非常广泛，例如网络路由器、搜索引擎、分布式系统等领域。它可以用于快速判断一个元素是否属于一个集合，从而避免了昂贵的磁盘或网络访问。另外，Bloom Filter还可以用于去重、数据压缩、数据同步等场景。
下面我们使用python代码简单实现一个bloom filter。定义了一个BloomFilter类，它接受两个参数：容量和误差率。在初始化函数中，我们计算出需要的位数和哈希函数的个数，并创建一个位数组。在添加元素时，使用多个哈希函数将元素映射到位数组中，并将对应的位设置为1。在查询元素时，同样使用多个哈希函数将元素映射到位数组中，并检查对应的位是否都为1。如果有任何一个位为0，则认为这个元素不属于集合中；否则，认为这个元素可能属于集合中。
在主函数中，创建一个Bloom Filter对象，并向其中添加了三个元素。然后，我们、、查询了两个元素，其中一个属于集合中，另一个不属于集合中。最后，打印出查询结果。
需要注意的是，Bloom Filter的误判率取决于位数组的大小和哈希函数的个数。在实际应用中，需要根据具体的场景和需求来选择合适的参数，以达到较低的误判率和较高的空间效率
import math
import mmh3
from bitarray import bitarray
class BloomFilter:
def __init__(self, capacity, error_rate):
self.capacity = capacity
self.error_rate = error_rate
self.num_bits = int(-capacity * math.log(error_rate) / math.log(2) ** 2)
self.num_hashes = int(self.num_bits * math.log(2) / capacity)
self.bits = bitarray(self.num_bits)
self.bits.setall(0)
def add(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.num_bits
self.bits[index] = 1
def __contains__(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.num_bits
if not self.bits[index]:
return False
return True
if __name__ == '__main__':
bf = BloomFilter(10000, 0.01)
bf.add("apple")
bf.add("banana")
bf.add("orange")
print("apple" in bf)
print("pear" in bf)原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。