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