目录
布隆过滤器本质上是一种数据结构，是一种巧妙的概率型数据结构，用来高效的插入和查询，是用来告诉使用者某样东西一定不存在或者可能存在。使用多个哈希函数，将一个数据映射到位图结构中。例：
不了解位图吗？看这篇文章： http://t.csdn.cn/M5vmC
先来回顾哈希函数吧 ~
将任意的输入数据转换成特定的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。如图：
当我们存储海量数据时，哈希的空间效率很低，当只有一个哈希函数时，很容易发生哈希碰撞~
布隆过滤器是一个由固定大小的二进制向量或者位图和一系列映射函数所组成的。
在初始状态下，对于一个长度为m的位数组，所有位置0，如下：
当有变量被加入集合时，通过K个映射函数将这个变量映射成位图中的K个点，把它们置为1【举例中以3个映射函数为例】：
查询某个变量的时候，只要这些对应的点是否是都是1：
为什么说可能存在，而不是一定存在呢？
那是因为映射函数本身就是散列函数，散列函数就是会有碰撞哒~
布隆过滤器不能直接支持删除操作，因为在删除一个元素时，可能会影响其他元素
例：
当我们要删除obj1时，需要将4处置0，而此时obj2的hash3也是映射到4处，就会出现后续的查询有问题~
实现删除方案：
将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素是给计数器加一，删除元素时，减一【通过占用几倍存储空间来增加删除操作】
此方案的缺点：
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。
需要使用，套公式即可 ~
import java.util.BitSet;
class SimpleHash {
public int cap;//当前容量
public int seed;//随机
public SimpleHash(int cap,int seed) {
this.cap = cap;
this.seed = seed;
}
//模仿库中哈希写哈希函数：
//根据seed的不同，创建不同的哈希函数
int hash(String key) {
int h;
return (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));
}
}
public class MyBloomFilter {
//导入库中的位图
public BitSet bitSet;
//记录存储了多少数据
public int usedSize;
//随机种子
public static final int[] seeds = {3,5,9,11,15,19,25,31};//这里面的数字是随便设置的
public SimpleHash[] simpleHashes;
public static final int SIZE = 1 << 20;//这个20是随意给的
public MyBloomFilter() {
bitSet = new BitSet(SIZE);
simpleHashes = new SimpleHash[seeds.length];
for(int i = 0;i<simpleHashes.length;i++) {
simpleHashes[i] = new SimpleHash(SIZE,seeds[i]);
}
}
/**
* 添加数据 到布隆过滤器
* @param val
*/
public void add(String val) {
//3个哈希函数，分别处理当前的数据
//把他们都存储在位图中即可
}
/**
* 是否包含val，会存在误判
* @param val
* @return
*/
public boolean contains(String val) {
}
}
补充上述代码空缺部分：
/**
* 添加数据 到布隆过滤器
* @param val
*/
public void add(String val) {
//3个哈希函数，分别处理当前的数据
for (SimpleHash simpleHash : simpleHashes) {
int index = simpleHash.hash(val);
//把他们都存储在位图中即可
bitSet.set(index);
}
usedSize ++;
} /**
* 是否包含val，会存在误判
* @param val
* @return
*/
public boolean contains(String val) {
for (SimpleHash simpleHash : simpleHashes) {
int index = simpleHash.hash(val);
boolean flg = bitSet.get(index);
if(!flg) {
return false;
}
}
return true;
} //测试
public static void main(String[] args) {
MyBloomFilter myBloomFilter = new MyBloomFilter();
myBloomFilter.add("baidu1");
myBloomFilter.add("baidu2");
myBloomFilter.add("tencent");
System.out.println(myBloomFilter.contains("baidu1"));//true
System.out.println(myBloomFilter.contains("haha"));//false
}依赖：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency>测试：
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class Test {
private static int size = 1000000;//预计要插入多少数据
private static double fpp = 0.01;//期望的误判率
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
//插入数据
for (int i = 0; i < 1000000; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "误判了");
}
}
System.out.println("总共的误判数:" + count);
}
}
测试结果：
好啦！！！我们下期再见咯~