Redis中Bloom filter布隆過濾器的學(xué)習(xí)
1.概念
? 布隆過濾器是一個(gè)高空間利用率的概率性數(shù)據(jù)結(jié)構(gòu),主要目的是節(jié)省內(nèi)存空間以及判斷一個(gè)元素是否存在于一個(gè)集合中(存在誤判的情況),可以理解為一個(gè)不怎么精確的 set 結(jié)構(gòu),當(dāng)你使用它的 contains 方法判斷某個(gè)對(duì)象是否存在時(shí),它可能會(huì)誤判。但是布隆過濾器也不是特別不精確,只要參數(shù)設(shè)置的合理,它的精確度可以控制的相對(duì)足夠精確,只會(huì)有小小的誤判概率(控制參數(shù):error_rate-誤判率 initial_size-初始容量)
? error_rate越小,越精確,需要的空間越大
? initial_size越大,越精確,當(dāng)實(shí)際數(shù)量超出這個(gè)數(shù)值時(shí),誤判率會(huì)上升
布隆過濾器可以判斷某個(gè)數(shù)據(jù)一定不存在,但是無法判斷一定存在
2.guava實(shí)現(xiàn)
2.1.依賴
<!--guava實(shí)現(xiàn)布隆過濾器--> <dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>19.0</version> </dependency>
2.2.初始化布隆過濾器
//初始化布隆過濾器,放入到spring容器里面 @Bean public MyBloomFilter<String> initBloomFilterHelper() { return new MyBloomFilter<>((Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8).putString(from, Charsets.UTF_8) , 1000000, 0.01); }
2.3.布隆過濾器
package com.qin.redis.bloomfilter; import com.google.common.base.Preconditions; import com.google.common.hash.Funnel; import com.google.common.hash.Hashing; /** * @version: V1.0.0 * @className: MyBloomFilter */ public class MyBloomFilter<T> { private int numHashFunctions; private int bitSize; private Funnel<T> funnel; public MyBloomFilter(Funnel<T> funnel, int expectedInsertions, double fpp) { Preconditions.checkArgument(funnel != null, "funnel不能為空"); this.funnel = funnel; // 計(jì)算bit數(shù)組長(zhǎng)度 bitSize = optimalNumOfBits(expectedInsertions, fpp); // 計(jì)算hash方法執(zhí)行次數(shù) numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize); } public int[] murmurHashOffset(T value) { int[] offset = new int[numHashFunctions]; long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong(); int hash1 = (int) hash64; int hash2 = (int) (hash64 >>> 32); for (int i = 1; i <= numHashFunctions; i++) { int nextHash = hash1 + i * hash2; if (nextHash < 0) { nextHash = ~nextHash; } offset[i - 1] = nextHash % bitSize; } return offset; } /** * 計(jì)算bit數(shù)組長(zhǎng)度 */ private int optimalNumOfBits(long n, double p) { if (p == 0) { // 設(shè)定最小期望長(zhǎng)度 p = Double.MIN_VALUE; } int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); return sizeOfBitArray; } /** * 計(jì)算hash方法執(zhí)行次數(shù) */ private static int optimalNumOfHashFunctions(long n, long m) { int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2))); return countOfHash; } public static void main(String[] args) { System.out.println(optimalNumOfHashFunctions(1000000000L, 123450000L)); } }
2.4.添加元素或者判斷是否存在
package com.qin.redis.bloomfilter.service; import com.google.common.base.Preconditions; import com.hikvison.aksk.redis.bloomfilter.MyBloomFilter; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.data.redis.core.RedisTemplate; import org.springframework.stereotype.Service; /** * @version: V1.0.0 * @className: RedisBloomFilterService */ @Service public class RedisBloomFilterService { @Autowired private RedisTemplate redisTemplate; /** * 根據(jù)給定的布隆過濾器添加值 */ public <T> void addByBloomFilter(MyBloomFilter<T> bloomFilterHelper, String key, T value) { Preconditions.checkArgument(bloomFilterHelper != null, "myBloomFilter不能為空"); int[] offset = bloomFilterHelper.murmurHashOffset(value); for (int i : offset) { System.out.println("key : " + key + " " + "value : " + i); redisTemplate.opsForValue().setBit(key, i, true); } } /** * 根據(jù)給定的布隆過濾器判斷值是否存在 */ public <T> boolean includeByBloomFilter(MyBloomFilter<T> bloomFilterHelper, String key, T value) { Preconditions.checkArgument(bloomFilterHelper != null, "myBloomFilter不能為空"); int[] offset = bloomFilterHelper.murmurHashOffset(value); for (int i : offset) { System.out.println("key : " + key + " " + "value : " + i); if (!redisTemplate.opsForValue().getBit(key, i)) { return false; } } return true; } }
3.Redisson實(shí)現(xiàn)
3.1.依賴
<dependency> <groupId>org.redisson</groupId> <artifactId>redisson</artifactId> <version>2.7.0</version> </dependency>
3.2.注入或測(cè)試
//單機(jī)模式:可以設(shè)置集群、哨兵模式 @Bean public Redisson redisson() { Config config = new Config(); config.useSingleServer().setAddress("redis://127.0.0.1:6379"); RedissonClient redissonClient = Redisson.create(config); //初始化過濾器 RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter("testBloomFilter"); bloomFilter.tryInit(1000000L,0.05); //插入元素 bloomFilter.add("zhangsan"); bloomFilter.add("lisi"); //判斷元素是否存在 boolean flag = bloomFilter.contains("lisi"); return (Redisson) redissonClient; }
到此這篇關(guān)于Redis中Bloom filter布隆過濾器的學(xué)習(xí)的文章就介紹到這了,更多相關(guān)Redis布隆過濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
將MongoDB作為Redis式的內(nèi)存數(shù)據(jù)庫(kù)的使用方法
這篇文章主要介紹了將MongoDB作為Redis式的內(nèi)存數(shù)據(jù)庫(kù)的使用方法,原理其實(shí)只是將內(nèi)存虛擬作為磁盤,需要的朋友可以參考下2015-06-06手動(dòng)實(shí)現(xiàn)Redis的LRU緩存機(jī)制示例詳解
這篇文章主要介紹了手動(dòng)實(shí)現(xiàn)Redis的LRU緩存機(jī)制示例詳解,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-03-03通俗易懂的Redis數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程(入門)
這篇文章主要介紹了通俗易懂的Redis數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03