Redis中Bloom filter布隆過濾器的學習

更新時間：2022年12月14日 10:09:13 作者：楓靈小宇

布隆過濾器是一個非常長的二進制向量和一系列隨機哈希函數(shù)的組合，可用于檢索一個元素是否存在，本文就詳細的介紹一下Bloom filter布隆過濾器，具有一定的參考價值，感興趣的可以了解一下

1.概念

? 布隆過濾器是一個高空間利用率的概率性數(shù)據結構，主要目的是節(jié)省內存空間以及判斷一個元素是否存在于一個集合中（存在誤判的情況），可以理解為一個不怎么精確的 set 結構，當你使用它的 contains 方法判斷某個對象是否存在時，它可能會誤判。但是布隆過濾器也不是特別不精確，只要參數(shù)設置的合理，它的精確度可以控制的相對足夠精確，只會有小小的誤判概率（控制參數(shù)：error_rate-誤判率 initial_size-初始容量）

? error_rate越小，越精確,需要的空間越大

? initial_size越大，越精確,當實際數(shù)量超出這個數(shù)值時，誤判率會上升

布隆過濾器可以判斷某個數(shù)據一定不存在，但是無法判斷一定存在

2.guava實現(xiàn)

2.1.依賴

<!--guava實現(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;
        // 計算bit數(shù)組長度
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        // 計算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;
    }
    /**
     * 計算bit數(shù)組長度
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            // 設定最小期望長度
            p = Double.MIN_VALUE;
        }
        int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
        return sizeOfBitArray;
    }
    /**
     * 計算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;
    /**
     * 根據給定的布隆過濾器添加值
     */
    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);
        }
    }
    /**
     * 根據給定的布隆過濾器判斷值是否存在
     */
    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實現(xiàn)

3.1.依賴

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>2.7.0</version>
</dependency>

3.2.注入或測試

 //單機模式：可以設置集群、哨兵模式
    @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;
    }

到此這篇關于Redis中Bloom filter布隆過濾器的學習的文章就介紹到這了,更多相關Redis布隆過濾器內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: