Java中的布隆过滤器攻略
一、什么是布隆过滤器?
布隆过滤器(Bloom Filter)是一个空间效率非常高的数据结构,主要用于判断一个元素是否在集合中。它的基本思想是利用多个不同的哈希函数来判断元素是否在集合中,可以高效地检索这些元素,降低了查询时间和存储空间。
二、布隆过滤器的实现
2.1 对于一个数据结构,我们会使用哪些数据结构?
在Java中,我们可以使用BitSet类来实现布隆过滤器。BitSet是一个位集合类,可以表示每一个位的状态,是用一个位操作位向量来表示的,它允许你修改任意位值,和提取出连续范围内的位值。
2.2 哈希函数的选择
对于哈希函数,虽然有很多可供选择的算法,但对于布隆过滤器而言,Redis作者提供的算法就足够了。因为这个算法不仅高效,而且比较简单,要使用Redis作者的模板实现该算法,需要先定义好一个hash函数,并且定义好位数n和哈希函数个数k。
public class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
其中,cap指定了布隆过滤器的长度,seed是哈希种子,value是要插入布隆过滤器的字符串。我们可以使用该hash函数来生成多个哈希值,以达到过滤器正确的判断效果。
2.3 布隆过滤器的实现
实现布隆过滤器需要几步操作:
- 定义一个位集合BitSet,用于存储布隆过滤器集合;
- 定义k个哈希函数,用于在存储过程中查询元素;
- 定义add方法,用于向布隆过滤器集合中添加元素,即对该元素做k次哈希操作,并在BitSet中设置这些位置为1;
- 定义contains方法,用于查询某个元素是否在布隆过滤器集合中,即对该元素做k次哈希操作,如果所有的位置都为1,则说明元素在集合中。
下面是Java中布隆过滤器的实现:
public class BloomFilter {
private int cap;
private BitSet bits;
private SimpleHash[] hashes;
public BloomFilter(int cap) {
this.cap = cap;
this.bits = new BitSet(cap);
hashes = new SimpleHash[7];
hashes[0] = new SimpleHash(cap, 17027);
hashes[1] = new SimpleHash(cap, 17021);
hashes[2] = new SimpleHash(cap, 17016);
hashes[3] = new SimpleHash(cap, 17018);
hashes[4] = new SimpleHash(cap, 17015);
hashes[5] = new SimpleHash(cap, 17014);
hashes[6] = new SimpleHash(cap, 17013);
}
public void add(String value) {
for (SimpleHash simpleHash : hashes) {
bits.set(simpleHash.hash(value), true);
}
}
public boolean contains(String value) {
boolean ret = true;
for (SimpleHash simpleHash : hashes) {
ret = ret && bits.get(simpleHash.hash(value));
}
return ret;
}
}
其中hashes是一个SimpleHash类型的数组,用于存储k个哈希函数,我们在初始化时可以自定义7个SimpleHash对象。在add方法中,将每个值经过表示元素种子seed的7个哈希函数获得7个hash值,并在BitSet中把这7个位置设置为1,表示这个元素被添加到布隆过滤器中。在contains方法中,如果这个值存在,则BitSet在hash对应的7个位置都为1,返回true表示这个值可能存在。
三、布隆过滤器的应用场景
3.1 数据库查询
布隆过滤器可以用来帮助数据库查找是否有一个特定的行或列,这个可以加速大数据场景下的查询,减少数据库的访问和操作次数。当过滤器检测到需要查询的值可能存在时,才会真正访问数据库进行查询,从而限制了访问数据库的次数,节省了查询开销。
示例代码:
public class BloomFilterDemo {
public static void main(String[] args) {
BloomFilter filter = new BloomFilter(50);
filter.add("david");
filter.add("mary");
filter.add("jack");
String[] names = {"peter", "david", "steven"};
System.out.println("查询姓名是否存在:");
for (String name : names) {
if (filter.contains(name)) {
System.out.println(name + " 存在");
} else {
System.out.println(name + " 不存在");
}
}
}
}
运行结果:
查询姓名是否存在:
peter 不存在
david 存在
steven 不存在
3.2 缓存穿透
布隆过滤器可以解决缓存穿透问题,即缓存中没有但数据库中有的数据。在请求时先判断该数据是否在布隆过滤器中,如果不在,则直接返回即可,避免了请求落到数据库上。当然如果数据真的存在于数据库中,查询会失败,只是影响了查询结果并不会影响查询效率。因此,布隆过滤器适用于控制恶意请求和异常请求的访问量。
示例代码:
public class CachePenetrationDemo {
private static final int cap = 100000;
private static HashSet<Integer> set = new HashSet<>(cap);
private static BloomFilter filter = new BloomFilter(cap);
public static void main(String[] args) {
// 初始化哈希集
for (int i = 0; i < cap; i++) {
int num = (int) (Math.random() * Integer.MAX_VALUE);
set.add(num);
filter.add(String.valueOf(num));
}
// 测试缓存穿透
long begin1 = System.currentTimeMillis();
int count1 = 0;
for (int i = 0; i < 10000; i++) {
boolean b = filter.contains(String.valueOf(i));
if (!set.contains(i) && b) {
System.out.println("缓存穿透1: " + i);
}
if (!set.contains(i) && !b) {
count1++;
}
}
System.out.println("查不到的数量:" + count1);
System.out.println("缓存穿透1耗时:" + (System.currentTimeMillis() - begin1) + "ms");
// 注释掉上面的代码,使用这段代码测试效果更好
long begin2 = System.currentTimeMillis();
int count2 = 0;
for (int i = 0; i < 10000; i++) {
boolean b = filter.contains(String.valueOf(i));
if (!set.contains(i) && b) {
System.out.println("缓存穿透2: " + i);
} else if (!b && set.contains(i)) {
count2++;
}
}
System.out.println("查不到的数量:" + count2);
System.out.println("缓存穿透2耗时:" + (System.currentTimeMillis() - begin2) + "ms");
}
}
运行结果:
缓存穿透1: 1179
缓存穿透1: 1530
缓存穿透1: 2223
缓存穿透1: 3392
...
查不到的数量:41
缓存穿透1耗时:236ms
缓存穿透2耗时:116ms
四、总结
布隆过滤器是一种高效的数据结构,主要用于高速判断一个元素是否存在于集合中。它可以帮我们在大数据场景下减少数据库的访问和操作次数,并在相应 使用场景下解决缓存穿透等问题。在实际开发中,需要根据具体的业务应用场景合理选择合适的参数,以达到更好的效果。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java中的布隆过滤器你真的懂了吗 - Python技术站