一、布隆过滤器是什么？

它是一种概率型数据结构，特点是高效的插入和查询，作用是可以告诉你“某个数据一定不存在，或是可能存在”，原理是通过多个哈希函数，将一个数据映射到位图中，好处是不仅提高了查询效率，也可以节省大量的内存空间，底层相当于 哈希+位图；

解读：为什么能知道“某样东西一定不存在，或者可能存在”？

哈希冲突。因为他的原理是通过多个哈希函数来进行映射，好比我要存放两个字符串，有可能，这两个字符串经过哈希函数计算，映射到的位置正好相同，如下图：

但是，不难理解的一点是，假设有三个哈希函数进行哈希，那么如果我要查找某一个字符串，是否一定不存在，那么一定是肯定的，因为三个位置上只要有一个不为1，就说明要查找的这个字符串一定不存在；

PS：

1.一般使用布隆过滤器来说，是会给定一个误判率的；

2.布隆过滤器没有存储当前的数据（如上图）；

二、布隆过滤器的模拟实现

2.1、模拟实现

这里的逻辑实现太简单了，就不展开论述了，对于添加和查找功能，就是通过不同的哈希函数进行哈希来存入或查找不同元素，查找元素时，一旦有一个数值经过哈希函数无法在位图中找到，就说明一定不存在；

代码如下：

class SimpleHash {public int cap;//容量public int seed;//随机public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}/*** 根据seed的不同，创建不同点哈希函数* @param key* @return*/int hash(String key) {int h;return (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));}}
public class MyBloomFilter {//bitSet的初始化大小public static final int DEFAULT_SIZE = 1 << 20;//位图public BitSet bitSet;//记录存储的数据数量public int usedSize;public static final int[] seeds = {3,5,12,6,24,32};public SimpleHash[] simpleHashes;public MyBloomFilter() {bitSet = new BitSet(DEFAULT_SIZE);//创建哈希函数simpleHashes = new SimpleHash[seeds.length];for(int i = 0; i < simpleHashes.length; i++) {simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);}}/*** 添加元素到布隆过滤器* @param val*/public void add(String val) {//让每个哈希函数分别处理当前数据，并存入位图中for(int i = 0; i < simpleHashes.length; i++) {bitSet.set(simpleHashes[i].hash(val));}}/*** 是否包含val,这里会存在一定的误判* @param val 一定是通过这几个哈希函数看对应的位置* @return*/public boolean contains(String val) {//只要有1个为0 那么一定不存在for(int i = 0; i < simpleHashes.length; i++) {if(!bitSet.get(simpleHashes[i].hash(val))) {return false;}}return true;}//测试public static void main(String[] args) {MyBloomFilter myBloomFilter = new MyBloomFilter();myBloomFilter.add("hello");myBloomFilter.add("hello2");myBloomFilter.add("hello3");myBloomFilter.add("hehe");myBloomFilter.add("haha");System.out.println(myBloomFilter.contains("hello4"));}
}