感觉要理解布隆过滤器，需要从二叉树说起
平衡二叉树的性质：可以已logn的速度进行搜索，但由于二叉树是要保存key和value，及时使用set，也是需要保存key的，那么如果数据量巨大的时候，比如上亿的数据量，这时候如果在查询的时候，用二叉搜索树，就需要将其都加载到内存中，内存就会爆掉
布隆过滤器就解决了上述问题，可以不用那么多的内存空间，实现数据的查询，但他的查询是有一定局限性的，只能在指定的场景下使用：如果要经常判断 1 个元素是否存在
它是一个空间效率高的概率型数据结构，可以用来告诉你：一个元素一定不存在或者可能存在
优缺点
优点：空间效率和查询时间都远远超过一般的算法
缺点：有一定的误判率、删除困难
它实质上是一个很长的二进制向量和一系列随机映射函数（Hash函数）
常见应用：网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题
实现原理：由 m个位二进制、k个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置
添加元素：将每一个哈希函数生成的索引位置都设为 1
查询元素是否存在：
????????如果有一个哈希函数生成的索引位置不为 1，就代表不存在（100%准确）
????????如果每一个哈希函数生成的索引位置都为 1，就代表存在（存在一定的误判率）
添加、查询的时间复杂度都是：O(k) ，k 是哈希函数的个数。空间复杂度是：O(m) ，m 是二进制位的个数
布隆过滤器的误判率：
误判率 p 受 3 个因素影响：二进制位的个数 m、哈希函数的个数 k、数据规模 n
?
已知误判率 p、数据规模 n，求二进制位的个数 m、哈希函数的个数 k
?
public class BloomFilter<T> {
/**
* 二进制向量的长度(一共有多少个二进制位)
*/
private int bitSize;
/**
* 二进制向量
*/
private long[] bits;
/**
* 哈希函数的个数
*/
private int hashSize;
/**
* @param n 数据规模
* @param p 误判率, 取值范围(0, 1)
*/
public BloomFilter(int n, double p) {
if (n <= 0 || p <= 0 || p >= 1) {
throw new IllegalArgumentException("wrong n or p");
}
double ln2 = Math.log(2);
// 求出二进制向量的长度
bitSize = (int) (- (n * Math.log(p)) / (ln2 * ln2));
// 求出哈希函数的个数
hashSize = (int) (bitSize * ln2 / n);
// bits数组的长度
bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
// 每一页显示100条数据, pageSize
// 一共有999999条数据, n
// 请问有多少页 pageCount = (n + pageSize - 1) / pageSize
}
/**
* 添加元素1
*/
public boolean put(T value) {
nullCheck(value);
// 利用value生成2个整数
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
boolean result = false;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 生成一个二进位的索引
int index = combinedHash % bitSize;
// 设置index位置的二进位为1
if (set(index)) result = true;
// 101010101010010101
// | 000000000000000100 1 << index
// 101010111010010101
}
return result;
}
/**
* 判断一个元素是否存在
*/
public boolean contains(T value) {
nullCheck(value);
// 利用value生成2个整数
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 生成一个二进位的索引
int index = combinedHash % bitSize;
// 查询index位置的二进位是否为0
if (!get(index)) return false;
}
return true;
}
/**
* 设置index位置的二进位为1
*/
private boolean set(int index) {
long value = bits[index / Long.SIZE];
int bitValue = 1 << (index % Long.SIZE);
bits[index / Long.SIZE] = value | bitValue;
return (value & bitValue) == 0;
}
/**
* 查看index位置的二进位的值
* @return true代表1, false代表0
*/
private boolean get(int index) {
long value = bits[index / Long.SIZE];
return (value & (1 << (index % Long.SIZE))) != 0;
}
private void nullCheck(T value) {
if (value == null) {
throw new IllegalArgumentException("Value must not be null.");
}
}
}
