欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

记一次面试被问到的布隆过滤器(能不能叫布罗姆过滤器...) 如何代码简单实现

程序员文章站 2022-04-15 17:56:32
先贴代码,注释挺全的,后续写一点解释,不过好像也解释不太出啥来。。package com.project.test;import java.util.BitSet;public class BloomFilter { //初始化位数组时的大小 private static int INITIAL_CAPACITY = 2 << 24; //构造哈希函数的种子数组 private static int[] seeds = {8,18,28,38};...

先贴代码,注释挺全的,后续写一点解释,不过好像也解释不太出啥来。。

package com.project.test;

import java.util.BitSet;

public class BloomFilter {

    //初始化位数组时的大小
    private static int INITIAL_CAPACITY = 2 << 24;
    //构造哈希函数的种子数组
    private static int[] seeds = {8,18,28,38};
    //用默认大小初始化一个位数组
    private BitSet bitSet = new BitSet(INITIAL_CAPACITY);
    //私有一个哈希函数数组
    private HashFunction[] hashFunctions = new HashFunction[seeds.length];
    //构造函数时,填充哈希数组
    public BloomFilter(){
        for (int i = 0; i < seeds.length; i++) {
            hashFunctions[i] = new HashFunction(seeds[i],INITIAL_CAPACITY);
        }
    }

    /**
     * 向位数组里添加某个字符串
     * @param value 待添加的字符串
     * @return true 如果添加成功 false 则添加失败
     */
    public boolean add(String value){
        //value为null,直接false
        if (value == null){
            return false;
        }
        try {
            //遍历哈希函数数组,用每个函数映射一遍value得到位数组索引
            for (int i = 0; i < hashFunctions.length; i++) {
                int index = hashFunctions[i].hash(value);
                //将位数组对应索引置为true/false
                bitSet.set(index,true);
            }
            return true;
        } catch (Exception e) {
            e.printStackTrace();
            return false;
        }
    }

    /**
     * 判断某个字符串是否在位数组里
     * @param value 带判断的字符串
     * @return true 字符串(可能!)已经存在位数组中 false 字符串一定不存在位数组中
     */
    public boolean contains(String value){
        //value为null,直接false
        if (value == null){
            return false;
        }
        for (int i = 0; i < hashFunctions.length; i++) {
            int index = hashFunctions[i].hash(value);
            //拿到对应索引true/false
            boolean temp = bitSet.get(index);
            //有一个false,直接返回,肯定不在
            if (!temp){
                return false;
            }
        }
        return true;
    }

    /**
     *  静态内部类
     *  用于定义函数,计算哈希,压缩哈希,得到索引
     */
    private static class HashFunction{
        //种子
        private int seed;
        //位数组容量 INITIAL_CAPACITY
        private int capacity;
        //构造哈希函数
        public HashFunction() {
        }
        public HashFunction(int seed, int capacity) {
            this.seed = seed;
            this.capacity = capacity;
        }

        /**
         * 计算哈希值,压缩哈希值得到索引
         * @param value 待计算的字符串
         * @return
         */
        private int hash(String value){
            //遍历字符串每个字符,计算哈希值
            int result = 0;
            for (int i = 0; i < value.length(); i++) {
                result = seed * result + value.charAt(i);
            }
            //压缩哈希值到索引
            //result为长哈希值,压缩
            //当N为2的整数次幂时,result对N取余 result % N 等价于 result & (N - 1)
            result = result & (capacity - 1);
            return result;
        }
    }

    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter();
        System.out.println(bf.contains("苹果"));
        System.out.println(bf.contains("香蕉"));
        System.out.println(bf.contains("橘子"));
        System.out.println(bf.contains("蛋糕"));
        System.out.println(bf.contains("巧克力"));
        System.out.println("+++++++++++++++++++++++");
        bf.add("苹果");
        bf.add("香蕉");
        bf.add("橘子");
        bf.add("蛋糕");
        bf.add("巧克力");
        System.out.println(bf.contains("苹果"));
        System.out.println(bf.contains("香蕉"));
        System.out.println(bf.contains("橘子"));
        System.out.println(bf.contains("蛋糕"));
        System.out.println(bf.contains("巧克力"));
        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        System.out.println(bf.contains("车子"));
        System.out.println(bf.contains("曼联"));
        System.out.println(bf.contains("切尔西"));
        System.out.println(bf.contains("渣团"));
        System.out.println(bf.contains("拜仁"));
        System.out.println("@@@@@@@@@@@@@@@@@@@@@@@@");

    }

}

 

本文地址:https://blog.csdn.net/weixin_40821240/article/details/109819134