当前位置:   article > 正文

布隆过滤器的简易实现_登录动作布隆过滤

登录动作布隆过滤

布隆过滤器的原理再此就不重复说了,网上有很多种陈述的,再此就利用BitSet给出一个布隆过滤器的简易实现,

看不懂的欢迎私信我

 

import java.util.BitSet;

/**
 * @author zoujianglin
 * @date 2018/8/9 9:27
 */
public class SimpleBloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24;
    private static final int[] seeds = new int[]{7, 11, 13, 31, 37, 61,}; //种子,即使用六位来决定一个数是否存在
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public SimpleBloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    /**
     * 添加值 
     * @param value
     */
    public void add(String value) {
        for (SimpleHash f : func) {//将每个所得的hash对应得bits位置为true
            bits.set(f.hash(value), true);
        }

    }

    /**
     * 判断是否包含指定的值
     * @param value
     * @return
     */
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) { //遍历,该value对应得值是否都在bitset
            ret = ret && bits.get(f.hash(value));
        }

        return ret;
    }


    public static class SimpleHash { //利用种子,获取一个数值一个对应的hash位
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;

        }

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }

    }


}
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/763107
推荐阅读
相关标签
  

闽ICP备14008679号