bloom filter淺析(基本概念,概率分析,源碼分析)

Bloom filter是一種概率型數(shù)據(jù)結(jié)構(gòu)，用于判斷某個(gè)元素是否屬于一個(gè)集合。它可以快速地檢索元素，而不需要存儲(chǔ)實(shí)際的元素本身，因此具有很小的存儲(chǔ)空間。

基本概念：

1. 布隆過(guò)濾器使用一個(gè)位數(shù)組（bitmap）來(lái)表示集合，初始時(shí)所有位都被置為0。

2. 通過(guò)多個(gè)哈希函數(shù)將元素映射到位數(shù)組的不同位置上，將對(duì)應(yīng)位置的位設(shè)置為1。

3. 當(dāng)要查詢一個(gè)元素時(shí)，將該元素通過(guò)相同的哈希函數(shù)映射到位數(shù)組的相應(yīng)位置，如果所有對(duì)應(yīng)位置的位都為1，則表示該元素可能存在于集合中，否則一定不存在。

概率分析：

由于布隆過(guò)濾器使用多個(gè)哈希函數(shù)進(jìn)行映射，因此可能會(huì)存在哈希沖突的情況。假設(shè)布隆過(guò)濾器中有n個(gè)元素，位數(shù)組的長(zhǎng)度為m，使用k個(gè)哈希函數(shù)，則每個(gè)元素映射到位數(shù)組的位置的概率為1/m，因此一個(gè)位為0的位置的概率為(1-1/m)^kn。當(dāng)查詢一個(gè)元素時(shí)，如果所有對(duì)應(yīng)位置的位都為1，則表示該元素可能存在于集合中。但是有可能存在哈希沖突，導(dǎo)致其他元素也將對(duì)應(yīng)位置的位置為1，因此存在一定的誤判率。

源碼分析：

以下是一個(gè)簡(jiǎn)單的布隆過(guò)濾器的示例代碼：

from bitarray import bitarray
import mmh3
class BloomFilter:
def __init__(self, size, num_hashes):
self.size = size
self.num_hashes = num_hashes
self.bit_array = bitarray(size)
self.bit_array.setall(0)
def add(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.size
self.bit_array[index] = 1
def contains(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.size
if self.bit_array[index] == 0:
return False
return True
# 使用示例
bf = BloomFilter(1000000, 5)
bf.add("apple")
print(bf.contains("apple"))  # 輸出True
print(bf.contains("banana")) # 輸出False

這段代碼使用了第三方庫(kù)bitarray和mmh3來(lái)實(shí)現(xiàn)布隆過(guò)濾器。bitarray用于表示位數(shù)組，mmh3用于計(jì)算哈希值。在初始化布隆過(guò)濾器時(shí)，需要指定位數(shù)組的長(zhǎng)度和哈希函數(shù)的個(gè)數(shù)。add方法用于將元素添加到布隆過(guò)濾器中，contains方法用于判斷一個(gè)元素是否存在于布隆過(guò)濾器中。在查詢?cè)貢r(shí)，需要使用相同的哈希函數(shù)進(jìn)行計(jì)算，并檢查對(duì)應(yīng)位置的位是否為1。