用Java實現(xiàn)一個簡單的布隆過濾器

更新時間：2023年12月28日 10:13:34 作者：一個風輕云淡

這篇文章主要介紹了用Java實現(xiàn)一個簡單的布隆過濾器,布隆過濾器是1970年由布隆提出的,它實際上是一個很長的二進制向量和一系列隨機映射函數(shù),布隆過濾器可以用于檢索一個元素是否在一個集合中,需要的朋友可以參考下

設計初衷

在實際開發(fā)中，會遇到很多要判斷一個元素是否在某個集合中的業(yè)務場景，類似于垃圾郵件的識別，惡意ip地址的訪問，緩存穿透等情況。類似于緩存穿透這種情況，有許多的解決方法，如：redis存儲null值等，而對于垃圾郵件的識別，惡意ip地址的訪問，我們也可以直接用 HashMap 去存儲惡意ip地址以及垃圾郵件，然后每次訪問時去檢索一下對應集合中是否有相同數(shù)據(jù)。

但是對于大數(shù)據(jù)量的項目，如，垃圾郵件出現(xiàn)有十幾二十萬，惡意ip地址出現(xiàn)有上百萬，或者從幾十億電話中檢索出指定的電話是否在等操作，那么這十幾億的數(shù)據(jù)就會占據(jù)大幾G的空間，這個時候就可以考慮一下布隆過濾器了。

?網(wǎng)頁URL的去重，垃圾郵件的判別，集合重復元素的判別，查詢加速（比如基于key-value的存儲系統(tǒng)）、數(shù)據(jù)庫防止查詢擊穿，使用BloomFilter來減少不存在的行或列的磁盤查找

布隆過濾器定義

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。

由一個初始值為零的bit數(shù)組和多個哈希函數(shù)構成，用來快速判斷集合中是否存在某個元素。

布隆過濾器可以用于查詢一個元素是否存在于一個集合當中，查詢結果為以下二者之一：

這個元素可能存在于這個集合當中。
這個元素一定不存在于這個集合當中。

進行數(shù)據(jù)插入時：使用多個hash函數(shù)對key進行hash運算得到多個整數(shù)索引值，對位數(shù)組長度進行取模運算得到多個位置，每個hash函數(shù)都會得到一個不同的位置，將這幾個位置都置1就完成了add操作。

進行數(shù)據(jù)查詢時：將這個key的多個位置上的值取出來，只要有其中一位是零就表示這個key不存在，但如果都是1，則不一定存在對應的key。（也就是有，不一定有，無，就一定無）

java實現(xiàn)

基于上面理解介紹，我們現(xiàn)在基于java手擼一個簡單布隆過濾器

bitSize：位圖的大小，即位圖中的位數(shù)。
bits：位圖對象，用于存儲元素的映射結果。
seeds：用于哈希函數(shù)的種子數(shù)組。
hashIterations：哈希函數(shù)的迭代次數(shù)。

class BloomFilter {
    private int bitSize;
    private BitSet bits;
    private int[] seeds;
    private int hashIterations;
    /**
     * @param size          預計元素數(shù)量
     * @param falsePositive 期望誤判率
     */
    public BloomFilter(int size, double falsePositive) {
        this.bitSize = (int) Math.ceil((size * Math.log(falsePositive)) / Math.log(1.0 / (Math.pow(2.0, Math.log(2.0)))));
        this.bits = new BitSet(bitSize);
        this.hashIterations = (int) Math.round(Math.log(2.0) * bitSize / size);
        this.seeds = new int[hashIterations];
        for (int i = 0; i < hashIterations; i++) {
            seeds[i] = i + 1;
        }
    }
    /**
     * 添加一個元素
     *
     * @param element 元素
     */
    public void add(String element) {
        for (int seed : seeds) {
            int hash = MurmurHash.hash(element.getBytes(), seed);
            bits.set(Math.abs(hash % bitSize), true);
        }
    }
    /**
     * 判斷一個元素是否存在
     *
     * @param element 元素
     * @return 是否存在
     */
    public boolean contains(String element) {
        for (int seed : seeds) {
            int hash = MurmurHash.hash(element.getBytes(), seed);
            if (!bits.get(Math.abs(hash % bitSize))) {
                return false;
            }
        }
        return true;
    }
    /**
     * MurmurHash算法
     */
    static class MurmurHash {
        public static int hash(byte[] data, int seed) {
            int m = 0x5bd1e995;
            int r = 24;
            int h = seed ^ data.length;
            int len = data.length;
            int pos = 0;
            while (len >= 4) {
                int k = data[pos] & 0xff;
                k |= (data[pos + 1] & 0xff) << 8;
                k |= (data[pos + 2] & 0xff) << 16;
                k |= (data[pos + 3] & 0xff) << 24;
                k *= m;
                k ^= k >>> r;
                k *= m;
                h *= m;
                h ^= k;
                pos += 4;
                len -= 4;
            }
            switch (len) {
                case 3:
                    h ^= (data[pos + 2] & 0xff) << 16;
                case 2:
                    h ^= (data[pos + 1] & 0xff) << 8;
                case 1:
                    h ^= data[pos] & 0xff;
                    h *= m;
            }
            h ^= h >>> 13;
            h *= m;
            h ^= h >>> 15;
            return h;
        }
    }
}

BloomFilter 類表示布隆過濾器，提供了 add 和 contains 方法用于添加元素和判斷元素是否存在。

在構造函數(shù)中，根據(jù)預計元素數(shù)量和期望誤判率計算出位數(shù)組的大小、哈希函數(shù)個數(shù)和哈希種子。

添加元素時，使用多個哈希函數(shù)對元素進行哈希，并將對應的位設置為 1；判斷元素是否存在時，同樣使用多個哈希函數(shù)對元素進行哈希，并檢查對應的位是否都為 1。

注意，上述代碼中的哈希函數(shù)使用了 MurmurHash 算法，該算法的性能比較高，適合用于布隆過濾器中。同時，布隆過濾器的誤判率隨著元素數(shù)量的增加而增加，因此在實際使用中需要根據(jù)誤判率和元素數(shù)量的情況來選擇合適的參數(shù)。

測試

public class test {
    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(1000,0.01);
        bloomFilter.add("xyz");
        boolean xyz = bloomFilter.contains("xyz");
        System.out.println("xyz查詢結果："+xyz);
        boolean xyzk = bloomFilter.contains("xyzk");
        System.out.println("xyz查詢結果："+xyzk);
    }
}

測試結果：