BloomFilter概述：

目的是檢索元素是否在某個集合中，基于hash，速度比較快，不需要存儲所有的元素，只需要按照某種方式存儲hash值即可，因此比較節約內存，因此可以常駐內存加快查找速度。同時利用多個hash來解決hash沖突問題

我們假定集合元素為一個列表，我們可以用一個bit列表來存儲此元素是否存在，如下所示：

?存在為1不存在為0，不過由于hash很容易沖突，那么可以基于多hash函數進行沖突的避免，每次設置對于的hash值為1，如下所示：

?也就是說x1經過三次hash那么設置對應的下標為1，x2同理，當查找判斷的時候我們只需要同樣獲取三次hash值進行定位，當都為1的時候證明存在，反之則不存在，如下所示：

也就是說y1為不存在，因為有0，而y2，原則上存在，為什么是原則上呢？因為多次對位集合進行設置為1，而不清楚為0，那么很容易形成一個覆蓋，也就是說不存在的判斷是準確的，而存在的判斷是不準確的。

轉發請注明出處： http://snv.iteye.com/

總之：

1. BloomFilter能很快的判斷某元素是否存在

2.BloomFilter能準確判斷不存在的，概率性判斷存在的

3.常駐內存對大數據操作很快

Hadoop中的實現：

      BloomFilter
CountingBloomFilter
DynamicBloomFilter
RetouchedBloomFilter
    

使用場景：

1.操作的文件很多，那么當一個請求過來之后首先在內存做判斷，如果有那么操作，如果沒有那么直接返回，如nosql系列等

2.大數據處理時，如爬蟲采集時對url做判斷，如果沒有采集過那么采集等

3.對否要求高，對是要求低的操作?

?

?