這次kata的內(nèi)容:實(shí)現(xiàn)一個(gè)布隆過濾器
布隆過濾器 (Bloom Filter)
什么是布隆過濾器呢?簡單來說, 布隆過濾器可以告訴你一個(gè)元素是否在一個(gè)集合中.
有同學(xué)可能就會說了, 這很簡單啊, 集合中本來就有所有的元素, 我只要檢查輸入內(nèi)容是否在里面不就行了.
沒錯(cuò), 這種方法成功率最高(100%), 但是效率最低.
如果只是處理十個(gè)字符串潮秘、一百個(gè)字符串, 這都沒問題, 但是如果要處理成百上千萬的字符串, 顯然是不可行的, 空間和時(shí)間都無法接受.
這時(shí)候該主角出場了——布隆過濾器.
布隆過濾器的核心思想就是用盡可能少的空間來存儲盡可能多的內(nèi)容, 同時(shí)盡量保證準(zhǔn)確率.布隆過濾器本質(zhì)上很像哈希表, 把一個(gè)大的空間映射到一個(gè)小的空間, 那么問題就來了, 如果兩個(gè)不同元素映射到了同一個(gè)位置怎么辦呢?哈希表有各種算法可以解決沖突, 但是布隆過濾器非常簡單粗暴——我才不管你, 映射到同一個(gè)位置那就存同一個(gè)位置.
因此, 布隆過濾器的準(zhǔn)確率并不是100%.準(zhǔn)確地說, 布隆過濾器具有假陽性, 也就是說如果它告訴你一個(gè)元素在集合中, 那這個(gè)結(jié)果可能是錯(cuò)誤的, 因?yàn)橛锌赡苓@個(gè)元素和集合中另一個(gè)不同的元素映射到了同一位置.但是反過來, 如果它告訴你一個(gè)元素不在集合中, 那這個(gè)元素就肯定不在集合中.所以布隆過濾器在某些場景下是非常合適的.
為了進(jìn)一步壓縮空間同時(shí)提高準(zhǔn)確率, 布隆過濾器有很多種改進(jìn)方法, 其中比較常用的是把一個(gè)元素映射到結(jié)果集中的多個(gè)位(bit).舉例來說, 假設(shè)每個(gè)元素會被映射到5個(gè)點(diǎn), 那么兩個(gè)元素只要有一個(gè)點(diǎn)不相同就可以判斷出來识虚；但是如果只映射到一個(gè)點(diǎn), 那么這個(gè)點(diǎn)只要相同就無法準(zhǔn)確判斷了, 因此映射到多個(gè)點(diǎn)可以增加準(zhǔn)確度.此外, 這個(gè)方法還可以壓縮空間, 因?yàn)橛成湟粋€(gè)點(diǎn)的時(shí)候, 為了減少碰撞我們必須使用很大的空間, 但是映射多個(gè)點(diǎn)的時(shí)候, 多個(gè)點(diǎn)全部相同的概率很小, 所以我們就可以使用比較小的空間.
