布隆過濾器原理很簡單：就是把一個字符串哈希成一個整數key，然后選取一個很長的比特序列，開始都是0，在key把此位置的0變為1；下次進來一個字符串，哈希之后的值key，如果在此比特位上的值也是1，那么就說明這個字符串存在了。
如果按照上面的做法，那就和哈希算法沒有什么區別了，哈希算法還有重復的呢。
布隆過濾器是將一個字符串哈希成多個key，我還是按照書上的說吧。
先建立一個16億二進制常量，然后將這16億個二進制位全部置0。對于每個字符串，用8個不同的隨機產生器（F1,F2,.....,F8）產生8個信息指紋(f1,f2,....,f8).再用一個隨機數產生器G把這八個信息指紋映射到1到16億中的8個自然數g1,g2,...,g8。現在把這8個位置的二進制位全部變為1。這樣一個布隆過濾器就建好了。
那么如何檢測一個字符串是否已經存在了呢？
現在用8個隨機數產生器（F1,F2,...,F8）對這個字符串產生8個信息指紋s1,s2,...,s8，然后將這8個信息指紋對應到布隆過濾器的8個二進制位，分別是T1,T2,...,T8.如果字符串存在，那么顯然T1,T2,...,T8對應的二進制位都應該是1。就是這樣來判斷字符串是否已經存在的。
其實布隆過濾器就是對哈希算法的一個擴展，既然本質是哈希，那么就肯定會有不足，也就是說，肯定會有誤判，一個字符串明明沒有出現過而布隆過濾器判斷出現了，雖然可能性很小，但是確實存在。
那么如何減少這種概率呢，首先可以想到的是如果將8個信息指紋擴展到16個錯誤的概率肯定會降低，但是也要考慮到，這樣的話，那么一個布隆過濾器所能存儲的字符串數量也降低了1倍；另外就是選取很好的哈希函數，對字符串的哈希方法有很多種，其中不乏很好的哈希函數。
布隆過濾器主要運用在過濾惡意網址用的，將所有的惡意網址建立在一個布隆過濾器上，然后對用戶的訪問的網址進行檢測，如果在惡意網址中那么就通知用戶。這樣的話，我們還可以對一些常出現判斷錯誤的網址設定一個白名單，然后對出現判斷存在的網址再和白名單中的網址進行匹配，如果在白名單中，那么就放行。當然這個白名單不能太大，也不會太大，布隆過濾器錯誤的概率是很小的。有興趣的讀者可以去查閱，布隆過濾器的錯誤率。
下面給出Java版的布隆過濾器源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
import java.util.BitSet; /** * * @author xkey */ private static final int DEFAULT_SIZE = 2 << 24;//布隆過濾器的比特長度 private static final int[] seeds = {3,5,7, 11, 13, 31, 37, 61};//這里要選取質數，能很好的降低錯誤率 private static BitSet bits = new BitSet(DEFAULT_SIZE); private static SimpleHash[] func = new SimpleHash[seeds.length]; public static void addValue(String value) { for(SimpleHash f : func)//將字符串value哈希為8個或多個整數，然后在這些整數的bit上變為1 bits.set(f.hash(value),true); } public static void add(String value) { if(value != null) addValue(value); } public static boolean contains(String value) { if(value == null) return false; boolean ret = true; for(SimpleHash f : func)//這里其實沒必要全部跑完，只要一次ret==false那么就不包含這個字符串 ret = ret && bits.get(f.hash(value)); return ret; } public static void main(String[] args) { String value = "www.ythuaji.com.cn"; for (int i = 0; i < seeds.length; i++) { func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); } add(value); System.out.println(contains(value)); } } class SimpleHash {//這玩意相當于C++中的結構體 private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } public int hash(String value) {//字符串哈希，選取好的哈希函數很重要 int result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i); } return (cap - 1) & result; } } |
總結：布隆過濾器是對哈希算法的一種創新，而且需要消耗的空間也很小，錯誤率很低。總之這種創新的思路很值得學習，是一種對bit這種數據類型的運用。
以上這篇布隆過濾器(Bloom Filter)的Java實現方法就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
