先來看幾個比較常見的例子
字處理軟件中，需要檢查一個英語單詞是否拼寫正確
在 FBI，一個嫌疑人的名字是否已經(jīng)在嫌疑名單上
在網(wǎng)絡(luò)爬蟲里，一個網(wǎng)址是否被訪問過
yahoo, gmail等郵箱垃圾郵件過濾功能
這幾個例子有一個共同的特點： 如何判斷一個元素是否存在一個集合中？
數(shù)組
鏈表
樹、平衡二叉樹、Trie
Map (紅黑樹)
哈希表
雖然上面描述的這幾種數(shù)據(jù)結(jié)構(gòu)配合常見的排序、二分搜索可以快速高效的處理絕大部分判斷元素是否存在集合中的需求。但是當集合里面的元素數(shù)量足夠大，如果有500萬條記錄甚至1億條記錄呢？這個時候常規(guī)的數(shù)據(jù)結(jié)構(gòu)的問題就凸顯出來了。數(shù)組、鏈表、樹等數(shù)據(jù)結(jié)構(gòu)會存儲元素的內(nèi)容，一旦數(shù)據(jù)量過大，消耗的內(nèi)存也會呈現(xiàn)線性增長，最終達到瓶頸。有的同學可能會問，哈希表不是效率很高嗎？查詢效率可以達到O(1)。但是哈希表需要消耗的內(nèi)存依然很高。使用哈希表存儲一億 個垃圾 email 地址的消耗？哈希表的做法：首先，哈希函數(shù)將一個email地址映射成8字節(jié)信息指紋；考慮到哈希表存儲效率通常小于50%（哈希沖突）；因此消耗的內(nèi)存：8 * 2 * 1億 字節(jié) = 1.6G 內(nèi)存，普通計算機是無法提供如此大的內(nèi)存。這個時候，布隆過濾器（Bloom Filter）就應(yīng)運而生。在繼續(xù)介紹布隆過濾器的原理時，先講解下關(guān)于哈希函數(shù)的預(yù)備知識。
哈希函數(shù)的概念是：將任意大小的數(shù)據(jù)轉(zhuǎn)換成特定大小的數(shù)據(jù)的函數(shù)，轉(zhuǎn)換后的數(shù)據(jù)稱為哈希值或哈希編碼。下面是一幅示意圖：
可以明顯的看到，原始數(shù)據(jù)經(jīng)過哈希函數(shù)的映射后稱為了一個個的哈希編碼，數(shù)據(jù)得到壓縮。哈希函數(shù)是實現(xiàn)哈希表和布隆過濾器的基礎(chǔ)。
巴頓.布隆于一九七零年提出
一個很長的二進制向量 （位數(shù)組）
一系列隨機函數(shù) (哈希)
空間效率和查詢效率高
有一定的誤判率（哈希表是精確匹配）
布隆過濾器（Bloom Filter）的核心實現(xiàn)是一個超大的位數(shù)組和幾個哈希函數(shù)。假設(shè)位數(shù)組的長度為m，哈希函數(shù)的個數(shù)為k
以上圖為例，具體的操作流程：假設(shè)集合里面有3個元素{x, y, z}，哈希函數(shù)的個數(shù)為3。首先將位數(shù)組進行初始化，將里面每個位都設(shè)置位0。對于集合里面的每一個元素，將元素依次通過3個哈希函數(shù)進行映射，每次映射都會產(chǎn)生一個哈希值，這個值對應(yīng)位數(shù)組上面的一個點，然后將位數(shù)組對應(yīng)的位置標記為1。查詢W元素是否存在集合中的時候，同樣的方法將W通過哈希映射到位數(shù)組上的3個點。如果3個點的其中有一個點不為1，則可以判斷該元素一定不存在集合中。反之，如果3個點都為1，則該元素可能存在集合中。注意：此處不能判斷該元素是否一定存在集合中，可能存在一定的誤判率。可以從圖中可以看到：假設(shè)某個元素通過映射對應(yīng)下標為4，5，6這3個點。雖然這3個點都為1，但是很明顯這3個點是不同元素經(jīng)過哈希得到的位置，因此這種情況說明元素雖然不在集合中，也可能對應(yīng)的都是1，這是誤判率存在的原因。
將要添加的元素給k個哈希函數(shù)
得到對應(yīng)于位數(shù)組上的k個位置
將這k個位置設(shè)為1
將要查詢的元素給k個哈希函數(shù)
得到對應(yīng)于位數(shù)組上的k個位置
如果k個位置有一個為0，則肯定不在集合中
如果k個位置全部為1，則可能在集合中
下面給出python的實現(xiàn)，使用murmurhash算法
import mmh4from bitarray import bitarray# zhihu_crawler.bloom_filter# Implement a simple bloom filter with murmurhash algorithm.# Bloom filter is used to check wether an element exists in a collection, and it has a good performance in big data situation.# It may has positive rate depend on hash functions and elements count.BIT_SIZE = 5000000class BloomFilter: def __init__(self): # Initialize bloom filter, set size and all bits to 0 bit_array = bitarray(BIT_SIZE) bit_array.setall(0) self.bit_array = bit_array def add(self, url): # Add a url, and set points in bitarray to 1 (Points count is equal to hash funcs count.) # Here use 7 hash functions. point_list = self.get_postions(url) for b in point_list: self.bit_array[b] = 1 def contains(self, url): # Check if a url is in a collection point_list = self.get_postions(url) result = True for b in point_list: result = result and self.bit_array[b] return result def get_postions(self, url): # Get points positions in bit vector. point1 = mmh4.hash(url, 41) % BIT_SIZE point2 = mmh4.hash(url, 42) % BIT_SIZE point3 = mmh4.hash(url, 43) % BIT_SIZE point4 = mmh4.hash(url, 44) % BIT_SIZE point5 = mmh4.hash(url, 45) % BIT_SIZE point6 = mmh4.hash(url, 46) % BIT_SIZE point7 = mmh4.hash(url, 47) % BIT_SIZE return [point1, point2, point3, point4, point5, point6, point7]
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
重慶分公司
重慶分公司
