淺談布隆過濾器

jone5679 發布于2019-08-16 13:52 / 1527人閱讀

摘要：那該怎么辦，現在該介紹今天的主角了布隆過濾器就可以解決這樣的問題。具體介紹布隆過濾器實際上是一個很長的二進制矢量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。缺點布隆過濾器有寧可錯殺一百，也不能放過一個的性質。

1. 問題情景

如果面試官問你，一個網站有 100 億 url 存在一個黑名單中，每條 url 平均 64 字節。問這個黑名單要怎么存？若此時隨便輸入一個 url，如何判斷該 url 是否在這個黑名單中？

對于第一個問題，如果把黑名單看成一個集合，將其存在 hashmap 中，貌似太大了，需要 640G，明顯不科學。

那該怎么辦？ok，現在該介紹今天的主角了 —— 布隆過濾器就可以解決這樣的問題。

首先，布隆過濾器是什么？維基百科是這樣解釋的：

布隆過濾器（英語：Bloom
Filter）是1970年由布隆提出的。它實際上是一個很長的二進制矢量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。

官方說法看下就好，如果不理解沒關系，其實不會難，下面我們講人話慢慢來。

2. 具體介紹

布隆過濾器實際上是一個很長的二進制矢量和一系列隨機映射函數。

「很長的二進制矢量」：這是一個長度很長的數組，什么類型的數組呢？bit 類型的數組，也是我們說的「位」，（1Byte = 8bit，1KB = 1024Byte）。

「一系列隨機映射函數」：有多個哈希函數。那什么是哈希函數呢？JDK 里面有計算得到哈希值的方法，那就是一個哈希函數。

布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難

這個不就可以解決我們最開始的問題嗎？那它是怎么解決的呢？

3. 解決過程

下面我說下大體的過程，細節部分可先不理解，重要的是明白流程，細節我后面補充。

假設，bit 類型數組的長度為 m，每個元素值為 0，有 k 個哈希函數。

首先，當輸入一個 url 的時候，此時這個 url 會經過 k 個哈希函數處理，得到多個哈希值（v1,v2,...,vk）。之后得到這些哈希值對應在數組的下標位置，最后將這些下標的元素都置為 1。

那么如何判斷一個 url 在黑名單里面呢？輸入一條 url，它經過上述處理之后，會得到多個數組的下標位置。如果這些下標的元素值都已經為 1 了，說明該在黑名單里面，否則不在。

總體就是這樣的流程，下面說下大家可能存在的疑問：

1、bit 類型的數組如何構建

2、得到 v1,v2,...,vk 這些哈希值后，如何得到其在數組的下標位置，并將其設置為 1 呢？

兩個問題我一起說下，Java 里面沒有 bit 這樣的類型，怎么構建呢？—— 不難，我們可以使用 int，一個 int 是 32 位。

//創建了一個 100 * 32bit 的數組
int[] arr = new int[100]; 
// 代表 bit 數組 0-31 位的元素
arr[0];

因此上面再會說「分別將這些哈希值除以數組的長度 m，和對 m 取模，得到這些哈希值對應在數組的下標位置」。

具體我們可以拿一個哈希值 data 來舉個栗子，假設 int 數組長度為 100。

void Set(int data) {
       // ByteNO 是表示在 table 數組中那個元素
       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. 缺點

布隆過濾器有寧可錯殺一百，也不能放過一個的性質。講人話就是屬于黑名單的 url 一定能夠正確判斷它在黑名單中，但不屬于黑名單中的 url 也可能會被認為在黑名單中，存在一定的失誤率。

至于失誤率要保持在多少，數組長度，哈希函數的個數分別要設置多少就需要根據實際情況來選擇了，網上有對應的數學公式計算，這里就不展開講了。

參考：
https://blog.csdn.net/wenqian...

歡迎關注微信公眾號「不只Java」，后臺回復「電子書」，送說不定有你想要的呢

GPU云服務器云服務器布隆過濾器布隆去重設計淺談淺談javascript

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72490.html

布隆過濾器簡介

摘要：布隆過濾器可以用于檢索一個元素是否在一個集合中。舉個栗子，比如第一次將存入布隆過濾器，將數組的，位置置為了，只要下次再有存入布隆過濾器，發現已經是全是了，所以可知該字符串已經保存過。 ????最近做爬蟲項目過濾重復的url的時候,了解到一個東西,叫布隆過濾器,然后也學習了一下,寫下這篇博客記錄一下.下面我們將分為幾個專題來介紹布隆過濾器:1.什么是布隆過濾器;2.布隆過濾器的使用場景和...

shuibo 2019-08-16 17:30 評論0 收藏0
大白話布隆過濾器

摘要：可以看出，僅僅從布隆過濾器本身而言，根本沒有存放完整的數據，只是運用一系列隨機映射函數計算出位置，然后填充二進制向量。也就是說布隆過濾器只能判斷數據是否一定不存在，而無法判斷數據是否一定存在。我向布隆過濾器插入了，然后用來測試誤判率。本文是站在小白的角度去討論布隆過濾器，如果你是科班出身，或者比較聰明，又或者真正想完全搞懂布隆過濾器的可以移步。不知道從什么時候開始，本來默默無聞的布隆過濾器...

meteor199 2019-05-23 16:22 評論0 收藏0
布隆過濾器的Python實現(標準、計數、標準擴容、計數擴容)

摘要：布隆過濾器的實現，包括標準計數標準擴容計數擴容。計數擴容布隆過濾器標準擴容布隆過濾器的子類，功能繼承自標準擴容布隆過濾器，但支持刪除元素的操作。 bloompy github:bloompy 布隆過濾器的Python3實現，包括標準、計數、標準擴容、計數擴容。更新自pybloom。安裝 pip install bloompy 使用通過bloompy你可以使用四種布隆過濾器標準布...

Pocher 2019-07-30 18:35 評論0 收藏0