一、算法介紹
布隆過濾器是一種多哈希函數映射的快速查找算法，通常用于在大資料量場景下快速判斷資料存在性。該算法通過犧牲正确性進而在空間和時間上都有不錯的效率。
二、算法原理
當一個元素被加入集合時，通過N個散列函數将這個元素映射成一個位圖中的N個點，将它們置為1。判斷某個元素是否存在時，通過這些點是不是都是1即可：如果這些點有任何一個0，則目标元素一定不在；如果都是1，則目标元素很可能在。例如，一個集合中隻存在一個apple元素，其經過三個哈希函數計算映射在位圖中三個位，此時判斷orange是否存在于集合中，同樣經過三個哈希函數計算，我們發現有一位為0，是以orange一定不存在于集合中。
三、算法實作
構造一個布隆過濾器需要一個給定長度的位圖和N個哈希函數，那麼問題來了，這個位圖到底要多大？到底要多少個哈希函數呢？這裡引入兩個公式：
根據預估資料量n以及誤判率fpp，位圖大小m的計算方式：
根據預估資料量n以及位圖長度m，哈希函數個數k的計算方式：
根據公式我們可以明顯看出，當資料量越大、誤判率越低，則位圖長度越大。
關于m和k的計算，我們可以看一下Guava中的實作：
解決了位圖長度和哈希函數個數的計算問題，接下來我們看看哈希函數選取問題，一般情況下我們都需要三個甚至更多的哈希函數，我們如果真要去準備這些函數那就太麻煩了，這裡我們可以參考如下論文：
https://www.ccs.neu.edu/home/pete/pub/bloom-filters-verification.pdf
這篇論文提出了一種算法，把原本需要N個哈希函數的計算轉化成了兩個哈希值的運算，完美地解決了這個問題。如下所示：
上述公式中f(i)為第i個哈希函數。其中0 < i < k。也就是說使用a()和b()對一次輸入求出兩個不同的哈希值，然後将這兩個哈希值代入此公式，便可求出N個哈希值。 在Guava中同樣采用此算法，Guava的布隆過濾器中實作了MURMUR128_MITZ_32和MURMUR128_MITZ_64兩種政策，我們以MURMUR128_MITZ_32為例看看：
計算邏輯如下：
1）根據Murmur3算法計算出輸入對象的64位哈希值，并将其分為兩段，後32位為hash1，前32位為hash2，hash1對應公式中的函數a的傳回值，hash2對應公式中的函數b的傳回值；
2）将hash1、hash2和需要的哈希個數numHashFunctions代入公式中，逐個計算出每一個哈希值。