Java如何實現布隆過濾器

這篇文章將為大家詳細講解有關Java如何實現布隆過濾器，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

前言

布隆過濾器的作用是加快判定一個元素是否在集合中出現的方法。因為其主要是過濾掉了大部分元素間的精確匹配，故稱為過濾器。

布隆過濾器

在日常生活工作，我們會經常遇到這的場景，從一個Excel里面檢索一個信息在不在Excel表中，還記得被CTRL+F支配的恐懼么，不扯了，軟件開發中，一般會使用散列表來實現，Hash Table也叫哈希表，哈希表的優點是快速準確，缺點是浪費儲存空間，我們這個場景，儲存登錄的userId到哈希表，當用戶規模十分巨大的時候，哈希表的儲存效率低的問題就顯示出來了，今天介紹一種數學工具：布隆過濾器，它只需要哈希表1/8到1/4的大小就能解決同樣的問題。

背書中

布隆過濾器（Bloom Filter）是由伯頓·布隆（Burton Bloom）于1970年提出來的，它實際上是一個很長的二進制向量和一系列隨機映射函數。

原理

使用我們這個場景，來講原理吧，假設我們的個人網站同時在線人數達到1億（意淫一下），要存儲這一億人的在線狀態，先構建一個16億比特位即兩億字節的向量，然后把這16億個比特位都記為0。對于每一個登錄用的userId，使用8個不同的算法產出8個不同信息指紋，在用一個算法把這8個信息隱身到這16億個比特位的8個位置上，把這8個位置都設置成1，這樣就構建成了一個記錄一億用戶在線狀態的布隆過濾器。

1億在線用戶的布隆過濾器

檢索就是同樣的原理，使用相同的算法對要檢索的userId產生8個信息指紋，然后在看這八個信息指紋在這16億比特位對應的值是否為1，都為1就說明這個userId在線，下面就用java代碼來實現一個布隆過濾器。

Java實現布隆過濾器

先實現一個簡單的布隆過濾器

package edu.se;

import java.util.BitSet;

/**
 * @author ZhaoWeinan
 * @date 2018/10/28
 * @description
 */
public class BloomFileter {

 //使用加法hash算法，所以定義了一個8個元素的質數數組
 private static final int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
 //用八個不同的質數，相當于構建8個不同算法
 private Hash[] hashList = new Hash[primes.length];
 //創建一個長度為10億的比特位
 private BitSet bits = new BitSet(256 << 22);

 public BloomFileter() {
 for (int i = 0; i < primes.length; i++) {
  //使用8個質數，創建八種算法
  hashList[i] = new Hash(primes[i]);
 }
 }

 //添加元素
 public void add(String value) {
 for (Hash f : hashList) {
  //算出8個信息指紋，對應到2的32次方個比特位上
  bits.set(f.hash(value), true);
 }
 }

 //判斷是否在布隆過濾器中
 public boolean contains(String value) {
 if (value == null) {
  return false;
 }
 boolean ret = true;
 for (Hash f : hashList) {
  //查看8個比特位上的值
  ret = ret && bits.get(f.hash(value));
 }
 return ret;
 }

 //加法hash算法
 public static class Hash {

 private int prime;

 public Hash(int prime) {
  this.prime = prime;
 }

 public int hash(String key) {
  int hash, i;
  for (hash = key.length(), i = 0; i < key.length(); i++) {
  hash += key.charAt(i);
  }
  return (hash % prime);
 }
 }

 public static void main(String[] args) {

 BloomFileter bloomFileter = new BloomFileter();
 System.out.println(bloomFileter.contains("5324512515"));
 bloomFileter.add("5324512515");

 //維護1億個在線用戶
 for (int i = 1 ; i < 100000000 ; i ++){
  bloomFileter.add(String.valueOf(i));
 }

 long begin = System.currentTimeMillis();
 System.out.println(begin);
 System.out.println(bloomFileter.contains("5324512515"));
 long end = System.currentTimeMillis();
 System.out.println(end);
 System.out.println("判斷5324512515是否在線使用了:" + (begin - end));
 }
}

這段代碼是構建了一個10億位的bitSet，然后把一億個userId加入到了我們的布隆過濾器中，最近判斷5324512515這個userId是否登錄，打出代碼的執行時間

維護了1億個userId以后檢索5324512515是否登錄，代碼執行時間很短

在讓我們來看看內存占用的情況

jvm整個的內存情況

再來看看BloomFileter這個類的實例，就占用了100多MB

實例的大小

看來布隆過濾器對于儲存的效率確實很高

布隆過濾器的誤識別問題

布隆過濾器的好處在于快速、省空間，但是有一定的誤識別率，這個概率很小，要計算出現誤識別的概率并不難，下面貼一段書上的話

假定布隆過濾器有m比特，里面有n個元素，每個元素對應k個信息指紋的hash函數，在這個布隆過濾器插入一個元素，那么比特位被設置成1的概率為1/m，它依然為0的概率為1-1/m，那么k個哈希函數都沒有把他設置成1的概率為1-1/m的k次方，一個比特在插入了n個元素后，被設置為1的概率為1減1-1/m的kn次方，最后書上給出了一個公式，在這里就不貼了，就貼一個表吧，是m/n比值不同，以及K分別為不同的值得情況下的假陽性概率：

書上的表，直接拍下來的

書上的表，直接拍下來的

布隆過濾器就為大家說到這里，歡迎大家來交流，指出文中一些說錯的地方，讓我加深認識。

關于“Java如何實現布隆過濾器”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。