摘要:可以看出,僅僅從布隆過濾器本身而言,根本沒有存放完整的數據,只是運用一系列隨機映射函數計算出位置,然后填充二進制向量。也就是說布隆過濾器只能判斷數據是否一定不存在,而無法判斷數據是否一定存在。我向布隆過濾器插入了,然后用來測試誤判率。
本文是站在小白的角度去討論布隆過濾器,如果你是科班出身,或者比較聰明,又或者真正想完全搞懂布隆過濾器的可以移步。
不知道從什么時候開始,本來默默無聞的布隆過濾器一下子名聲大燥,仿佛身在互聯網,做著開發的,無人不知,無人不曉,哪怕對技術不是很關心的小伙伴也聽過它的名號。我也花了不少時間去研究布隆過濾器,看了不少博客,無奈不是科班出身,又沒有那么聰明的頭腦,又比較懶...經過“放棄,拿起,放棄,拿起”的無限輪回,應該算是了解了布隆過濾器的核心思想,所以想給大家分享下。
布隆過濾器的應用我們先來看下布隆過濾器的應用場景,讓大家知道神奇的布隆過濾器到底能做什么。
我們經常會把一部分數據放在Redis等緩存,比如產品詳情。這樣有查詢請求進來,我們可以根據產品Id直接去緩存中取數據,而不用讀取數據庫,這是提升性能最簡單,最普遍,也是最有效的做法。一般的查詢請求流程是這樣的:先查緩存,有緩存的話直接返回,如果緩存中沒有,再去數據庫查詢,然后再把數據庫取出來的數據放入緩存,一切看起來很美好。但是如果現在有大量請求進來,而且都在請求一個不存在的產品Id,會發生什么?既然產品Id都不存在,那么肯定沒有緩存,沒有緩存,那么大量的請求都懟到數據庫,數據庫的壓力一下子就上來了,還有可能把數據庫打死。 雖然有很多辦法都可以解決這問題,但是我們的主角是“布隆過濾器”,沒錯,“布隆過濾器”就可以解決(緩解)緩存穿透問題。至于為什么說是“緩解”,看下去你就明白了。
現在有大量的數據,而這些數據的大小已經遠遠超出了服務器的內存,現在再給你一個數據,如何判斷給你的數據在不在其中。如果服務器的內存足夠大,那么用HashMap是一個不錯的解決方案,理論上的時間復雜度可以達到O(1),但是現在數據的大小已經遠遠超出了服務器的內存,所以無法使用HashMap,這個時候就可以使用“布隆過濾器”來解決這個問題。但是還是同樣的,會有一定的“誤判率”。
什么是布隆過濾器布隆過濾器是一個叫“布隆”的人提出的,它本身是一個很長的二進制向量,既然是二進制的向量,那么顯而易見的,存放的不是0,就是1。
現在我們新建一個長度為16的布隆過濾器,默認值都是0,就像下面這樣:
現在需要添加一個數據:
我們通過某種計算方式,比如Hash1,計算出了Hash1(數據)=5,我們就把下標為5的格子改成1,就像下面這樣:
我們又通過某種計算方式,比如Hash2,計算出了Hash2(數據)=9,我們就把下標為9的格子改成1,就像下面這樣:
還是通過某種計算方式,比如Hash3,計算出了Hash3(數據)=2,我們就把下標為2的格子改成1,就像下面這樣:
這樣,剛才添加的數據就占據了布隆過濾器“5”,“9”,“2”三個格子。
可以看出,僅僅從布隆過濾器本身而言,根本沒有存放完整的數據,只是運用一系列隨機映射函數計算出位置,然后填充二進制向量。
這有什么用呢?比如現在再給你一個數據,你要判斷這個數據是否重復,你怎么做?
你只需利用上面的三種固定的計算方式,計算出這個數據占據哪些格子,然后看看這些格子里面放置的是否都是1,如果有一個格子不為1,那么就代表這個數字不在其中。這很好理解吧,比如現在又給你了剛才你添加進去的數據,你通過三種固定的計算方式,算出的結果肯定和上面的是一模一樣的,也是占據了布隆過濾器“5”,“9”,“2”三個格子。
但是有一個問題需要注意,如果這些格子里面放置的都是1,不一定代表給定的數據一定重復,也許其他數據經過三種固定的計算方式算出來的結果也是相同的。這也很好理解吧,比如我們需要判斷對象是否相等,是不可以僅僅判斷他們的哈希值是否相等的。
也就是說布隆過濾器只能判斷數據是否一定不存在,而無法判斷數據是否一定存在。
按理來說,介紹完了新增、查詢的流程,就要介紹刪除的流程了,但是很遺憾的是布隆過濾器是很難做到刪除數據的,為什么?你想想,比如你要刪除剛才給你的數據,你把“5”,“9”,“2”三個格子都改成了0,但是可能其他的數據也映射到了“5”,“9”,“2”三個格子啊,這不就亂套了嗎?
相信經過我這么一介紹,大家對布隆過濾器應該有一個淺顯的認識了,至少你應該清楚布隆過濾器的優缺點了:
優點:由于存放的不是完整的數據,所以占用的內存很少,而且新增,查詢速度夠快;
缺點: 隨著數據的增加,誤判率隨之增加;無法做到刪除數據;只能判斷數據是否一定不存在,而無法判斷數據是否一定存在。
可以看到,布隆過濾器的優點和缺點一樣明顯。
在上文中,我舉的例子二進制向量長度為16,由三個隨機映射函數計算位置,在實際開發中,如果你要添加大量的數據,僅僅16位是遠遠不夠的,為了讓誤判率降低,我們還可以用更多的隨機映射函數、更長的二進制向量去計算位置。
guava實現布隆過濾器現在相信你對布隆過濾器應該有一個比較感性的認識了,布隆過濾器核心思想其實并不難,難的在于如何設計隨機映射函數,到底映射幾次,二進制向量的長度設置為多少比較好,這可能就不是一般的開發可以駕馭的了,好在Google大佬給我們提供了開箱即用的組件,來幫助我們實現布隆過濾器,現在就讓我們看看怎么Google大佬送給我們的“禮物”吧。
首先在pom引入“禮物”:
com.google.guava guava 19.0
然后就可以測試啦:
private static int size = 1000000;//預計要插入多少數據
private static double fpp = 0.01;//期望的誤判率
private static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
//插入數據
for (int i = 0; i < 1000000; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "誤判了");
}
}
System.out.println("總共的誤判數:" + count);
}
代碼簡單分析: 我們定義了一個布隆過濾器,有兩個重要的參數,分別是 我們預計要插入多少數據,我們所期望的誤判率,誤判率不能為0。 我向布隆過濾器插入了0-1000000,然后用1000000-2000000來測試誤判率。
運行結果:
1999501誤判了 1999567誤判了 1999640誤判了 1999697誤判了 1999827誤判了 1999942誤判了 總共的誤判數:10314
現在總共有100萬數據是不存在的,誤判了10314次,我們計算下誤判率
和我們定義的期望誤判率0.01相差無幾。redis實現布隆過濾器
上面使用guava實現布隆過濾器是把數據放在本地內存中,無法實現布隆過濾器的共享,我們還可以把數據放在redis中,用 redis來實現布隆過濾器,我們要使用的數據結構是bitmap,你可能會有疑問,redis支持五種數據結構:String,List,Hash,Set,ZSet,沒有bitmap呀。沒錯,實際上bitmap的本質還是String。
可能有小伙伴會說,納尼,布隆過濾器還沒介紹完,怎么又出來一個bitmap,沒事,你可以把bitmap就理解為一個二進制向量。
要用redis來實現布隆過濾器,我們需要自己設計映射函數,自己度量二進制向量的長度,這對我來說,無疑是一個不可能完成的任務,只能借助搜索引擎,下面直接放出代碼把。
public class RedisMain {
static final int expectedInsertions = 100;//要插入多少數據
static final double fpp = 0.01;//期望的誤判率
//bit數組長度
private static long numBits;
//hash函數數量
private static int numHashFunctions;
static {
numBits = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
}
public static void main(String[] args) {
Jedis jedis = new Jedis("192.168.0.109", 6379);
for (int i = 0; i < 100; i++) {
long[] indexs = getIndexs(String.valueOf(i));
for (long index : indexs) {
jedis.setbit("codebear:bloom", index, true);
}
}
for (int i = 0; i < 100; i++) {
long[] indexs = getIndexs(String.valueOf(i));
for (long index : indexs) {
Boolean isContain = jedis.getbit("codebear:bloom", index);
if (!isContain) {
System.out.println(i + "肯定沒有重復");
}
}
System.out.println(i + "可能重復");
}
}
/**
* 根據key獲取bitmap下標
*/
private static long[] getIndexs(String key) {
long hash1 = hash(key);
long hash2 = hash1 >>> 16;
long[] result = new long[numHashFunctions];
for (int i = 0; i < numHashFunctions; i++) {
long combinedHash = hash1 + i * hash2;
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
result[i] = combinedHash % numBits;
}
return result;
}
private static long hash(String key) {
Charset charset = Charset.forName("UTF-8");
return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong();
}
//計算hash函數個數
private static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
//計算bit數組長度
private static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
}
運行結果:
88可能重復 89可能重復 90可能重復 91可能重復 92可能重復 93可能重復 94可能重復 95可能重復 96可能重復 97可能重復 98可能重復 99可能重復
本篇博客到這里就結束了,謝謝大家。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/7188.html
摘要:布隆過濾器的實現,包括標準計數標準擴容計數擴容。計數擴容布隆過濾器標準擴容布隆過濾器的子類,功能繼承自標準擴容布隆過濾器,但支持刪除元素的操作。 bloompy github:bloompy 布隆過濾器的Python3實現,包括標準、計數、標準擴容、計數擴容。更新自pybloom。 安裝 pip install bloompy 使用 通過bloompy你可以使用四種布隆過濾器 標準布...
閱讀 2675·2023-04-25 15:15
閱讀 1316·2021-11-25 09:43
閱讀 1604·2021-11-23 09:51
閱讀 1079·2021-11-12 10:36
閱讀 2880·2021-11-11 16:55
閱讀 955·2021-11-08 13:18
閱讀 723·2021-10-28 09:31
閱讀 2048·2019-08-30 15:47