java怎麼快速判斷元素是否在集合裡

1、什麼叫布隆過濾器

布隆過濾器（Bloom Filter）是一個叫做 Bloom 的老哥於1970年提出的。

實際上可以把它看作由二進位向量（或說位數組）和一系列隨機映射函數（雜湊函數）兩部分組成的資料結構。

它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率和刪除困難。

2、實作原理

先來一張圖片

 布隆過濾器演算法主要想法就是利用n 個雜湊函數進行hash 過後，得到不同的雜湊值，根據hash 映射到數組（這個數組的長度可能會很長很長）的不同的索引位置上，然後將相應的索引位上的值設定為1。

判斷該元素是否出現在集合中，就是利用k個不同的雜湊函數計算雜湊值，看雜湊值對應對應索引位置上面的值是否是1，如果有1個不是1 ，說明該元素不存在在集合中。

但是也有可能判斷元素在集合中，但是元素不在，這個元素所有索引位置上面的1都是別的元素設定的，這就導致一定的誤判幾率（這就是為什麼上面是活可能在一個集合中的根本原因，因為會存在一定的hash 衝突）。

注意：誤判率越低，對應的表現就會越低。

3、作用

布隆過濾器是可以用來判斷一個元素是不是（可能）在一個集合裡，並且相比於其它的資料結構，布隆過濾器在空間和時間方面都有巨大的優勢。

注意上面的一個字：可能。這裡先預留一個懸念，下文會詳細分析到。

判斷給定資料是否存在

防止快取穿透（判斷請求的資料是否有效避免直接繞過快取請求資料庫）等等、郵箱的垃圾郵件過濾、黑名單功能等等。

4、具體實作

看完了布隆過濾器的演算法思想，那就開始具體的實現的講解。

我先來舉個例子，假設有旺財和小強兩個字串，他們分別經過三次的hash 演算法，然後根據hash 的結果將對應的數組（假設數組長度為16）的索引位置的值置為1，先來看下旺財這個詞組:

#旺財經過三次hash 過後，值分別為2,4,6 那麼根據可以得到索引值分別為2、4、6，於是就將該數組的索引（2、4、6）位置的值置為1，其餘當做是0，現在假設需要查找旺財，同樣經過這個三個hash 然後發現所得到的索引2、4、6對應的位置的值都為1，那麼可以判斷旺財可能是存在的。

接著有將小強插入布隆過濾器中，實際的過程和上面的一樣，假設得到的下標是1、3、5

拋開旺財的存在，小強此時是這樣子在布隆過濾器中的，結合旺財和小強實際的數組是這樣子的：

# # 現在有來一個資料：9527，現在要求是判斷9527 是否存在，假設9527 經過三次hash 過後得到的下標分別為：5、6、7。結果發現下標為 7 的位置的值為0，那麼可以肯定的判斷出，9527 一定不存在。

接著又來了一個 國產007，經過三次hash 過後得到的下標分別為：2、3、5，結果發現2、3、5下標對應的值全是1，於是可以大致判斷 國產007可能存在。但實際上經過我們剛剛的演示，國產007 根本就不存在，之所以 2、3、5 索引位置的值為1 ，那是因為其他的數據設置的。

說到這裡，我不知道大家有沒有明白布隆過濾器的作用。

5、程式碼的實作

作為java 程式設計師，我們真的很幸福了，我們使用到很多的框架和工具，基本上都被封裝好了，布隆過濾器，我們就使用google 封裝好的工具類別。當然還有其他方法，大家可以探索探索。

首先加入依賴

<!--布隆过滤依赖-->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>25.1-jre</version>
</dependency>

程式碼的實作

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
public class BloomFilterDemo {
        public static void main(String[] args) {
        /**
         * 创建一个插入对象为一亿，误报率为0.01%的布隆过滤器
         * 不存在一定不存在
         * 存在不一定存在
         * ----------------
         *  Funnel 对象：预估的元素个数，误判率
         *  mightContain ：方法判断元素是否存在
         */
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 100000000, 0.0001);
        bloomFilter.put("死");
        bloomFilter.put("磕");
        bloomFilter.put("Redis");
        System.out.println(bloomFilter.mightContain("Redis"));
        System.out.println(bloomFilter.mightContain("Java"));
    }
}

 具體的解釋已經寫在註解中了。到這裡相信大家一定明白了布隆過濾器和怎麼使用了。

6、實戰

我們來模擬這樣的場景：透過布隆過濾器來解決快取穿透。

首先你的知道什麼叫做快取穿透吧？

快取穿透是指使用者存取一個快取和資料庫中都沒有的數據，因為快取中不存在，所以就會去存取資料庫，如果並發很高。很容易會擊垮資料庫

那布隆過濾器是如何解決這個問題的呢？他

的原理是这样子的：将数据库中所有的查询条件，放入布隆过滤器中，当一个查询请求过来时，先经过布隆过滤器进行查，如果判断请求查询值存在，则继续查；如果判断请求查询不存在，直接丢弃。

其代码如下：

String get(String key) {
    String value = redis.get(key);     
    if (value  == null) {
        if(!bloomfilter.mightContain(key)){
            return null; 
        }else{
            value = db.get(key); 
            redis.set(key, value); 
        }    
    }
    return value；
}

以上是java怎麼快速判斷元素是否在集合裡的詳細內容。更多資訊請關注PHP中文網其他相關文章！