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

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

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