資訊專欄INFORMATION COLUMN
摘要：那該怎么辦，現(xiàn)在該介紹今天的主角了布隆過濾器就可以解決這樣的問題。具體介紹布隆過濾器實際上是一個很長的二進(jìn)制矢量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。缺點布隆過濾器有寧可錯殺一百，也不能放過一個的性質(zhì)。
1. 問題情景
如果面試官問你，一個網(wǎng)站有 100 億 url 存在一個黑名單中，每條 url 平均 64 字節(jié)。問這個黑名單要怎么存？若此時隨便輸入一個 url，如何判斷該 url 是否在這個黑名單中？
對于第一個問題，如果把黑名單看成一個集合，將其存在 hashmap 中，貌似太大了，需要 640G，明顯不科學(xué)。
那該怎么辦？ok，現(xiàn)在該介紹今天的主角了 —— 布隆過濾器就可以解決這樣的問題。
首先，布隆過濾器是什么？維基百科是這樣解釋的：
布隆過濾器（英語：Bloom
Filter）是1970年由布隆提出的。它實際上是一個很長的二進(jìn)制矢量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點是有一定的誤識別率和刪除困難。
官方說法看下就好，如果不理解沒關(guān)系，其實不會難，下面我們講人話慢慢來。
2. 具體介紹布隆過濾器實際上是一個很長的二進(jìn)制矢量和一系列隨機(jī)映射函數(shù)。
「很長的二進(jìn)制矢量」：這是一個長度很長的數(shù)組，什么類型的數(shù)組呢？bit 類型的數(shù)組，也是我們說的「位」，（1Byte = 8bit，1KB = 1024Byte）。
「一系列隨機(jī)映射函數(shù)」：有多個哈希函數(shù)。那什么是哈希函數(shù)呢？JDK 里面有計算得到哈希值的方法，那就是一個哈希函數(shù)。
布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點是有一定的誤識別率和刪除困難
這個不就可以解決我們最開始的問題嗎？那它是怎么解決的呢？
3. 解決過程下面我說下大體的過程，細(xì)節(jié)部分可先不理解，重要的是明白流程，細(xì)節(jié)我后面補充。
假設(shè)，bit 類型數(shù)組的長度為 m，每個元素值為 0，有 k 個哈希函數(shù)。
首先，當(dāng)輸入一個 url 的時候，此時這個 url 會經(jīng)過 k 個哈希函數(shù)處理，得到多個哈希值（v1,v2,...,vk）。之后得到這些哈希值對應(yīng)在數(shù)組的下標(biāo)位置，最后將這些下標(biāo)的元素都置為 1。
那么如何判斷一個 url 在黑名單里面呢？輸入一條 url，它經(jīng)過上述處理之后，會得到多個數(shù)組的下標(biāo)位置。如果這些下標(biāo)的元素值都已經(jīng)為 1 了，說明該在黑名單里面，否則不在。
總體就是這樣的流程，下面說下大家可能存在的疑問：
1、bit 類型的數(shù)組如何構(gòu)建
2、得到 v1,v2,...,vk 這些哈希值后，如何得到其在數(shù)組的下標(biāo)位置，并將其設(shè)置為 1 呢？
兩個問題我一起說下，Java 里面沒有 bit 這樣的類型，怎么構(gòu)建呢？—— 不難，我們可以使用 int，一個 int 是 32 位。
//創(chuàng)建了一個 100 * 32bit 的數(shù)組 int[] arr = new int[100]; // 代表 bit 數(shù)組 0-31 位的元素 arr[0];
因此上面再會說「分別將這些哈希值除以數(shù)組的長度 m，和對 m 取模，得到這些哈希值對應(yīng)在數(shù)組的下標(biāo)位置」。
具體我們可以拿一個哈希值 data 來舉個栗子，假設(shè) int 數(shù)組長度為 100。
void Set(int data) {
// ByteNO 是表示在 table 數(shù)組中那個元素
int ByteNo = data / 32;
// bitNo 是表示在 32 位 bit 中哪個 bit 位。
int BitNo = data % 32;
// 置 1
_table[ByteNo] |= (1 << BitNo);
}
4. 使用效果
最開始我們提到，如果將 100 億 url 放到 HashMap 中需要 640GB，那么使用布隆過濾器后又需要多少空間呢？答案是約等于 23 GB。相比之下，這個空間大小是不是就可以接受很多了。
5. 缺點布隆過濾器有寧可錯殺一百，也不能放過一個的性質(zhì)。講人話就是屬于黑名單的 url 一定能夠正確判斷它在黑名單中，但不屬于黑名單中的 url 也可能會被認(rèn)為在黑名單中，存在一定的失誤率。
至于失誤率要保持在多少，數(shù)組長度，哈希函數(shù)的個數(shù)分別要設(shè)置多少就需要根據(jù)實際情況來選擇了，網(wǎng)上有對應(yīng)的數(shù)學(xué)公式計算，這里就不展開講了。
參考：
https://blog.csdn.net/wenqian...
歡迎關(guān)注微信公眾號「不只Java」，后臺回復(fù)「電子書」，送說不定有你想要的呢
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/72490.html
摘要：布隆過濾器的實現(xiàn)，包括標(biāo)準(zhǔn)計數(shù)標(biāo)準(zhǔn)擴(kuò)容計數(shù)擴(kuò)容。計數(shù)擴(kuò)容布隆過濾器標(biāo)準(zhǔn)擴(kuò)容布隆過濾器的子類，功能繼承自標(biāo)準(zhǔn)擴(kuò)容布隆過濾器，但支持刪除元素的操作。 bloompy github:bloompy 布隆過濾器的Python3實現(xiàn)，包括標(biāo)準(zhǔn)、計數(shù)、標(biāo)準(zhǔn)擴(kuò)容、計數(shù)擴(kuò)容。更新自pybloom。 安裝 pip install bloompy 使用 通過bloompy你可以使用四種布隆過濾器 標(biāo)準(zhǔn)布...
閱讀 2022·2021-11-22 14:44
閱讀 1830·2021-11-02 14:46
閱讀 3875·2021-10-13 09:40
閱讀 2722·2021-09-07 09:58
閱讀 1852·2021-09-03 10:28
閱讀 1736·2019-08-29 15:30
閱讀 1065·2019-08-29 15:28
閱讀 1552·2019-08-26 12:20
