hbase中Bloom filter是什么

這篇文章主要介紹了hbase中Bloom filter是什么，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

一、Bloom filter

適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集

基本原理及要點：

對 于原理來說很簡單，位數組+k個獨立hash函數。將 hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程并不保證查找的結果是100%正確的。同時也不 支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。

還 有一個比較重要的問題，如何根據輸入元素個數n，確定位數組m的大小及hash函數 個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集 合。但m還應該更大些，因為還要保證bit數組里至少一半為0，則m應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。

舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。

注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(準確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。

擴展：

Bloom filter將 集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。

問題實例：給你A,B兩個文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？

根 據這個問題我們來計算下內存的占用，4G=2^32大概是40億*8大概是340 億，n=50億，如果按出錯率0.01算需要的大概是650億個bit。現在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些 urlip是一一對應的，就可以轉換成ip，則大大簡單了。

感謝你能夠認真閱讀完這篇文章，希望小編分享的“hbase中Bloom filter是什么”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!