本文已收錄至Github，推薦閱讀 ?? Java隨想錄
微信公眾號：Java隨想錄
目錄- 問題描述
- BloomFilter(布隆過濾器)
- fpp
- 布隆過濾器的特點
- 布隆過濾器中的資料可不可以洗掉
- 布隆過濾器應該設計為多大？
- 布隆過濾器應該使用多少個哈希函式？
- 布隆過濾器的時間復雜度和空間復雜度?
- Guava的布隆過濾器的實作
- BitMap
問題描述
在開發程序中，經常要判斷一個元素是否在一個集合中，假設你現在要給專案添加IP黑名單功能，此時你手上有大約 1億個惡意IP的資料集，有一個IP發起請求，你如何判斷這個IP在不在你的黑名單中？
類似這種問題用Java自己的Collection和Map很難處理，因為它們存盤元素本身，會造成記憶體不足，而我們只關心元素存不存在，對于元素的值我們并不關心，具體值是什么并不重要，
BloomFilter(布隆過濾器)
布隆過濾器可以用來判斷某個元素是否在集合內，具有運行快速，記憶體占用小的特點，它是一個保存了很長的二級制向量，同時結合 Hash 函式實作的，而高效插入和查詢的代價就是，它是一個基于概率的資料結構，只能告訴我們一個元素絕對不在集合內，對于存在集合內有一定的誤判率，
fpp
因為布隆過濾器中總是會存在誤判率，因為哈希碰撞是不可能百分百避免的，布隆過濾器對這種誤判率稱之為假陽性概率，即：False Positive Probability，簡稱為 fpp，
在實踐中使用布隆過濾器時可以自己定義一個 fpp，然后就可以根據布隆過濾器的理論計算出需要多少個哈希函式和多大的位陣列空間，需要注意的是這個 fpp 不能定義為 100%，因為無法百分保證不發生哈希碰撞，
下圖表示向布隆過濾器中添加元素 https://blog.csdn.net/bookssea 和 https://www.abc.com 的程序，它使用了 func1 和 func2 兩個簡單的哈希函式，
對寫入的資料做 H 次 hash 運算定位到陣列中的位置，同時將資料改為 1 ，當有資料查詢時也是同樣的方式定位到陣列中， 一旦其中的有一位為 0 則認為資料肯定不存在于集合，否則資料可能存在于集合中，
通過其原理可以知道，可我們可以提高陣列長度以及 hash 計算次數來降低誤報率，但是相應的 CPU、記憶體的消耗也會相應的提高；這需要我們根據自己的業務需要去權衡選擇，
布隆過濾器的特點
布隆過濾有以下2個特點：
- 只要回傳資料不存在，則肯定不存在，
- 回傳資料存在，但只能是大概率存在，
在有限的陣列長度中存放大量的資料，即便是再完美的 Hash 演算法也會有沖突，所以有可能兩個完全不同的 A、B 兩個資料最后定位到的位置是一模一樣的，這時拿 B 進行查詢時那自然就是誤報了，
布隆過濾器中的資料可不可以洗掉
布隆過濾器判斷一個元素存在就是判斷對應位置是否為 1 來確定的，但是如果要洗掉掉一個元素是不能直接把 1 改成 0 的，因為這個位置可能存在其他元素，所以如果要支持洗掉，最簡單的做法就是加一個計數器，就是說位陣列的每個位如果不存在就是 0，存在幾個元素就存具體的數字，而不僅僅只是存 1，那么這就有一個問題，本來存 1 就是一位就可以滿足了，但是如果要存具體的數字比如說 2，那就需要 2 位了，所以帶有計數器的布隆過濾器會占用更大的空間，
<dependency>
<groupId>com.baqend</groupId>
<artifactId>bloom-filter</artifactId>
<version>1.0.7</version>
</dependency>
新建一個帶有計數器的布隆過濾器 CountingBloomFilter：
import orestes.bloomfilter.FilterBuilder;
public class CountingBloomFilter {
public static void main(String[] args) {
orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
0.01).countingBits(8).buildCountingBloomFilter();
cbf.add("zhangsan");
cbf.add("lisi");
cbf.add("wangwu");
System.out.println("是否存在王五：" + cbf.contains("wangwu")); //true
cbf.remove("wangwu");
System.out.println("是否存在王五：" + cbf.contains("wangwu")); //false
}
}
構建布隆過濾器前面 2 個引數一個就是期望的元素數，一個就是 fpp 值，后面的 countingBits 引數就是計數器占用的大小，這里傳了一個 8 位，即最多允許 255 次重復，如果不傳的話這里默認是 16 位大小，即允許 65535次重復，
建議使用Guava自帶的布隆過濾器，直接傳入預期的資料量以及fpp，它會自動幫我們計算陣列長度和哈希次數
布隆過濾器應該設計為多大？
假設在布隆過濾器里面有 k 個哈希函式，m 個位元位（也就是位陣列長度），以及 n 個已插入元素，錯誤率會近似于 (1-ekn/m)k，所以你只需要先確定可能插入的資料集的容量大小 n，然后再調整 k 和 m 來為你的應用配置過濾器，
布隆過濾器應該使用多少個哈希函式？
對于給定的 m（位元位個數）和 n（集合元素個數），最優的 k（哈希函式個數）值為: (m/n)ln(2)
布隆過濾器的時間復雜度和空間復雜度?
對于一個 m（位元位個數）和 k（哈希函式個數）值確定的布隆過濾器，添加和判斷操作的時間復雜度都是 O(k)，這意味著每次你想要插入一個元素或者查詢一個元素是否在集合中，只需要使用 k 個哈希函式對該元素求值，然后將對應的位元位標記或者檢查對應的位元位即可，
Guava的布隆過濾器的實作
Guava有自帶的布隆過濾器的實作
public class BloomFilterTest {
public static void main(String[] args) {
long star = System.currentTimeMillis();
BloomFilter<Integer> filter = BloomFilter.create(
Funnels.integerFunnel(),
//預計存放多少資料
10000000,
//可以接受的誤報率
0.01);
for (int i = 0; i < 10000000; i++) {
filter.put(i);
}
Assert.isTrue(filter.mightContain(1),"不存在");
Assert.isTrue(filter.mightContain(2),"不存在");
Assert.isTrue(filter.mightContain(3),"不存在");
Assert.isTrue(filter.mightContain(10000000),"不存在");
long end = System.currentTimeMillis();
System.out.println("執行時間：" + (end - star));
}
}
BitMap
BitMap不會存在誤判的情況，位圖也是布隆過濾器的實作，但是占用記憶體空間隨集合內最大元素的增大而增大，而布隆過濾器，因為其可能一個bit為多個元素作標識，這就保證了它的空間利用率，這2種方式根據業務進行選擇，
以32位整型為例，它可以表示數字的個數為2^32. 可以申請一個位圖，讓每個整數對應的位圖中的一個bit，這樣2^32個數需要的位圖的大小為512MB，具體實作的思路為：申請一個512MB的位圖，并把所有的位都初始化為0；接著遍歷所有的整數，對遍歷到的數字，把相應的位置上的bit設定為1.最后判斷待查找的數對應的位圖上的值是多少，如果是0，那么表示這個數字不存在，如果是1，那么表示這個數字存在，
Java中有BitMap的實作類，BitSet
public class BitMapTest {
public static void main(String[] args) {
int[] array = {3, 8, 5, 7, 1};
BitSet bitSet = new BitSet(5);
for (int i = 0; i < array.length; i++) {
bitSet.set(array, true);
}
bitSet.stream().forEach(e -> System.out.println(e));
}
}
本篇文章就到這里，感謝閱讀，如果本篇博客有任何錯誤和建議，歡迎給我留言指正，文章持續更新，可以關注公眾號第一時間閱讀，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/547755.html
標籤：Java