目录

一、面试题

二、位图概念 

三、模拟实现位图

 四、Java封装好的位图

五、位图的应用

 六、布隆过滤器

布隆过滤器的提出

布隆过滤器概念

布隆过滤器的插入

布隆过滤器的查找

七、布隆过滤器模拟实现

八、布隆过滤器优点

九、布隆过滤器缺点

十、布隆过滤器应用场景

---

一、面试题

给四十亿个无符号整型，没排过序，给定一个无符号整数，如何快速判断这个数是否在这四十亿个数据中？

1.遍历    时间复杂度O（N）。

2.排序+二分查找    排序时间复杂度O(NlogN)+二分查找时间复杂度O(logN)

二、位图概念 

三、模拟实现位图

import java.util.Arrays;

public class MyBitSet {
    public byte[] elem;
    public int CapCity;
    public MyBitSet() {
        elem=new byte[1];
    }
    public MyBitSet(int n) {
        elem=new byte[n/8+1];
    }

    /**
     * 添加元素到位图
     * @param val
     */
    public void set(int val) {
        if(val<0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        int ArrayIndex=val/8;
        int BitIndex=val%8;
        if(ArrayIndex>elem.length-1) {
            elem = Arrays.copyOf(elem,ArrayIndex+1);
        }
        elem[ArrayIndex]|=(1<<BitIndex);
        CapCity++;
    }

    /**
     * 判断位图中是否存在该元素
     * @param val
     * @return
     */
    public boolean get(int val) {
        if(val<0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        int ArrayIndex=val/8;
        int BitIndex=val%8;
        if(ArrayIndex>elem.length-1) {
            elem = Arrays.copyOf(elem,ArrayIndex+1);
        }
        if((elem[ArrayIndex]&=(1<<BitIndex))!=0) {
            return true;
        }
        return false;
    }

    /**
     * 重置
     * @param val
     */
    public void reSet(int val) {
        if(val<0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        int ArrayIndex=val/8;
        int BitIndex=val%8;
        if(ArrayIndex>elem.length-1) {
            elem = Arrays.copyOf(elem,ArrayIndex+1);
        }
        elem[ArrayIndex]&=~(1<<BitIndex);
        CapCity--;
    }
    public int getCapCity() {
        return CapCity;
    }
}

可以在主函数测试一下我们简单模拟实现的位图

public class Main {
    public static void main(String[] args) {
        int[] array={1,3,2,5,6,7,8};
        MyBitSet set=new MyBitSet();
        for (int i = 0; i < array.length; i++) {
            set.set(array[i]);
        }
        System.out.println(set.get(6));
        System.out.println(set.getCapCity());
        set.reSet(6);
        System.out.println(set.get(6));
    }
}

运行结果如下： 

true
7
false

进程已结束，退出代码为 0

 四、Java封装好的位图

我们Java自己有封装好的位图BitSet具体使用方法我们可以查阅Java文档BitSet （Java SE 21 & JDK 21）。

五、位图的应用

 六、布隆过滤器

布隆过滤器的提出

布隆过滤器概念

布隆过滤器的插入

比如向布隆过滤器插入“baidu”：

布隆过滤器的查找

七、布隆过滤器模拟实现

import java.util.BitSet;


class SimpleHash {
    public int cap; //当前容量
    public int seed; //随机数
    public SimpleHash(int cap,int seed){
        this.cap=cap;
        this.seed=seed;
    }
    //哈希函数
    public int hash(String key){
        int h;
        return  (key == null) ? 0 :(seed*cap-1) & (h = key.hashCode()) ^ (h >>> 16);
    }

}
public class MyBloomFilter {
    public static final int FINAL_SIZE=1<<20;
    //位图
    BitSet set;
    //记录了多少个数据
    int UsedSize;
    SimpleHash[] hash;
    //随机数数组
    public static final int[] seeds={9,22,3,4,55,6,77};
    public MyBloomFilter() {
        set=new BitSet(FINAL_SIZE);
        hash=new SimpleHash[seeds.length];
        for (int i = 0; i < seeds.length; i++) {
            hash[i]=new SimpleHash(FINAL_SIZE,seeds[i]);
        }
    }

    /**
     * 添加元素到布隆过滤器
     * @param val
     */
    public void add(String val) {
        for (int i = 0; i < hash.length; i++) {
           int x=hash[i].hash(val);
           set.set(x);
        }
    }

    /**
     * 检查元素是否存在
     * @param val
     * @return
     */
    public boolean contains(String val){
        for (int i = 0; i < hash.length; i++) {
            int x=hash[i].hash(val);
            if(!set.get(x)){
                return false;
            }
        }
        return true;
    }
}

 同样的我们可以在main函数钟测试我们简单实现的布隆过滤器

class Main{
    public static void main(String[] args) {
        MyBloomFilter bloomFilter=new MyBloomFilter();
        bloomFilter.add("hello");
        System.out.println(bloomFilter.contains("hello"));
        System.out.println(bloomFilter.contains("he"));
    }
}

运行结果如下：

true
false

进程已结束，退出代码为 0

八、布隆过滤器优点

九、布隆过滤器缺点

十、布隆过滤器应用场景