BloomFilter概述：

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

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

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

?也就是說x1經(jīng)過三次hash那么設(shè)置對應(yīng)的下標(biāo)為1，x2同理，當(dāng)查找判斷的時(shí)候我們只需要同樣獲取三次hash值進(jìn)行定位，當(dāng)都為1的時(shí)候證明存在，反之則不存在，如下所示：

也就是說y1為不存在，因?yàn)橛?，而y2，原則上存在，為什么是原則上呢？因?yàn)槎啻螌ξ患线M(jìn)行設(shè)置為1，而不清楚為0，那么很容易形成一個(gè)覆蓋，也就是說不存在的判斷是準(zhǔn)確的，而存在的判斷是不準(zhǔn)確的。

轉(zhuǎn)發(fā)請注明出處： http://snv.iteye.com/

總之：

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

2.BloomFilter能準(zhǔn)確判斷不存在的，概率性判斷存在的

3.常駐內(nèi)存對大數(shù)據(jù)操作很快

Hadoop中的實(shí)現(xiàn)：

      BloomFilter
CountingBloomFilter
DynamicBloomFilter
RetouchedBloomFilter
    

使用場景：

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

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

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

?

?