A. 布隆過濾器既然有錯誤率，為什麼還能應用在key-value系統中
bloom filter的特點是會出現誤報，但不會漏報，也就是說對於bloom filter驗證的一個數據內文件，可能不包含容你查找的數據項，但是包含你查找的數據項的數據文件它一定是會返回的，key-value系統中bloom filter返回的數據文件還是需要查看裡面的內容才能知道是否存在所需的數據的，這就保證了執行結果的正確性和完整性。因此key-value系統不會因此而出錯的，只是多訪問一些數據文件而已。在數據量很大key-value系統中，建立統一的B+樹索引的代價是非常大的，維護成本也很高，因此綜合起來bloom filter的性能是最好的。
B. 布隆過濾器
[TOC]
通過解決方案：
Java中如將數據存儲在內存中，最簡單的演算法結構是HashMap。通過HashMap判斷key是否存在，來判斷數據是否存在。通過hash演算法查找元素，時間復雜度基本是 O(1) （可能存在hash沖突後轉換成鏈表或紅黑樹的情況，時間復雜度的影響可以忽略）。
使用HashMap速度很快，存儲簡單，絕大部分場景可以使用。但是HashMap 佔用的空間比較大 ：
為什麼出現布隆過濾器：
舉例：
如1000萬個Integer存儲在內存中，佔用空間為：4x32x10000000位，即1220兆。如布隆過濾器通過4位元組存儲（布隆過濾器通過多次hash對數據計算後-->幾次hash根據數據量指定，得到多個數據， 佔用多個位 ），則佔用空間為610M。比原有空間少一半。
個人覺得，此比較在字元等的比較中尤為有效。
一個字元串多個字元，根據編碼方式，一個字元兩個或三個位元組，如10個字元，字元串存儲佔用20個位元組，還有相關字元串相關的類信息的內存佔用。
位存儲，根據數據量的大小，hash的位數，靈活計算。如4個位元組，則是原hashMap佔用空間的五分之一。
（1）定義位元組向量
先定義一個指定長度的位元組數組（位元組數組，數組內每個元素的值）。
如長度為8（一個位元組大小），默認所有元素值均為0，如下：
（2）計算哈希值
將要寫入過濾器的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。
（3）更新位元組向量
將計算出的位元組向量的索引， 對應的位元組向量中的元素值更高為1 （無論之前為0或者為1，均更改為1）。如下：
（1）計算哈希值
將要判斷過濾器中是否存在的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。
注意：哈希函數的判斷方式和計算索引的方式，需和寫入數據時完全一致。
（2）判斷是否存在
如原位元組數組中，對應1，3，7中存在的元素的值都為1。則判定為此元素 可能存在 ，但凡有一個元素的值不為1，則判定此元素 一定不存在 。
布隆過濾器，主要需實現的目標是， 在指定的數據個數范圍內，滿足誤判率在設定的范圍內 ，誤判率太高的話，無法起到過濾數據的情況，誤判率不能為0。
因此需要計算兩個數據來滿足 存儲數據的個數 和 誤判率 ：
使用布隆過濾器的決定性因素之一，就是此演算法插入數據和查詢數據的速度必須非常快。因此在對數據進行哈希運算的時候， 需選擇計算快的哈希演算法 。
而且， 寫入數據以及查詢數據的哈希演算法，順序和演算法都需完全一致 。
待完善。。。。。
可以通過google的 guava ，在內存中輕松實現布隆過濾器。
無需手動計算滿足位元組數組的長度和哈希個數，只需要輸入 擬輸入數據的個數 和 期望誤判率 即可。
不輸入期望誤判率的情況下，誤判率為0.03，即100個非范圍內的數據進行校驗時，約三個數據會判定為存在。
多次執行，結果一致，根據結果判定：
內存的存儲存在局限性，可以使用redis中的bitMap來實現位元組數組的存儲。
使用redis實現布隆過濾器。需要根據公式，手動計算位元組數組的長度和哈希的個數。
實現過程，待完善。。。。。。