記得前段時間的文章么？redis使用位圖法記錄在線用戶的狀態(tài)孤里，還是需要自己實現(xiàn)一個IM在線用戶狀態(tài)的記錄捌袜，今天來講講另一方案，布隆過濾器
布隆過濾器
在日常生活工作弄唧，我們會經(jīng)常遇到這的場景霍衫，從一個Excel里面檢索一個信息在不在Excel表中，還記得被CTRL+F支配的恐懼么澄干，不扯了柠傍，軟件開發(fā)中惧笛，一般會使用散列表來實現(xiàn)，Hash Table也叫哈希表静檬，哈希表的優(yōu)點是快速準(zhǔn)確并级，缺點是浪費儲存空間侮腹，我們這個場景父阻，儲存登錄的userId到哈希表，當(dāng)用戶規(guī)模十分巨大的時候履婉，哈希表的儲存效率低的問題就顯示出來了斟览，今天介紹一種數(shù)學(xué)工具：布隆過濾器，它只需要哈希表1/8到1/4的大小就能解決同樣的問題已烤。
背書中
布隆過濾器（Bloom Filter）是由伯頓·布隆（Burton Bloom）于1970年提出來的稍计，它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)裕循。
原理
使用我們這個場景剥哑，來講原理吧，假設(shè)我們的個人網(wǎng)站同時在線人數(shù)達(dá)到1億（意淫一下）抢埋，要存儲這一億人的在線狀態(tài)督暂，先構(gòu)建一個16億比特位即兩億字節(jié)的向量逻翁，然后把這16億個比特位都記為0。對于每一個登錄用的userId酷愧，使用8個不同的算法產(chǎn)出8個不同信息指紋缠诅，在用一個算法把這8個信息隱身到這16億個比特位的8個位置上，把這8個位置都設(shè)置成1士败，這樣就構(gòu)建成了一個記錄一億用戶在線狀態(tài)的布隆過濾器褥伴。
檢索就是同樣的原理重慢，使用相同的算法對要檢索的userId產(chǎn)生8個信息指紋似踱，然后在看這八個信息指紋在這16億比特位對應(yīng)的值是否為1志衣，都為1就說明這個userId在線猛们，下面就用java代碼來實現(xiàn)一個布隆過濾器弯淘。
Java實現(xiàn)布隆過濾器
先實現(xiàn)一個簡單的布隆過濾器
package edu.se;
import java.util.BitSet;
/**
* @author ZhaoWeinan
* @date 2018/10/28
* @description
*/
public class BloomFileter {
//使用加法hash算法，所以定義了一個8個元素的質(zhì)數(shù)數(shù)組
private static final int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
//用八個不同的質(zhì)數(shù)假勿，相當(dāng)于構(gòu)建8個不同算法
private Hash[] hashList = new Hash[primes.length];
//創(chuàng)建一個長度為10億的比特位
private BitSet bits = new BitSet(256 << 22);
public BloomFileter() {
for (int i = 0; i < primes.length; i++) {
//使用8個質(zhì)數(shù)态鳖，創(chuàng)建八種算法
hashList[i] = new Hash(primes[i]);
}
}
//添加元素
public void add(String value) {
for (Hash f : hashList) {
//算出8個信息指紋浆竭，對應(yīng)到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));
}
}
這段代碼是構(gòu)建了一個10億位的bitSet邦泄，然后把一億個userId加入到了我們的布隆過濾器中顺囊，最近判斷5324512515這個userId是否登錄，打出代碼的執(zhí)行時間
在讓我們來看看內(nèi)存占用的情況
再來看看BloomFileter這個類的實例站宗，就占用了100多MB
看來布隆過濾器對于儲存的效率確實很高
布隆過濾器的誤識別問題
布隆過濾器的好處在于快速硅瞧、省空間份乒，但是有一定的誤識別率恕汇，這個概率很小腕唧，要計算出現(xiàn)誤識別的概率并不難，下面貼一段書上的話
假定布隆過濾器有m比特瘾英，里面有n個元素枣接，每個元素對應(yīng)k個信息指紋的hash函數(shù)，在這個布隆過濾器插入一個元素缺谴，那么比特位被設(shè)置成1的概率為1/m但惶，它依然為0的概率為1-1/m，那么k個哈希函數(shù)都沒有把他設(shè)置成1的概率為1-1/m的k次方，一個比特在插入了n個元素后膀曾，被設(shè)置為1的概率為1減1-1/m的kn次方，最后書上給出了一個公式添谊，在這里就不貼了财喳，就貼一個表吧，是m/n比值不同斩狱，以及K分別為不同的值得情況下的假陽性概率：
布隆過濾器就為大家說到這里所踊，歡迎大家來交流泌枪，指出文中一些說錯的地方，讓我加深認(rèn)識秕岛。
最近開了一個微信公眾號畴蒲，IT知識貓攒驰，歡迎大家來投稿交流。
謝謝大家！
