redisベースのBloomFilter

GoogleのguavaフレームワークはBloomFilterを実現していることが知られており、guavaのBloomFilterとredisのbitMapはいずれもビットマップアルゴリズムに基づいているので、redisはBloomFilterを実現することもでき、BloomFilterに対してredisのデータは3つのredisサーバ上に存在し、guavaのBloomFilterとは異なりローカルに存在する.これはメモリ損失や分散システムには明らかに適切ではないので、今日はredisベースのBloomFilterを共有します(redisのbitmap-を見たほうがいいです.https://blog.csdn.net/u012888052/article/details/80380143).
直接コード:

@ConfigurationProperties("bloom.filter")
@Component
public class RedisBloomFilter {

    //     
    private long expectedInsertions;

    //       
    private double fpp;

    @Autowired
    private RedisTemplate redisTemplate;


    //bit    
    private long numBits;
    //hash    
    private int numHashFunctions ;

    public long getExpectedInsertions() {
        return expectedInsertions;
    }

    public void setExpectedInsertions(long expectedInsertions) {
        this.expectedInsertions = expectedInsertions;
    }

    public void setFpp(double fpp) {
        this.fpp = fpp;
    }

    public double getFpp() {
        return fpp;
    }

    @PostConstruct
    public void init(){
        this.numBits = optimalNumOfBits(expectedInsertions, fpp);
        this.numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    }

    //  hash    
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    //  bit    
    private long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    /**
     *   keys       
     */
    public boolean isExist(String key) {
        long[] indexs = getIndexs(key);
        List list = redisTemplate.executePipelined(new RedisCallback

yml構成:

bloom:
    filter:
      expectedInsertions: 1000
      fpp: 0.001F

大まかな流れは次のとおりです.
1:推定挿入量および許容誤り率からbit配列長およびhash関数数を算出する.
2:key値hashを、hash関数の数に基づいて、key値を一致させるために、このkeyの異なる下付き配列を計算します.
3:key値の下付き文字を巡り、同じ値(bf:hilite)を下付き文字の値に基づいて、下付き文字の長さに対応するバイナリ数に変換してbitmapに格納します.
4:判定の場合、keyを同じように下付き配列に変換し、getBit()メソッドで存在するか否かを判定します.
コードを見てもhash関数数numHashFunctionsは予想挿入量expectedInsertionsに関係なく許容可能な誤り率fppに反比例し,bit配列長numBitsは予想挿入量expectedInsertionsに比例し,許容可能な誤り率fppに反比例することが分かる.