布隆過濾器是否好用，得看哈希函數寫成啥樣

作者：小傅哥

沉澱、分享、成長，讓自己和他人都能有所收獲！😄

一、前言

​

​布隆過濾器的曆史​

​

布隆過濾器由 Burton Howard Bloom 于 1970 年提出，它是一種節省空間的機率資料結構，包括一個很長的二進制向量和一些列随機映射函數。

二、布隆過濾器結構

布隆過濾器是一個基于數組和哈希函數散列元素的結構，很像HashMap的哈希桶。布隆過濾器可以用于檢測一個元素是否在集合中。它的優點是空間效率和查詢時間比一般算法要好很多，但也有一定機率的誤判性。如HashMap出現哈希碰撞💥

• 趙敏：無忌，成昆上了光明頂！
• 張無忌：咱們過濾器年久失修，已經不準了！
• 張無忌：布隆過濾器的長度太小，哈希計算單一。導緻謝飛機、拎瓢沖、成昆，三個人的哈希值都是相同的，是以沒法判斷成昆是否上了光明頂。咱們隻能快些上山了，沿途小心。
• 楊左使：老大，我現在就去維修一下。布隆過濾器的優化方式可以通過增加長度和多樣新計算哈希解決。

三、布隆過濾器實作

布隆過濾器的實作條件包括可以存放二進制元素的 BitSet 以及多樣性的哈希計算函數。

public class BloomFilter {

    private static final HashGenerator.HashGroup[] GROUPS = new HashGenerator.HashGroup[]{HashGenerator.HashGroup.G1, HashGenerator.HashGroup.G2, HashGenerator.HashGroup.G3, HashGenerator.HashGroup.G4};

    private final BitSet bits;
  
    private HashGenerator[] generators;

}      

所有的元素存放都經過多樣的哈希計算存放到 BitSet 中，這樣可以盡可能的分散元素，減少誤判性。

• 源碼位址：​​https://github.com/fuzhengwei/java-algorithms​​
• 本章源碼：​​https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/bloom_filter​​

1. 哈希函數

private int hashG1(String value) {
    int hash = 0;
    for (int idx = 0; idx < value.length(); idx++) {
        char c = value.charAt(idx);
        hash = (hash << 5) + hash + c;
        hash &= hash;
        hash = Math.abs(hash);
    }
    return hash % (seed * size - 1);
}

private int hashG2(String value) {
    int hash = 7397;
    for (int idx = 0; idx < value.length(); idx++) {
        char c = value.charAt(idx);
        hash = (hash << 5) + hash + c;
    }
    return Math.abs(hash % seed * (size - 1));
}

private int hashG3(String value) {
    int hash = 0;
    for (int idx = 0; idx < value.length(); idx++) {
        char c = value.charAt(idx);
        hash = (hash << 5) + hash + c;
        hash += c;
        hash &= hash;
    }
    return Math.abs(hash % (seed * size - 1));
}

private int hashG4(String value) {
    int h;
    return (value == null) ? 0 : Math.abs(seed * (size - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
}      

• 這裡提供了四種哈希計算的方式，相當于每一個哈希計算都是一次擾動處理。一個元素的存放可以經過四次哈希，盡量讓元素值做到散列。

2. 建構容器

public BloomFilter(int size, int[] seeds) {
    bits = new BitSet(size);
    generators = new HashGenerator[seeds.length];
    for (int i = 0; i < seeds.length; i++) {
        generators[i] = new HashGenerator(size, seeds[i], GROUPS[i % GROUPS.length]);
    }
}      

• 構造函數根據所需建立的容器大小和哈希種子來初始化布隆過濾器。

3. 添加元素

public void add(String value) {
    for (HashGenerator generator : generators) {
        int hash = generator.doHash(value);
        bits.set(hash, true);
    }
}      

• 添加元素時按照元素初始化時的哈希計算種類，擷取哈希并存放。

4. 比對元素

public boolean contains(String value) {
    boolean ret = true;
    for (HashGenerator generator : generators) {
        ret = ret && bits.get(generator.doHash(value));
    }
    return ret;
}      

• 比對元素時用的是同一類哈希計算方式，并且把這些哈希值​

  ​&&​

  ​ 計算。用N個比特位置記錄一個值更準确

四、布隆過濾器測試

@Test
public void test() {
    String val00 = "小傅哥";
    String val01 = "https://bugstack.cn";
    String val02 = "https://github.com/fuzhengwei/CodeGuide";
    String val03 = "https://github.com/fuzhengwei";
    BloomFilter filter = new BloomFilter(Integer.MAX_VALUE, new int[]{7, 19, 43, 77});
    filter.add(val00);
    filter.add(val01);
    filter.add(val02);
    logger.info("測試結果 val00：{} 布隆過濾器：{}", val00, filter.contains(val00));
    logger.info("測試結果 val01：{} 布隆過濾器：{}", val01, filter.contains(val01));
    logger.info("測試結果 val02：{} 布隆過濾器：{}", val02, filter.contains(val02));
    logger.info("測試結果 val02：{} 布隆過濾器：{}", val03, filter.contains(val03));
}      

• 可以看到這裡初始化了一個比較大的布隆過濾器，并且提供了4個随機種子；​

  ​7, 19, 43, 77​

  ​計算哈希值。

21:33:22.790 [main] INFO bloom_filter.__test__.BloomFilterTest - 測試結果 val00：小傅哥 布隆過濾器：true
21:33:22.794 [main] INFO bloom_filter.__test__.BloomFilterTest - 測試結果 val01：https://bugstack.cn 布隆過濾器：true
21:33:22.794 [main] INFO bloom_filter.__test__.BloomFilterTest - 測試結果 val02：https://github.com/fuzhengwei/CodeGuide 布隆過濾器：true
21:33:22.795 [main] INFO bloom_filter.__test__.BloomFilterTest - 測試結果 val02：https://github.com/fuzhengwei 布隆過濾器：false


Process finished with exit code 0      

• 通過測試可以看到，存放的val00、val01、val02 分别可以驗證出 true 沒有存放的 val03 驗證為fasle

五、常見面試題

• 布隆過濾器的使用場景？
• 布隆過濾器的實作原理和方式？
• 如何提高布隆過濾器的準确性？
• 有哪些中哈希計算方式？
• 都有哪些類型的布隆過濾器實作？Google 開源的 Guava 中自帶的布隆過濾器、Redis 中的布隆過濾器(​​https://github.com/RedisBloom/RedisBloom​​)