跟大家講解下有關海量數據處理算法之BloomFilter，相信小伙伴們對這個話題應該也很關注吧，現在就為小伙伴們說說海量數據處理算法之BloomFilter，小編也收集到了有關海量數據處理算法之BloomFilter的相關資料，希望大家看到了會喜歡。
算法介紹 Bloom Filter的中文名稱叫做布隆過濾器，因為他最早的提出者叫做布隆(Bloom)，因而而得此名。布隆過濾器簡單的說就是為了檢索一個元素是否存在于某個集合當中，以此實現數據的過濾。也許你會想，這還不簡單，判斷元素是否存在某集合中，遍歷集合，
算法介紹
Bloom Filter的中文名稱叫做布隆過濾器，因為他最早的提出者叫做布隆(Bloom)，因而而得此名。布隆過濾器簡單的說就是為了檢索一個元素是否存在于某個集合當中，以此實現數據的過濾。也許你會想，這還不簡單，判斷元素是否存在某集合中，遍歷集合，一個個去比較不就能得出結果，當然這沒有任何的問題，但是當你面對的是海量數據的時候，在空間和時間上的代價是非常恐怖的，顯然需要更好的辦法來解決這個問題，而Bloom Filter就是一個不錯的算法。具體怎么實現，接著往下看。
Bloom Filter先來說說傳統的元素檢索的辦法，比如說事先在內存中存儲了一堆的url字符數組，然后給定一個指定的url，判斷是否存在于之前的集合中，我們肯定是加載整個數組到內存中，然后一個個去比較，假設每條url字符平均所占的量只有幾個字節，但是當數據變為海量的時候，也足以撐爆整個內存，這是空間上的一個局限。再者，逐次遍歷的方式本身就是一種暴力搜索，搜索的時間將會隨著集合容量的本身而線性擴展，一旦數據量變大，查詢時間上的開銷也是非常恐怖的。針對時間和空間上的問題，Bloom Filter都給出了完美的解決辦法。首先第一個空間的問題，原本的數據占用的是字符，在這里我們用1個位占據，也就是說1個元素我用1/8的字節表示，不管你的url長度是10個字符，100字符，統統用一個位表示，所以在這里我們需要能夠保證每個字符所代表的位不能沖突。因為用到了位的存儲，我們需要對數據進行一個hash映射，以此得到他的位置，然后將此位置上的位置標為1(默認都是為0)。所以說白了，Bloom Filter就是由一個很長的位數組和一些隨機的哈希函數構成。位數組你可以想象成下面的這種形式：
你可以想象這個長度非常長，反正1個單位就占據1個位，1k的空間就已經能夠表示1024*8=8192位了。所以說內存空間得到了巨大的節約。現在一個問題來了，為什么我剛剛用了一些隨機的哈希函數這個詞而不是說一個呢，因為會有哈希碰撞，再好的哈希函數也不能保證不會發生哈希沖突，所以這里需要采用多個哈希函數，所以元素是否存在的判斷條件就變為了只有所有的哈希函數映射的位置的值都是true的情況下，此元素才是存在于集合中的，這樣判斷的準確率就會大大提升了，哈希映射之后的效果圖如下：
假設我們的程序采用了如上圖所示的3個隨機獨立的哈希函數，1個元素需要進行3次不同的哈希函數的映射算法，對3個位置進行標記，對此元素的誤判概率我們做個計算，要使此元素誤判，就是說，他的這3個位置都有人占據了，就是說都與別的哈希函數有沖突，這最糟糕的情況就是他的3個映射位置與某個其他的元素通過哈希函數計算完全重疊，假設位空間長度1W位。每個位置被映射的概率就為1/1w，所以最糟糕的情況的沖突概率就是1/1w*1/1w*1/1w=1/10的12次方，如果最大的沖突概率的可能性呢，就是每個位置都與其中的某個哈希函數映射沖突，那誤差概率就是疊加的情況1/1w+1/1w+1/1w=0.0003。結果已經非常明顯了，通過3個哈希函數就已經能夠保證足夠低的誤判率了，更別說當你用4個，5個哈希函數做映射的情況。下面問題又轉移到了我們用什么方式去作為位數組呢，int數組，字符char數組，答案都不是。結果在下面。
BitSet這個是java中的某個數據類型，C,C++我目前不清楚有沒有這樣的類，為什么選用這個而不是前面說的int，或char數組，首先int當然不行，1個int本身就有32位，占了4個字節，用他做出0，1的存儲顯然相當于沒省下空間，自然我們就想到了用字符數組char[]，在C語言中1個char占一個字節，而在java中由于編碼方式的不同，一個char占2個字節，用char做存儲也只是稍稍比int介紹了一半的空間，并沒有真正的做到一個元素用一個位來表示，后來查了一下，java里面就有內置了BitSet專門就是做位存儲的，還能夠進行位相關的許多操作，他的操作其實就是和數組一樣，也是從0開始的。不熟悉的同學可以自行上網查閱相關資料，其實int數組也可以實現類似的功能，不過自己要做轉換，把int當成32位來算，之前我寫過相關的文章，是關于位示圖法存儲大數據。
算法的實現算法其實非常的簡單，我這里用一組少量的數據進行模擬。
輸入數據input.txt：
mikestudydaygetlastexamthinkfishhe然后是測試數據，用于查詢操作testInput.txt:playmikestudydaygetAxislastexamthinkfishhe其實就是我隨便組合的一些詞語。算法的工具類BloomFilterTool.java:
package BloomFilter;import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.IOException;import java.util.ArrayList;import java.util.BitSet;import java.util.HashMap;import java.util.Map;/** * 布隆過濾器算法工具類 * * @author lyq * */public class BloomFilterTool {// 位數組設置為10w位的長度public static final int BIT_ARRAY_LENGTH = 100000;// 原始文檔地址private String filePath;// 測試文檔地址private String testFilePath;// 用于存儲的位數組,一個單元用1個位存儲private BitSet bitStore;// 原始數據private ArrayList totalDatas;// 測試的查詢數據private ArrayList queryDatas;public BloomFilterTool(String filePath, String testFilePath) {this.filePath = filePath;this.testFilePath = testFilePath;this.totalDatas = readDataFile(this.filePath);this.queryDatas = readDataFile(this.testFilePath);}/** * 從文件中讀取數據 */public ArrayList readDataFile(String path) {File file = new File(path);ArrayList dataArray = new ArrayList();try {BufferedReader in = new BufferedReader(new FileReader(file));String str;String[] tempArray;while ((str = in.readLine()) != null) {tempArray = str.split("");for(String word: tempArray){dataArray.add(word);}}in.close();} catch (IOException e) {e.getStackTrace();}return dataArray;}/** * 獲取查詢總數據 * @return */public ArrayList getQueryDatas(){return this.queryDatas;}/** * 用位存儲數據 */private void bitStoreData() {long hashcode = 0;bitStore = new BitSet(BIT_ARRAY_LENGTH);for (String word : totalDatas) {// 對每個詞進行3次哈希求值，減少哈希沖突的概率hashcode = BKDRHash(word);hashcode %= BIT_ARRAY_LENGTH;bitStore.set((int) hashcode, true);hashcode = SDBMHash(word);hashcode %= BIT_ARRAY_LENGTH;bitStore.set((int) hashcode, true);hashcode = DJBHash(word);hashcode %= BIT_ARRAY_LENGTH;bitStore.set((int) hashcode, true);}}/** * 進行數據的查詢，判斷原數據中是否存在目標查詢數據 */public Map queryDatasByBF() {boolean isExist;long hashcode;int pos1;int pos2;int pos3;// 查詢詞的所屬情況圖Map word2exist = new HashMap();hashcode = 0;isExist = false;bitStoreData();for (String word : queryDatas) {isExist = false;hashcode = BKDRHash(word);pos1 = (int) (hashcode % BIT_ARRAY_LENGTH);hashcode = SDBMHash(word);pos2 = (int) (hashcode % BIT_ARRAY_LENGTH);hashcode = DJBHash(word);pos3 = (int) (hashcode % BIT_ARRAY_LENGTH);// 只有在3個哈希位置都存在才算真的存在if (bitStore.get(pos1) && bitStore.get(pos2) && bitStore.get(pos3)) {isExist = true;}// 將結果存入mapword2exist.put(word, isExist);}return word2exist;}/** * 進行數據的查詢采用普通的過濾器方式就是，逐個查詢 */public Map queryDatasByNF() {boolean isExist = false;// 查詢詞的所屬情況圖Map word2exist = new HashMap();// 遍歷的方式去查找for (String qWord : queryDatas) {isExist = false;for (String word : totalDatas) {if (qWord.equals(word)) {isExist = true;break;}}word2exist.put(qWord, isExist);}return word2exist;}/** * BKDR字符哈希算法 * * @param str * @return */private long BKDRHash(String str) {int seed = 31; long hash = 0;int i = 0;for (i = 0; i < str.length(); i++) {hash = (hash * seed) + (str.charAt(i));}hash = Math.abs(hash);return hash;}/** * SDB字符哈希算法 * * @param str * @return */private long SDBMHash(String str) {long hash = 0;int i = 0;for (i = 0; i < str.length(); i++) {hash = (str.charAt(i)) + (hash << 6) + (hash << 16) - hash;}hash = Math.abs(hash);return hash;}/** * DJB字符哈希算法 * * @param str * @return */private long DJBHash(String str) {long hash = 5381;int i = 0;for (i = 0; i < str.length(); i++) {hash = ((hash << 5) + hash) + (str.charAt(i));}hash = Math.abs(hash);return hash;}}場景測試類Client.java:package BloomFilter;import java.text.MessageFormat;import java.util.ArrayList;import java.util.Map;/** * BloomFileter布隆過濾器測試類 * * @author lyq * */public class Client {public static void main(String[] args) {String filePath ="C:\\Users\\lyq\\Desktop\\icon\\input.txt";String testFilePath ="C:\\Users\\lyq\\Desktop\\icon\\testInput.txt";// 總的查詢詞數int totalCount;// 正確的結果數int rightCount;long startTime = 0;long endTime = 0;// 布隆過濾器查詢結果Map bfMap;// 普通過濾器查詢結果Map nfMap;//查詢總數據ArrayList queryDatas;BloomFilterTool tool = new BloomFilterTool(filePath, testFilePath);// 采用布隆過濾器的方式進行詞的查詢startTime = System.currentTimeMillis();bfMap = tool.queryDatasByBF();endTime = System.currentTimeMillis();System.out.println("BloomFilter算法耗時"+ (endTime - startTime) +"ms");// 采用普通過濾器的方式進行詞的查詢startTime = System.currentTimeMillis();nfMap = tool.queryDatasByNF();endTime = System.currentTimeMillis();System.out.println("普通遍歷查詢操作耗時"+ (endTime - startTime) +"ms");boolean isExist;boolean isExist2;rightCount = 0;queryDatas = tool.getQueryDatas();totalCount = queryDatas.size();for (String qWord: queryDatas) {// 以遍歷的查詢的結果作為標準結果isExist = nfMap.get(qWord);isExist2 = bfMap.get(qWord);if (isExist == isExist2) {rightCount++;}else{System.out.println("預判錯誤的詞語："+ qWord);}}System.out.println(MessageFormat.format("Bloom Filter的正確個數為{0}，總查詢數為{1}個，正確率{2}", rightCount,totalCount, 1.0 * rightCount / totalCount));}}在算法的測試類中我對于Bloom Filter和普通的遍歷搜索方式進行了時間上的性能比較，當數據量比較小的時候，其實是看不出什么差距，甚至有可能布隆過濾器所花的時間可能更長比如我下面的某次測試結果：BloomFilter算法耗時2ms普通遍歷查詢操作耗時0msBloom Filter的正確個數為11，總查詢數為11個，【本文來自鴻網互聯 (http://www.68idc.cn)】正確率1但是當我用真實的測試數據進行測試，我把原始數據緩存了一篇標準的文檔，然后把查詢的結果詞語數量進行了翻倍，然后執行同樣的程序結果變為了下面這個樣子：BloomFilter算法耗時16ms普通遍歷查詢操作耗時47msBloom Filter的正確個數為2,743，總查詢數為2,743個，正確率1其實這還不足以模擬海量數據的場景，對于這個結果也不難理解，普通的暴力搜尋，是和原始數據的總量相關，時間復雜度為O(n)的，而Bloom Filter，則是常量級別，做一個哈希映射就OK 了，時間復雜度O(l),算法小結算法在實現的過程中遇到了一些小問題，第一就是在使用哈希函數的時候，因為我是隨機的選了3個字符哈希函數，后來發現老是會越界，一越界數值就會變為負的再通過BitSet就會報錯，原本在C語言中可以用unsigned int來解決，java中沒有這個概念，于是就直接取hash絕對值了。Bloom Filter算法的一個特點是數據可能會出現誤判，但是絕對不會漏判，誤判就是把不是存在集合中的元素判定成有，理由是哈希沖突可能造成此結果，而漏判指的是存在的元素判定成了不存在集合中，這個是絕對不可能的，因為如果你存在，你所代表的位置就一定會有被哈希映射到，一旦映射到了，在你再去查找就不會漏掉。算法的應用范圍其實挺多的，典型的比如垃圾郵箱地址的過濾。
來源：php中文網