前言

記得前段時(shí)間的文章么？redis使用位圖法記錄在線用戶的狀態(tài)，還是需要自己實(shí)現(xiàn)一個(gè)IM在線用戶狀態(tài)的記錄，今天來(lái)講講另一方案，布隆過(guò)濾器

布隆過(guò)濾器的作用是加快判定一個(gè)元素是否在集合中出現(xiàn)的方法。因?yàn)槠渲饕沁^(guò)濾掉了大部分元素間的精確匹配，故稱為過(guò)濾器。

布隆過(guò)濾器

在日常生活工作，我們會(huì)經(jīng)常遇到這的場(chǎng)景，從一個(gè)Excel里面檢索一個(gè)信息在不在Excel表中，還記得被CTRL+F支配的恐懼么，不扯了，軟件開(kāi)發(fā)中，一般會(huì)使用散列表來(lái)實(shí)現(xiàn)，Hash Table也叫哈希表，哈希表的優(yōu)點(diǎn)是快速準(zhǔn)確，缺點(diǎn)是浪費(fèi)儲(chǔ)存空間，我們這個(gè)場(chǎng)景，儲(chǔ)存登錄的userId到哈希表，當(dāng)用戶規(guī)模十分巨大的時(shí)候，哈希表的儲(chǔ)存效率低的問(wèn)題就顯示出來(lái)了，今天介紹一種數(shù)學(xué)工具：布隆過(guò)濾器，它只需要哈希表1/8到1/4的大小就能解決同樣的問(wèn)題。

背書(shū)中

布隆過(guò)濾器（Bloom Filter）是由伯頓·布?。˙urton Bloom）于1970年提出來(lái)的，它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。

原理

使用我們這個(gè)場(chǎng)景，來(lái)講原理吧，假設(shè)我們的個(gè)人網(wǎng)站同時(shí)在線人數(shù)達(dá)到1億（意淫一下），要存儲(chǔ)這一億人的在線狀態(tài)，先構(gòu)建一個(gè)16億比特位即兩億字節(jié)的向量，然后把這16億個(gè)比特位都記為0。對(duì)于每一個(gè)登錄用的userId，使用8個(gè)不同的算法產(chǎn)出8個(gè)不同信息指紋，在用一個(gè)算法把這8個(gè)信息隱身到這16億個(gè)比特位的8個(gè)位置上，把這8個(gè)位置都設(shè)置成1，這樣就構(gòu)建成了一個(gè)記錄一億用戶在線狀態(tài)的布隆過(guò)濾器。

1億在線用戶的布隆過(guò)濾器

檢索就是同樣的原理，使用相同的算法對(duì)要檢索的userId產(chǎn)生8個(gè)信息指紋，然后在看這八個(gè)信息指紋在這16億比特位對(duì)應(yīng)的值是否為1，都為1就說(shuō)明這個(gè)userId在線，下面就用java代碼來(lái)實(shí)現(xiàn)一個(gè)布隆過(guò)濾器。

Java實(shí)現(xiàn)布隆過(guò)濾器

先實(shí)現(xiàn)一個(gè)簡(jiǎn)單的布隆過(guò)濾器

package edu.se;

import java.util.BitSet;

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

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

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

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

 //判斷是否在布隆過(guò)濾器中
 public boolean contains(String value) {
 if (value == null) {
  return false;
 }
 boolean ret = true;
 for (Hash f : hashList) {
  //查看8個(gè)比特位上的值
  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");

 //維護(hù)1億個(gè)在線用戶
 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));
 }
}

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

維護(hù)了1億個(gè)userId以后檢索5324512515是否登錄，代碼執(zhí)行時(shí)間很短

在讓我們來(lái)看看內(nèi)存占用的情況

jvm整個(gè)的內(nèi)存情況

再來(lái)看看BloomFileter這個(gè)類(lèi)的實(shí)例，就占用了100多MB

實(shí)例的大小

看來(lái)布隆過(guò)濾器對(duì)于儲(chǔ)存的效率確實(shí)很高

布隆過(guò)濾器的誤識(shí)別問(wèn)題

布隆過(guò)濾器的好處在于快速、省空間，但是有一定的誤識(shí)別率，這個(gè)概率很小，要計(jì)算出現(xiàn)誤識(shí)別的概率并不難，下面貼一段書(shū)上的話

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

書(shū)上的表，直接拍下來(lái)的

書(shū)上的表，直接拍下來(lái)的

布隆過(guò)濾器就為大家說(shuō)到這里，歡迎大家來(lái)交流，指出文中一些說(shuō)錯(cuò)的地方，讓我加深認(rèn)識(shí)。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論