布隆去重(Bloom Filter)是一種高效的去重算法,廣泛應用于大規模數據的場景中。Python作為一門常用的編程語言,自然也有對應的布隆去重實現。
import hashlib import bitarray class BloomFilter: def __init__(self, size, hash_num): self.size = size self.hash_num = hash_num self.bit_array = bitarray.bitarray(size) self.bit_array.setall(0) def add(self, string): for seed in range(self.hash_num): result = int(hashlib.md5(string.encode('utf8')+str(seed).encode('utf8')).hexdigest(), 16) % self.size self.bit_array[result] = 1 def lookup(self, string): for seed in range(self.hash_num): result = int(hashlib.md5(string.encode('utf8')+str(seed).encode('utf8')).hexdigest(), 16) % self.size if self.bit_array[result] == 0: return "Nope" return "Probably"
以上的實現代碼中,我們通過哈希函數和位圖的方式實現了布隆去重的功能。其中,哈希函數使用了md5的算法,通過加上seed來生成多個不同的哈希函數。最后,將所有的哈希結果在位圖中設置為1,表示該字符串已經被添加到了布隆過濾器中。
而查詢的過程則是通過使用相同的哈希函數,判斷該字符串對應的位置是否已經為1,如果有一個位置不為1,則說明該字符串并沒有被添加過,返回"Nope",反之則返回"Probably"。
總體來說,布隆去重是一種犧牲一定的精確度換取高效率的算法,可用于構建大量數據的過濾器,達到快速查找和判斷是否存在的目的。