http://blog.csdn.net/jiaomeng/archive/2007/01/28/1496329.aspx

從哈希存儲到Bloom Filter

焦萌?2007年1月28日

?

先解釋一下什么是哈希函數。哈希函數簡單來說就是一種映射，它可取值的范圍（定義域）通常很大，但值域相對較小。哈希函數所作的工作就是將一個很大定義域內的值映射到一個相對較小的值域內。

傳統的哈希存儲

假設要哈希的集合為S，它有n個元素。傳統的哈希方法是，將哈希區域組織成h（h > n）個格子的列表，每一個格子都能存儲S中的一個元素。存儲時將S中的每一個元素映射到{0, 1, … , h-1}的范圍內，然后以這個值為索引將此元素存儲到對應的格子內。由于哈希函數將一個大集合映射到一個小集合中，所以存在將大集合中的多個元素映射到同一位置的情況，這就是所謂的碰撞（Collision）。當碰撞發生時，有多種策略可供選擇，比如用鏈表將映射到同一位置的元素串起來，或者在碰撞發生時再進行哈希映射直到找到空位為止等等。

?

?

傳統的哈希方法不會發生錯誤，而且存儲的元素還可以復原。如果哈希函數選擇得當，碰撞出現的情況比較少，那么查找某一個元素也很快。但是，如果你哈希某個集合只是為了判斷某個元素是否在這個集合中，那么你會發現好像存儲整個集合有點浪費。按傳統的哈希方法判斷某個元素是否屬于集合時，會把這個元素和它映射位置上的元素進行匹配，如果完全匹配則說明屬于集合，如果不匹配則不屬于。在絕大部分查找都不能匹配的情況下（這常常是實際中的情況），我們會發現匹配的過程經常用不到整個元素，因為元素的一部分就可以判斷不匹配了。基于“部分信息就能判斷不匹配”這個思路，Burton Bloom（Bloom Filter的發明者）提出了一種改進的方法。

改進的哈希存儲

在這種改進的方法中，哈希區域和前面一樣仍然被組織成格子的列表。但這次并不直接將集合元素存在格子里，而是將每一個元素編碼然后將編碼存在格子里。假設每個集合元素要占b位，編碼后要占c（c < b）位。由于編碼位數少于元素位數，不同元素的編碼有可能相同，因此在查找元素時可能會出現錯誤。編碼位數取決于你期望的錯誤率：編碼位數越多，錯誤就越少，反之則越大；當錯誤少到一定程度（大約2^-b），編碼位數就足以存下整個元素，因此就變回了傳統的哈希存儲。

?

?

這種方法對傳統的哈希存儲進行了改良，允許用戶在錯誤率和存儲空間之間作權衡。這里我們已經能夠看到Bloom Filter的一點端倪。如果說這種方法已經孕育了“正確率換空間”的思想的話，那么Bloom Filter更是這個思想的大膽實踐，它完全擺脫了傳統的哈希存儲方法，在存儲空間使用和減少錯誤率方面又進了一步。

Bloom Filter

在Bloom Filter中，哈希區域的每一位都被當成是獨立的可尋址的單元。在對集合元素進行編碼時，同時使用若干個獨立的哈希函數，將每一個哈希函數映射的地址都置為1。這種編碼方法可謂是另辟蹊徑，擺脫了原來一個格子一個格子的存儲方法。在改進的哈希存儲中，編碼位數是和正確率交換的籌碼，而在Bloom Filter中，籌碼變成了哈希函數的個數以及整個哈希區域（即位數組）的大小。如果想具體知道合適的哈希函數個數和位數組大小，請參閱第一篇Bloom Filter概念和原理。

?

和前面兩種哈希存儲方法相比，Bloom Filter最大的優勢自然是它的空間效率。另外，由于Bloom Filter不用處理碰撞（Collision），因此它在增加或查找集合元素時所用的時間完全恒定（哈希函數的計算時間），無論集合元素本身有多大，也無論多少集合元素已經加入到了位數組中。由于Bloom Filter和改進的哈希存儲都對集合元素進行了編碼，因此想要從哈希區域中恢復集合元素并不容易。但同時，如果你不想讓別人直接看到集合元素，這樣的編碼處理倒可以看成是一種加密，有效保護了你的隱私。

?

Bloom Filter很大的一個缺點就是不能刪除元素。由于Bloom Filter不處理碰撞，有可能多個哈希函數都映射到了同一位，因此不能簡單地在刪除時將1置為0。后面我們會看到，Counting Bloom Filter通過將每一位擴展為一個Counter來解決這一問題。

參考資料

[1] B. Bloom. Space/Time Tradeoffs in Hash Coding with Allowable Errors. Communications of the ACM 13:7 (1970), 422—426.

[2]?http://www.cs.berkeley.edu/~pbg/cs270/notes/lec27.pdf

[3]?http://security.riit.tsinghua.edu.cn/seminar/2006_11_16/hash_function_yaxuan.ppt

轉載于:https://www.cnblogs.com/iammatthew/archive/2010/09/16/1828191.html

總結

以上是生活随笔為你收集整理的【转】从哈希存储到Bloom Filter的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。