摘要：布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。舉個(gè)栗子，比如第一次將存入布隆過(guò)濾器，將數(shù)組的，位置置為了，只要下次再有存入布隆過(guò)濾器，發(fā)現(xiàn)已經(jīng)是全是了，所以可知該字符串已經(jīng)保存過(guò)。

????最近做爬蟲項(xiàng)目過(guò)濾重復(fù)的url的時(shí)候,了解到一個(gè)東西,叫布隆過(guò)濾器,然后也學(xué)習(xí)了一下,寫下這篇博客記錄一下.
下面我們將分為幾個(gè)專題來(lái)介紹布隆過(guò)濾器:
1.什么是布隆過(guò)濾器;
2.布隆過(guò)濾器的使用場(chǎng)景和缺陷;
3.布隆過(guò)濾器java實(shí)現(xiàn);
4.guava中使用布隆過(guò)濾器;
5.布隆過(guò)濾器的變體

????首先我們得知道布隆過(guò)濾器的概念是什么,采自wiki百科:
布隆過(guò)濾器（英語(yǔ)：Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
tips:看完這個(gè)我們可以知道是一個(gè)叫布隆的人提出的一個(gè)用來(lái)檢索一個(gè)元素是否在一個(gè)集合中的算法，效率高，性能好。

很長(zhǎng)的二進(jìn)制向量（這里可以理解為很長(zhǎng)的bit數(shù)組）

一系列的隨機(jī)映射函數(shù)（hash函數(shù)）

????如圖所示，將一個(gè)字符串存入布隆過(guò)濾器的時(shí)候，這個(gè)字符串會(huì)先被多個(gè)hash函數(shù)生成不同的hash值，然后在對(duì)應(yīng)的bit數(shù)組的位置，將0置為1（bit數(shù)組初始化的時(shí)候，全部位置都是0）；然后第二次在有相同的字符串存入的時(shí)候，因?yàn)橹耙呀?jīng)對(duì)應(yīng)的位置都被置為1了，所以可以很輕松的知道這個(gè)值已經(jīng)存在了。
????舉個(gè)栗子，比如第一次將abc@gmail.com存入布隆過(guò)濾器，將bit數(shù)組的1，3,5位置置為了1，只要下次再有abc@gmail.com存入布隆過(guò)濾器，發(fā)現(xiàn)1,3,5已經(jīng)是全是1了，所以可知該字符串已經(jīng)保存過(guò)。（簡(jiǎn)單來(lái)說(shuō)就是bit數(shù)組中對(duì)應(yīng)的值只要全是1就存在，其他情況就是不存在，但是因?yàn)榇嬖趆ash沖突，所以會(huì)有誤判，有可能存在abc和xyz的hash值在bit數(shù)組中映射的位置是相同的。這種情況我們可以增加班名單，或者調(diào)整hash函數(shù)來(lái)減少誤判情況。）

知道了布隆過(guò)濾器的概念，我們?cè)賮?lái)看看在實(shí)際工作中，它主要使用在哪些地方。

1.網(wǎng)絡(luò)爬蟲可以通過(guò)布隆過(guò)濾器判斷當(dāng)前的url是否已經(jīng)爬取過(guò)；

2.防止惡意鏈接或者垃圾郵件，短信之類的，從數(shù)十億個(gè)鏈接或者垃圾郵件中判斷該鏈接（郵件發(fā)件人，短信發(fā)信人是否是在黑名單中），
平時(shí)手機(jī)上來(lái)電提示寫著對(duì)方式惡意推銷，外賣，這種場(chǎng)景也是可以用布隆過(guò)濾器來(lái)判斷；

3.防止緩存擊穿，將已存在的緩存放到布隆中，當(dāng)使用緩存的時(shí)候，可以先訪問(wèn)布隆過(guò)濾器，存在則訪問(wèn)緩存，不存在則訪問(wèn)數(shù)據(jù)庫(kù)；

4.檢索系統(tǒng)查詢當(dāng)前的輸入信息是否存在于數(shù)據(jù)庫(kù)中，也可以使用布隆過(guò)濾器。

public class BloomFilter {


    /**
     * bitSet的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 選取的hash函數(shù)
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * bitSet每一位只能是true或false  其實(shí)就是bit數(shù)組說(shuō)的0或者1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    public static void main(String[] args) {
        String value = "wxwwt@gmail.com";
        BloomFilter filter = new BloomFilter();
        System.out.println(filter.contains(value));
        filter.add(value);
        System.out.println(filter.contains(value));
    }

    public BloomFilter() {
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    public static class SimpleHash {

        private int cap;
        private int seed;

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

        /**
         * 計(jì)算hash值
         *
         * @param value
         * @return
         */

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }

    }
}

google的java工具包中已經(jīng)編寫了布隆過(guò)濾器的代碼，可以直接拿來(lái)用，具體使用可以google一下，這里只簡(jiǎn)單的提一下：

public static void main(String[] args) {
      // 創(chuàng)建布隆過(guò)濾器
      BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 1000);

      // 添加數(shù)據(jù)
      for (int index = 0; index < 100000; index++) {
          bloomFilter.put("wxwwt-" + index);
      }

      //  查看數(shù)據(jù)是否存在
      if (bloomFilter.mightContain("wxwwt-" + 9999)) {
          System.out.println("存在");
      }
      // 誤判元素
      if (bloomFilter.mightContain("不存在的元素")) {
          System.out.println("誤判啦");
      } else {
          System.out.println("不存在");
      }
  }

運(yùn)行結(jié)果：

在數(shù)據(jù)量很大的時(shí)候使用布隆過(guò)濾器非常方便，占用的內(nèi)存空間很小（因?yàn)槭褂玫氖莃it數(shù)組，空間使用非常小，空間開銷就是bit數(shù)組的大?。樵冃室埠芨撸ㄖ苯油ㄟ^(guò)計(jì)算hash函數(shù)的出來(lái)的），唯一的問(wèn)題就是可能會(huì)有誤判，不過(guò)概率也是比較小的，也可以通過(guò)增加白名單和增加hash函數(shù)的數(shù)量來(lái)減少這個(gè)問(wèn)題的產(chǎn)生，總的來(lái)說(shuō)利大于弊，在僅判斷元素是否存在而不涉及到刪除的情況下非常好用（最基本的bloomfilter是無(wú)法刪除元素的，置為0就沒(méi)法判斷存在情況了，有bloom過(guò)濾器的變體是支持刪除的）。

1.https://nick-weixx.github.io/...
2.https://zh.wikipedia.org/wiki...
3.https://zhangluncong.com/2018...