如何判斷一個元素在億級數(shù)據(jù)中是否存在？
最近有朋友問我這么一個面試題目：現(xiàn)在有一個非常龐大的數(shù)據(jù)，假設(shè)全是 int 類型?，F(xiàn)在我給你一個數(shù)，你需要告訴我它是否存在其中(盡量高效)。
需求其實很清晰，只是要判斷一個數(shù)據(jù)是否存在即可。但這里有一個比較重要的前提：非常龐大的數(shù)據(jù)。
常規(guī)實現(xiàn)
先不考慮這個條件，我們腦海中出現(xiàn)的***種方案是什么?我想大多數(shù)想到的都是用 HashMap 來存放數(shù)據(jù)，因為它的寫入查詢的效率都比較高。
寫入和判斷元素是否存在都有對應(yīng)的 API，所以實現(xiàn)起來也比較簡單。為此我寫了一個單測，利用 HashSet 來存數(shù)據(jù)(底層也是 HashMap );同時為了后面的對比將堆內(nèi)存寫死：
- -Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError
為了方便調(diào)試加入了 GC 日志的打印，以及內(nèi)存溢出后 Dump 內(nèi)存：
- @Test
- public void hashMapTest(){
- long star = System.currentTimeMillis();
- Set<Integer> hashset = new HashSet<>(100) ;
- for (int i = 0; i < 100; i++) {
- hashset.add(i) ;
- }
- Assert.assertTrue(hashset.contains(1));
- Assert.assertTrue(hashset.contains(2));
- Assert.assertTrue(hashset.contains(3));
- long end = System.currentTimeMillis();
- System.out.println("執(zhí)行時間：" + (end - star));
- }
當(dāng)我只寫入 100 條數(shù)據(jù)時自然是沒有問題的。還是在這個基礎(chǔ)上，寫入 1000W 數(shù)據(jù)試試：
執(zhí)行后馬上就內(nèi)存溢出：
可見在內(nèi)存有限的情況下我們不能使用這種方式。實際情況也是如此;既然要判斷一個數(shù)據(jù)是否存在于集合中，考慮的算法的效率以及準(zhǔn)確性肯定是要把數(shù)據(jù)全部 load 到內(nèi)存中的。
Bloom Filter
基于上面分析的條件，要實現(xiàn)這個需求最需要解決的是如何將龐大的數(shù)據(jù) load 到內(nèi)存中。
而我們是否可以換種思路，因為只是需要判斷數(shù)據(jù)是否存在，也不是需要把數(shù)據(jù)查詢出來，所以完全沒有必要將真正的數(shù)據(jù)存放進(jìn)去。
偉大的科學(xué)家們已經(jīng)幫我們想到了這樣的需求。Burton Howard Bloom 在 1970 年提出了一個叫做 Bloom Filter(中文翻譯：布隆過濾)的算法。
它主要用于解決判斷一個元素是否在一個集合中，但它的優(yōu)勢是只需要占用很小的內(nèi)存空間以及有著高效的查詢效率。所以在這個場景下再合適不過了。
Bloom Filter 原理
下面來分析下它的實現(xiàn)原理。官方的說法是：它是一個保存了很長的二級制向量，同時結(jié)合 Hash 函數(shù)實現(xiàn)的。
聽起來比較繞，但是通過一個圖就比較容易理解了：
如上圖所示：
- 首先需要初始化一個二進(jìn)制的數(shù)組，長度設(shè)為 L(圖中為 8)，同時初始值全為 0 。
- 當(dāng)寫入一個 A1=1000 的數(shù)據(jù)時，需要進(jìn)行 H 次 Hash 函數(shù)的運算(這里為 2 次);與 HashMap 有點類似，通過算出的 HashCode 與 L 取模后定位到 0、2 處，將該處的值設(shè)為 1。
- A2=2000 也是同理計算后將 4、7 位置設(shè)為 1。
- 當(dāng)有一個 B1=1000 需要判斷是否存在時，也是做兩次 Hash 運算，定位到 0、2 處，此時他們的值都為 1 ，所以認(rèn)為 B1=1000 存在于集合中。
- 當(dāng)有一個 B2=3000 時，也是同理。***次 Hash 定位到 index=4 時，數(shù)組中的值為 1，所以再進(jìn)行第二次 Hash 運算，結(jié)果定位到 index=5 的值為 0，所以認(rèn)為 B2=3000 不存在于集合中。
整個的寫入、查詢的流程就是這樣，匯總起來就是：對寫入的數(shù)據(jù)做 H 次 Hash 運算定位到數(shù)組中的位置，同時將數(shù)據(jù)改為 1 。
當(dāng)有數(shù)據(jù)查詢時也是同樣的方式定位到數(shù)組中。一旦其中的有一位為 0 則認(rèn)為數(shù)據(jù)肯定不存在于集合，否則數(shù)據(jù)可能存在于集合中。
所以布隆過濾有以下幾個特點：
- 只要返回數(shù)據(jù)不存在，則肯定不存在。
- 返回數(shù)據(jù)存在，但只能是大概率存在。
- 同時不能清除其中的數(shù)據(jù)。
***點應(yīng)該都能理解，重點解釋下 2、3 點。為什么返回存在的數(shù)據(jù)卻是可能存在呢，這其實也和 HashMap 類似。
在有限的數(shù)組長度中存放大量的數(shù)據(jù)，即便是再***的 Hash 算法也會有沖突，所以有可能兩個完全不同的 A、B 兩個數(shù)據(jù)***定位到的位置是一模一樣的。
這時拿 B 進(jìn)行查詢時那自然就是誤報了。刪除數(shù)據(jù)也是同理，當(dāng)我把 B 的數(shù)據(jù)刪除時，其實也相當(dāng)于是把 A 的數(shù)據(jù)刪掉了，這樣也會造成后續(xù)的誤報。
基于以上的 Hash 沖突的前提，所以 Bloom Filter 有一定的誤報率，這個誤報率和 Hash 算法的次數(shù) H，以及數(shù)組長度 L 都是有關(guān)的。
自己實現(xiàn)一個布隆過濾
算法其實很簡單不難理解，于是利用 Java 實現(xiàn)了一個簡單的雛形：
- 首先初始化了一個 int 數(shù)組。
- 寫入數(shù)據(jù)的時候進(jìn)行三次 Hash 運算，同時把對應(yīng)的位置置為 1。
- 查詢時同樣的三次 Hash 運算，取到對應(yīng)的值，一旦值為 0 ，則認(rèn)為數(shù)據(jù)不存在。
代碼如下：
- public class BloomFilters {
- /**
- * 數(shù)組長度
- */
- private int arraySize;
- /**
- * 數(shù)組
- */
- private int[] array;
- public BloomFilters(int arraySize) {
- this.arraySize = arraySize;
- array = new int[arraySize];
- }
- /**
- * 寫入數(shù)據(jù)
- * @param key
- */
- public void add(String key) {
- int first = hashcode_1(key);
- int second = hashcode_2(key);
- int third = hashcode_3(key);
- array[first % arraySize] = 1;
- array[second % arraySize] = 1;
- array[third % arraySize] = 1;
- }
- /**
- * 判斷數(shù)據(jù)是否存在
- * @param key
- * @return
- */
- public boolean check(String key) {
- int first = hashcode_1(key);
- int second = hashcode_2(key);
- int third = hashcode_3(key);
- int firstIndex = array[first % arraySize];
- if (firstIndex == 0) {
- return false;
- }
- int secondIndex = array[second % arraySize];
- if (secondIndex == 0) {
- return false;
- }
- int thirdIndex = array[third % arraySize];
- if (thirdIndex == 0) {
- return false;
- }
- return true;
- }
- /**
- * hash 算法1
- * @param key
- * @return
- */
- private int hashcode_1(String key) {
- int hash = 0;
- int i;
- for (i = 0; i < key.length(); ++i) {
- hash = 33 * hash + key.charAt(i);
- }
- return Math.abs(hash);
- }
- /**
- * hash 算法2
- * @param data
- * @return
- */
- private int hashcode_2(String data) {
- final int p = 16777619;
- int hash = (int) 2166136261L;
- for (int i = 0; i < data.length(); i++) {
- hash = (hash ^ data.charAt(i)) * p;
- }
- hash += hash << 13;
- hash ^= hash >> 7;
- hash += hash << 3;
- hash ^= hash >> 17;
- hash += hash << 5;
- return Math.abs(hash);
- }
- /**
- * hash 算法3
- * @param key
- * @return
- */
- private int hashcode_3(String key) {
- int hash, i;
- for (hash = 0, i = 0; i < key.length(); ++i) {
- hash += key.charAt(i);
- hash += (hash << 10);
- hash ^= (hash >> 6);
- }
- hash += (hash << 3);
- hash ^= (hash >> 11);
- hash += (hash << 15);
- return Math.abs(hash);
- }
- }
實現(xiàn)邏輯其實就和上文描述的一樣。下面來測試一下，同樣的參數(shù)：
- -Xms64m -Xmx64m -XX:+PrintHeapAtGC
- @Test
- public void bloomFilterTest(){
- long star = System.currentTimeMillis();
- BloomFilters bloomFilters = new BloomFilters(10000000) ;
- for (int i = 0; i < 10000000; i++) {
- bloomFilters.add(i + "") ;
- }
- Assert.assertTrue(bloomFilters.check(1+""));
- Assert.assertTrue(bloomFilters.check(2+""));
- Assert.assertTrue(bloomFilters.check(3+""));
- Assert.assertTrue(bloomFilters.check(999999+""));
- Assert.assertFalse(bloomFilters.check(400230340+""));
- long end = System.currentTimeMillis();
- System.out.println("執(zhí)行時間：" + (end - star));
- }
執(zhí)行結(jié)果如下：
只花了 3 秒鐘就寫入了 1000W 的數(shù)據(jù)同時做出來準(zhǔn)確的判斷。
當(dāng)讓我把數(shù)組長度縮小到了 100W 時就出現(xiàn)了一個誤報，400230340 這個數(shù)明明沒在集合里，卻返回了存在。
這也體現(xiàn)了 Bloom Filter 的誤報率。我們提高數(shù)組長度以及 Hash 計算次數(shù)可以降低誤報率，但相應(yīng)的 CPU、內(nèi)存的消耗就會提高;這就需要根據(jù)業(yè)務(wù)需要自行權(quán)衡。
Guava 實現(xiàn)
剛才的方式雖然實現(xiàn)了功能，也滿足了大量數(shù)據(jù)。但觀察 GC 日志非常頻繁，同時老年代也使用了 90%，接近崩潰的邊緣。
總的來說就是內(nèi)存利用率做的不好。其實 Google Guava 庫中也實現(xiàn)了該算法，下面來看看業(yè)界權(quán)威的實現(xiàn)：
- -Xms64m -Xmx64m -XX:+PrintHeapAtGC
- @Test
- public void guavaTest() {
- 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.assertTrue(filter.mightContain(1));
- Assert.assertTrue(filter.mightContain(2));
- Assert.assertTrue(filter.mightContain(3));
- Assert.assertFalse(filter.mightContain(10000000));
- long end = System.currentTimeMillis();
- System.out.println("執(zhí)行時間：" + (end - star));
- }
也是同樣寫入了 1000W 的數(shù)據(jù)，執(zhí)行沒有問題。
觀察 GC 日志會發(fā)現(xiàn)沒有一次 fullGC，同時老年代的使用率很低。和剛才的一對比這里明顯的要好上很多，也可以寫入更多的數(shù)據(jù)。
那就來看看 Guava 它是如何實現(xiàn)的?構(gòu)造方法中有兩個比較重要的參數(shù)，一個是預(yù)計存放多少數(shù)據(jù)，一個是可以接受的誤報率。 我這里的測試 demo 分別是 1000W 以及 0.01。
Guava 會通過你預(yù)計的數(shù)量以及誤報率幫你計算出你應(yīng)當(dāng)會使用的數(shù)組大小 numBits 以及需要計算幾次 Hash 函數(shù) numHashFunctions 。這個算法計算規(guī)則可以參考維基百科。
put 寫入函數(shù)
真正存放數(shù)據(jù)的 put 函數(shù)如下：
- 根據(jù) murmur3_128 方法的到一個 128 位長度的 byte[]。
- 分別取高低 8 位的到兩個 Hash 值。
- 再根據(jù)初始化時的到的執(zhí)行 Hash 的次數(shù)進(jìn)行 Hash 運算。
- bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
其實也是 Hash 取模拿到 index 后去賦值 1，重點是 bits.set() 方法。
set 方法是 BitArray 中的一個函數(shù)，BitArray 就是真正存放數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu)，利用了一個 long[]data 來存放數(shù)據(jù)。
所以 set() 時候也是對這個 data 做處理：
- 在 set 之前先通過 get() 判斷這個數(shù)據(jù)是否存在于集合中，如果已經(jīng)存在則直接返回告知客戶端寫入失敗。
- 接下來就是通過位運算進(jìn)行位或賦值。
- get() 方法的計算邏輯和 set 類似，只要判斷為 0 就直接返回存在該值。
mightContain 是否存在函數(shù)
前面幾步的邏輯都是類似的，只是調(diào)用了剛才的 get() 方法判斷元素是否存在而已。
總結(jié)
布隆過濾的應(yīng)用還是蠻多的，比如數(shù)據(jù)庫、爬蟲、防緩存擊穿等。特別是需要精確知道某個數(shù)據(jù)不存在時做點什么事情就非常適合布隆過濾。
本示例代碼參考這里：https://github.com/crossoverJie/JCSprout
