漫畫:高效的布隆演算法

• 2019 年 10 月 4 日
• 筆記

x星球經過和y星球的激戰後，x星球已經無法居住，重建需要很長的時間，因此遷移到why星球上。

ps: 假設每個人ip代表不同的用戶。

ps:一個B代表一個位元組，一個位元組8位，即8個二進位數，1GB=1024MB=1024*1024KB=1024*1024*1024B。

ps:ip如何轉成int類型。每段均為最大值的ip為255.255.255.255,8位正好可以表示一個255大小的數字，因此每8位表示一個數字，ip一共是4段，正好32位。

ps: 255 * 255 * 255 * 255 = 4228250625，4228250625/(1024*1024*8)=504。

ps:f1,f2,f3代表3個不同的hash函數。箭頭指向的地方代表通過hash函數計算出的hash值同時也是在點陣圖中的位置。

ps:另外一般情況下不能從布隆過濾器中刪除元素，由於有一些字元串計算的hash值可能會相同，此時我們會想到，把每個位置存上對應的次數，刪除元素的時候同時減1，前面我們說過會有誤判的情況，所以要安全的刪掉元素不是這麼簡單。

end:本文主要講解布隆過濾器的演算法思想，具體的實現我們可以去看guava中的BloomFIlter。

文章轉載自公眾號 JAVA小咖秀 ， 作者 小小小咖