电子商务网站建设流程图,建设工程许可证在那个网站办,济南网站建设山东酷风,北京市工商注册网上服务系统1.背景
为预防大量黑客故意发起非法的时间查询请求#xff0c;造成缓存击穿#xff0c;建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数#xff08;哈希函数#xff09;来记录与识别某个数据是否在一个集合中。如果数据不在集合中…1.背景
为预防大量黑客故意发起非法的时间查询请求造成缓存击穿建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数哈希函数来记录与识别某个数据是否在一个集合中。如果数据不在集合中能被识别出来不需要到数据库中进行查询所以能将数据库查询返回值为空的查询过滤掉。 缓存穿透 缓存穿透是查询一个根本不存在的数据由于缓存是不命中时需要从数据库查询这将导致这个不存在的数据每次请求都要到数据库去查询进而给数据库带来压力。
2.布隆过滤器介绍
1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列的随机映射函数哈希函数两部分组成的数据结构。 用途 用于检索一个元素是否在一个集合中。 优点 时间复杂度低增加及查询元素的时间复杂度都是O(k)k为Hash函数的个数 占用存储空间小布隆过滤器相对于其他数据结构如Set、Map非常节省空间。 缺点 存在误判只能证明一个元素一定不存在或者可能存在返回结果是概率性的但是可以通过调整参数来降低误判比例 删除困难一个元素映射到bit数组上的k个位置为1删除的时候不能简单的直接置为0可能会影响到其他元素的判断。
3.原理
当一个元素加入布隆过滤器中的时候会进行如下操作
使用布隆过滤器中的哈希函数对元素进行计算得到哈希值有几个哈希函数得到几个哈希值。 根据得到的哈希值在位数组中把对应下标的值置为1。 当我们需要判断一个元素是否位于布隆过滤器的时候会进行如下操作
对给定元素再次进行相同的哈希计算 得到值之后判断位数组中的每个元素是否都为1如果值都为1那么说明这个值在布隆过滤器中如果存在一个值不为1说明该元素不在布隆过滤器中。 举个例子 如图所示当字符串存储要加入到布隆过滤器中时该字符串首先由多个哈希函数生成不同的哈希值然后将对应的位数组的下标设置为1当位数组初始化时所有位置均为 0。当第二次存储相同字符串时因为先前的对应位置已设置为 1所以很容易知道此值已经存在去重非常方便。 如果我们需要判断某个字符串是否在布隆过滤器中时只需要对给定字符串再次进行相同的哈希计算得到值之后判断位数组中的某个元素是否都为1如果值都为1那么说明这个值在布隆过滤器中如果存在一个值不为1说明该元素不在布隆过滤器中。 不同的字符串可能哈希出来的位置相同这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。
综上布隆过滤器说某个元素存在小概率会误判。布隆过滤器说某个元素不存在那么这个元素一定不在。
4.使用场景
4.1判断给定数据是否存在 比如判断一个数字是否在于包含大量数字的数字集中数字集很大5亿以上、防止缓存穿透判断请求的数据是否有效避免直接绕过缓存请求数据库、邮箱的垃圾邮件过滤、黑名单功能等。 4.2去重 爬给定网址的时候对已经爬取过的URL去重。
5.代码实现
5.1Java实现
package com.fandf.test.redis;import java.util.BitSet;/*** java布隆过滤器*/
public class MyBloomFilter {/*** 位数组大小*/private static final int DEFAULT_SIZE 2 24;/*** 通过这个数组创建多个Hash函数*/private static final int[] SEEDS new int[]{4, 8, 16, 32, 64, 128, 256};/*** 初始化位数组数组中的元素只能是 0 或者 1*/private final BitSet bits new BitSet(DEFAULT_SIZE);/*** Hash函数数组*/private final MyHash[] myHashes new MyHash[SEEDS.length];/*** 初始化多个包含 Hash 函数的类数组每个类中的 Hash 函数都不一样*/public MyBloomFilter() {// 初始化多个不同的 Hash 函数for (int i 0; i SEEDS.length; i) {myHashes[i] new MyHash(DEFAULT_SIZE, SEEDS[i]);}}/*** 添加元素到位数组*/public void add(Object value) {for (MyHash myHash : myHashes) {bits.set(myHash.hash(value), true);}}/*** 判断指定元素是否存在于位数组*/public boolean contains(Object value) {boolean result true;for (MyHash myHash : myHashes) {result result bits.get(myHash.hash(value));}return result;}/*** 自定义 Hash 函数*/private class MyHash {private int cap;private int seed;MyHash(int cap, int seed) {this.cap cap;this.seed seed;}/*** 计算 Hash 值*/int hash(Object obj) {return (obj null) ? 0 : Math.abs(seed * (cap - 1) (obj.hashCode() ^ (obj.hashCode() 16)));}}public static void main(String[] args) {String str 好好学技术;MyBloomFilter myBloomFilter new MyBloomFilter();System.out.println(str是否存在 myBloomFilter.contains(str));myBloomFilter.add(str);System.out.println(str是否存在 myBloomFilter.contains(str));}
}5.2Guava实现
依赖
dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion31.1-jre/version
/dependency代码
package com.fandf.test.redis;import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;/*** Guava*/
public class GuavaBloomFilter {public static void main(String[] args) {BloomFilterString bloomFilter BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);bloomFilter.put(好好学技术);System.out.println(bloomFilter.mightContain(不好好学技术));System.out.println(bloomFilter.mightContain(好好学技术));}
}5.3hutool实现
依赖
dependencygroupIdcn.hutool/groupIdartifactIdhutool-all/artifactIdversion5.8.3/version
/dependency代码
package com.fandf.test.redis;import cn.hutool.bloomfilter.BitMapBloomFilter;
import cn.hutool.bloomfilter.BloomFilterUtil;/*** hutool*/
public class HutoolBloomFilter {public static void main(String[] args) {BitMapBloomFilter bloomFilter BloomFilterUtil.createBitMap(1000);bloomFilter.add(好好学技术);System.out.println(bloomFilter.contains(不好好学技术));System.out.println(bloomFilter.contains(好好学技术));}
}5.4Redisson实现
依赖
dependencygroupIdorg.redisson/groupIdartifactIdredisson/artifactIdversion3.20.0/version
/dependency代码
package com.fandf.test.redis;import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;/*** Redisson 实现布隆过滤器*/
public class RedissonBloomFilter {public static void main(String[] args) {Config config new Config();config.useSingleServer().setAddress(redis://127.0.0.1:6379);//构造RedissonRedissonClient redisson Redisson.create(config);RBloomFilterString bloomFilter redisson.getBloomFilter(name);//初始化布隆过滤器预计元素为100000000L,误差率为1%bloomFilter.tryInit(100000000L,0.01);bloomFilter.add(好好学技术);System.out.println(bloomFilter.contains(不好好学技术));System.out.println(bloomFilter.contains(好好学技术));}
}
