20-BloomFilter

1. hutool

import cn.hutool.bloomfilter.BitMapBloomFilter;


@Test
public void tmp() {
    // 初始化
    BitMapBloomFilter filter = new BitMapBloomFilter(10);
    filter.add("123");
    filter.add("abc");
    filter.add("ddd");

    // 查找
    filter.contains("abc")
}

2. google

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
    <scope>compile</scope>
</dependency>

@Test
public void bloomFilter() {
    // 存入的是字符串
    BloomFilter<CharSequence> bloomFilterStr = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100, 0.01);

    for (int i = 0; i < 100; i++) {
        bloomFilterStr.put("test" + i);
    }
    boolean containsValue1 = bloomFilterStr.mightContain("test1");
    boolean containsValue2 = bloomFilterStr.mightContain("test34");
    boolean containsValue3 = bloomFilterStr.mightContain("test1000001");
    System.out.println(containsValue1);
    System.out.println(containsValue2);
    System.out.println(containsValue3);
}

3. custom

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
    <scope>compile</scope>
</dependency>

package com.listao.redis.util;

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;
import com.google.common.primitives.Longs;

public class BloomFilterHelper<T> {

    private final int numHashFunctions;

    private final int bitSize;

    private final Funnel<T> funnel;

    public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
        Preconditions.checkNotNull(funnel);
        Preconditions.checkArgument(expectedInsertions >= 0L, "Expected insertions (%s) must be >= 0", expectedInsertions);
        Preconditions.checkArgument(fpp > 0.0D, "False positive probability (%s) must be > 0.0", fpp);
        Preconditions.checkArgument(fpp < 1.0D, "False positive probability (%s) must be < 1.0", fpp);
        this.funnel = funnel;
        // 计算bit数组长度
        bitSize = this.optimalNumOfBits(expectedInsertions, fpp);
        // 计算hash方法执行次数
        numHashFunctions = this.optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }

    public int[] murmurHashOffset32(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;
    }

    public long[] murmurHashOffset64(T value) {
        long[] offset = new long[numHashFunctions];
        byte[] bytes = Hashing.murmur3_128().hashObject(value, funnel).asBytes();
        long hash1 = this.lowerEight(bytes);
        long hash2 = this.upperEight(bytes);
        long combinedHash = hash1;

        for (int i = 0; i < numHashFunctions; ++i) {
            offset[i] = (combinedHash & 9223372036854775807L) % bitSize;
            combinedHash += hash2;
        }
        return offset;
    }

    /**
     * 计算bit数组长度
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            // 设定最小期望长度
            p = Double.MIN_VALUE;
        }
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    /**
     * 计算hash方法执行次数
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    private long lowerEight(byte[] bytes) {
        return Longs.fromBytes(bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]);
    }

    private long upperEight(byte[] bytes) {
        return Longs.fromBytes(bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]);
    }

}

/**
 * initBloomFilterHelper
 */
// @Bean(name = "BloomFilterHelper")
public BloomFilterHelper<String> initBloomFilterHelper() {
    return new BloomFilterHelper<>((Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8).putString(from, Charsets.UTF_8), 10000000, 0.01);
}

/**
 * bloomAdd
 *
 * @param bloomFilterHelper bloomFilterHelper
 * @param key               key
 * @param value             value
 */
public <T> void bloomAdd(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
    Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
    int[] offset = bloomFilterHelper.murmurHashOffset32(value);
    for (int i : offset) {
        stringRedisTemplate.opsForValue().setBit(key, i, true);
    }
}

/**
 * bloomInclude
 *
 * @param bloomFilterHelper bloomFilterHelper
 * @param key               key
 * @param value             value
 * @return boolean
 */
public <T> boolean bloomInclude(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
    Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
    int[] offset = bloomFilterHelper.murmurHashOffset32(value);
    for (int i : offset) {
        System.out.println("key : " + key + " " + "value : " + i);
        Boolean bit = stringRedisTemplate.opsForValue().getBit(key, i);
        if (bit == null || !bit) {
            return false;
        }
    }
    return true;
}