Java怎么實現(xiàn)布隆過濾器

這篇“Java怎么實現(xiàn)布隆過濾器”文章的知識點大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java怎么實現(xiàn)布隆過濾器”文章吧。

什么是布隆過濾器

布隆過濾器（Bloom Filter）是1970年由布隆提出來的。 它實際上是由一個很長的二進制數(shù)組+一系列hash算法映射函數(shù)，用于判斷一個元素是否存在于集合中。
布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。

場景

假設有10億條手機號，然后判斷某條手機號是否在列表內(nèi)？

mysql可以嗎？

正常情況下，如果數(shù)據(jù)量不大，我們可以考慮使用mysql存儲。將所有數(shù)據(jù)存儲到數(shù)據(jù)庫，然后每次去庫里查詢判斷是否存在。但是如果數(shù)據(jù)量太大，超過千萬，mysql查詢效率是很低的，特別消耗性能。

HashSet可以嗎？

我們可以把數(shù)據(jù)放入HashSet中，利用HashSet天然的去重性，查詢只需要調(diào)用contains方法即可，但是hashset是存放在內(nèi)存中的，數(shù)據(jù)量過大內(nèi)存直接oom了。

布隆過濾器特點

• 插入和查詢效率高，占用空間少，但是返回的結(jié)果是不確定的。

• 一個元素如果判斷為存在的時候，它不一定真的存在。但是如果判斷一個元素不存在，那么它一定是不存在的。

• 布隆過濾器可以添加元素，但是一定不能刪除元素，會導致誤判率增加。

布隆過濾器原理

布隆過濾器其實就是是一個BIT數(shù)組，通過一系列hash算法映射出對應的hash,然后將hash對應的數(shù)組下標位置改為1。查詢時就是對數(shù)據(jù)在進行一系列hash算法得到下標，從BIT數(shù)組里取數(shù)據(jù)如如果是1 則說明數(shù)據(jù)有可能存在，如果是0 說明一定不存在

為什么會有誤差率

我們知道布隆過濾器其實是對數(shù)據(jù)做hash,那么不管用什么算法，都有可能兩條不同的數(shù)據(jù)生成的hash確是相同的，也就是我們常說的hash沖突。

首先插入一條數(shù)據(jù)： 好好學技術(shù)

在插入一條數(shù)據(jù)：

這是如果查詢一條數(shù)據(jù)，假設他的hash下標已經(jīng)標為1了，那么布隆過濾器就會認為他存在

常見使用場景

緩存穿透

java實現(xiàn)布隆過濾器

package com.fandf.test.redis;

import java.util.BitSet;

/**
 * java布隆過濾器
 *
 * @author fandongfeng
 */
public class MyBloomFilter {

    /**
     * 位數(shù)組大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;

    /**
     * 通過這個數(shù)組創(chuàng)建多個Hash函數(shù)
     */
    private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};

    /**
     * 初始化位數(shù)組，數(shù)組中的元素只能是 0 或者 1
     */
    private final BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * Hash函數(shù)數(shù)組
     */
    private final MyHash[] myHashes = new MyHash[SEEDS.length];

    /**
     * 初始化多個包含 Hash 函數(shù)的類數(shù)組，每個類中的 Hash 函數(shù)都不一樣
     */
    public MyBloomFilter() {
        // 初始化多個不同的 Hash 函數(shù)
        for (int i = 0; i < SEEDS.length; i++) {
            myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位數(shù)組
     */
    public void add(Object value) {
        for (MyHash myHash : myHashes) {
            bits.set(myHash.hash(value), true);
        }
    }

    /**
     * 判斷指定元素是否存在于位數(shù)組
     */
    public boolean contains(Object value) {
        boolean result = true;
        for (MyHash myHash : myHashes) {
            result = result && bits.get(myHash.hash(value));
        }
        return result;
    }

    /**
     * 自定義 Hash 函數(shù)
     */
    private class MyHash {
        private int cap;
        private int seed;

        MyHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 計算 Hash 值
         */
        int hash(Object obj) {
            return (obj == null) ? 0 : Math.abs(seed * (cap - 1) & (obj.hashCode() ^ (obj.hashCode() >>> 16)));
        }
    }

    public static void main(String[] args) {
        String str = "好好學技術(shù)";
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        System.out.println("str是否存在：" + myBloomFilter.contains(str));
        myBloomFilter.add(str);
        System.out.println("str是否存在：" + myBloomFilter.contains(str));
    }


}

Guava實現(xiàn)布隆過濾器

引入依賴

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

package com.fandf.test.redis;

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * @author fandongfeng
 */
public class GuavaBloomFilter {

    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
        bloomFilter.put("好好學技術(shù)");
        System.out.println(bloomFilter.mightContain("不好好學技術(shù)"));
        System.out.println(bloomFilter.mightContain("好好學技術(shù)"));
    }
}

hutool實現(xiàn)布隆過濾器

引入依賴

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.8.3</version>
</dependency>

package com.fandf.test.redis;

import cn.hutool.bloomfilter.BitMapBloomFilter;
import cn.hutool.bloomfilter.BloomFilterUtil;

/**
 * @author fandongfeng
 */
public class HutoolBloomFilter {
    public static void main(String[] args) {
        BitMapBloomFilter bloomFilter = BloomFilterUtil.createBitMap(1000);
        bloomFilter.add("好好學技術(shù)");
        System.out.println(bloomFilter.contains("不好好學技術(shù)"));
        System.out.println(bloomFilter.contains("好好學技術(shù)"));
    }

}

Redisson實現(xiàn)布隆過濾器

引入依賴

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.20.0</version>
</dependency>

package com.fandf.test.redis;
 
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
 
/**
 * Redisson 實現(xiàn)布隆過濾器
 * @author fandongfeng
 */
public class RedissonBloomFilter {
 
    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        //構(gòu)造Redisson
        RedissonClient redisson = Redisson.create(config);
 
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("name");
        //初始化布隆過濾器：預計元素為100000000L,誤差率為1%
        bloomFilter.tryInit(100000000L,0.01);
        bloomFilter.add("好好學技術(shù)");
 
        System.out.println(bloomFilter.contains("不好好學技術(shù)"));
        System.out.println(bloomFilter.contains("好好學技術(shù)"));
    }
}

以上就是關(guān)于“Java怎么實現(xiàn)布隆過濾器”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。