布隆過(guò)濾器就是利用的 bit
整體思想就是
1個(gè)2進(jìn)制的 bit數(shù)組
和多個(gè)不同算法的hash
怎么整呢
就是比如
我有16個(gè)bit相當(dāng)于2個(gè)字節(jié) 因?yàn)?個(gè)字節(jié)是8位 這個(gè)肯定大家都知道
因?yàn)閎it只能是 0 或者1 在因?yàn)椴悸∵^(guò)濾器的思想就是判斷存過(guò)的key是否存在
所以就簡(jiǎn)單了 就是整一堆2進(jìn)制bit數(shù)組
0 0 0 0 0 0 0 0 這是8位bit 數(shù)組肯定有下標(biāo)
如果我存的key是 “中國(guó)”
上面講了有多個(gè)hash算法 那既然是多個(gè)hash算法對(duì) “中國(guó)” hash肯定就得出來(lái)的數(shù)不一樣
比如 hash1算法（中國(guó)） =2 hash2算法（中國(guó)）=5
那么存的結(jié)果就是
0 0 0 1 0 0 1 0 第二位和第五位就都變成1了 ps我不確定bit數(shù)組下標(biāo)從0開始還是1開始所以就 假設(shè)他從1開始
所以在判斷中國(guó)存在不存在的時(shí)候 就根據(jù)兩次hash算法去對(duì)應(yīng)的下標(biāo)看是不是1， 如果是0肯定就沒有
如果都是1 也不一定 就有 蹈胡。 為什么這么說(shuō) 因?yàn)槎鄠€(gè)hash算法就是為了避免hash碰撞出刷，但是我們學(xué)過(guò)hashmap都了解hash是肯定會(huì)碰撞的 所以 遇到 其他的key剛好和你碰撞了 就會(huì)進(jìn)行誤判了 所以 布隆過(guò)濾器主要是解決判斷這個(gè)這個(gè)key是否存儲(chǔ)過(guò)稳摄，如果多個(gè)hash的結(jié)果只要有一個(gè)bit位置是0那么這個(gè)key肯定就沒有布隆過(guò)濾器這個(gè)可以做的非常好 但是你得業(yè)務(wù)要是 對(duì)誤判可以接受那你可以判斷他是否有。下面給出本地實(shí)現(xiàn)和分布式實(shí)現(xiàn)蜕青。
ps 布隆過(guò)濾器最大的缺點(diǎn)就是 沒法刪除單獨(dú)的key為什么 因?yàn)槟銊h除了 你肯定就是把bit 設(shè)置成0 但是如果hash碰撞了 你設(shè)置成0了 就會(huì)影響其他的key了所以不能刪除
在一個(gè)就是誤判了 這個(gè)是我們可以預(yù)料到的。
1.本地布隆過(guò)濾器
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>20.0</version>
</dependency>
int expectedInsertions = 1000000; //預(yù)期插入多少個(gè)需要判斷的key
double fpp = 0.01; //錯(cuò)誤率 底層估計(jì)是 根據(jù)錯(cuò)誤率去算需要多少位 肯定錯(cuò)誤率越低占用內(nèi)存空間越大，估計(jì)還和hash算法有關(guān)
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), expectedInsertions, fpp);
//存數(shù)據(jù)
bloomFilter.put("hello");
bloomFilter.put("world");
//判斷是否存過(guò)數(shù)據(jù)
bloomFilter.mightContain("hello"); // true
bloomFilter.mightContain("world"); // true
bloomFilter.mightContain("test"); // false
2.分布式環(huán)境布隆過(guò)濾器
redission的實(shí)現(xiàn)
// 獲取布隆過(guò)濾器對(duì)象
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("bloom-filter");
// 初始化布隆過(guò)濾器等太，設(shè)置預(yù)計(jì)元素?cái)?shù)量和誤判率
bloomFilter.tryInit(10000, 0.03);
// 添加元素
bloomFilter.add("hello");
bloomFilter.add("world");
// 判斷元素是否存在
System.out.println(bloomFilter.contains("hello"));
System.out.println(bloomFilter.contains("redis"));
// 清空過(guò)濾器
bloomFilter.delete();
