Redis实现布隆过滤器解析( 二 ) _生活百科

2）mightContain方法深入分析
public boolean mightContain(T object) {return strategy.mightContain(object, funnel, numHashFunctions, bits);}public <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.BitArray bits) {long bitSize = bits.bitSize();long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();int hash1 = (int)hash64;int hash2 = (int)(hash64 >>> 32);for(int i = 1; i <= numHashFunctions; ++i) {int combinedHash = hash1 + i * hash2;if (combinedHash < 0) {combinedHash = ~combinedHash;}if (!bits.get((long)combinedHash % bitSize)) {return false;}}return true;}3）put方法深入分析
@CanIgnoreReturnValuepublic boolean put(T object) {return strategy.put(object, funnel, numHashFunctions, bits);}//策略实现填入bitspublic <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.BitArray bits) {long bitSize = bits.bitSize();long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();int hash1 = (int)hash64;int hash2 = (int)(hash64 >>> 32);boolean bitsChanged = false;for(int i = 1; i <= numHashFunctions; ++i) {int combinedHash = hash1 + i * hash2;if (combinedHash < 0) {combinedHash = ~combinedHash;}bitsChanged |= bits.set((long)combinedHash % bitSize);}return bitsChanged;}采用Redis实现布隆过滤器【1】抽出guava框架中部分核心逻辑方法形成工具类
/** * 算法过程： * 1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数 * 2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0 * 3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1 * 4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。* @description: 布隆过滤器，摘录自Google-guava包 **/public class BloomFilterHelper<T> {private int numHashFunctions;private int bitSize;private Funnel<T> funnel;public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {Preconditions.checkArgument(funnel != null, "funnel不能为空");this.funnel = funnel;// 计算bit数组长度bitSize = optimalNumOfBits(expectedInsertions, fpp);// 计算hash方法执行次数numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);}public int[] murmurHashOffset(T value) {int[] offset = new int[numHashFunctions];//有点类似于hashmap中采用高32位与低32位相与获得hash值long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();int hash1 = (int) hash64;int hash2 = (int) (hash64 >>> 32);//采用对低32进行变更以达到随机哈希函数的效果for (int i = 1; i <= numHashFunctions; i++) {int nextHash = hash1 + i * hash2;if (nextHash < 0) {nextHash = ~nextHash;}offset[i - 1] = nextHash % bitSize;}return offset;}/*** 计算bit数组长度* Math.log(2) = 0.6931471805599453;（取0.693147来用）* (Math.log(2) * Math.log(2)) = 0.48045237;* 假设传入n为1,000,000, p为0.01;* Math.log(0.01) = -4.605170185988091;* 则返回值为9,585,071 ,即差不多是预设容量的10倍** 要知道 1MB = 1024KB , 1KB = 1024B ,1B=8bit 。* 也就是对一百万数据预计花费的内存为1.143MB的内存*/private int optimalNumOfBits(long n, double p) {if (p == 0) {// 设定最小期望长度p = Double.MIN_VALUE;}return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));}/*** 计算hash方法执行次数*/private int optimalNumOfHashFunctions(long n, long m) {return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));}}【2】构建Redis实现布隆过滤器的服务类
public class BloomRedisService {private RedisTemplate<String, Object> redisTemplate;private BloomFilterHelper bloomFilterHelper;public void setBloomFilterHelper(BloomFilterHelper bloomFilterHelper) {this.bloomFilterHelper = bloomFilterHelper;}public void setRedisTemplate(RedisTemplate<String, Object> redisTemplate) {this.redisTemplate = redisTemplate;}/*** 根据给定的布隆过滤器添加值*/public <T> void addByBloomFilter(String key, T value) {Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");int[] offset = bloomFilterHelper.murmurHashOffset(value);for (int i : offset) {redisTemplate.opsForValue().setBit(key, i, true);}}/*** 根据给定的布隆过滤器判断值是否存在*/public <T> boolean includeByBloomFilter(String key, T value) {Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");int[] offset = bloomFilterHelper.murmurHashOffset(value);for (int i : offset) {if (!redisTemplate.opsForValue().getBit(key, i)) {return false;}}return true;}}【3】编辑配置类
@Slf4j@Configurationpublic class BloomFilterConfig implements InitializingBean{@Autowiredprivate PmsProductService productService;@Autowiredprivate RedisTemplate template;@Beanpublic BloomFilterHelper<String> initBloomFilterHelper() {return new BloomFilterHelper<>((Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8).putString(from, Charsets.UTF_8), 1000000, 0.01);}// 布隆过滤器bean注入@Beanpublic BloomRedisService bloomRedisService(){BloomRedisService bloomRedisService = new BloomRedisService();bloomRedisService.setBloomFilterHelper(initBloomFilterHelper());bloomRedisService.setRedisTemplate(template);return bloomRedisService;}@Overridepublic void afterPropertiesSet() throws Exception {List<Long> list = productService.getAllProductId();log.info("加载产品到布隆过滤器当中,size:{}",list.size());if(!CollectionUtils.isEmpty(list)){list.stream().forEach(item->{//LocalBloomFilter.put(item);bloomRedisService().addByBloomFilter(RedisKeyPrefixConst.PRODUCT_REDIS_BLOOM_FILTER,item+"");});}}}

Redis实现布隆过滤器解析( 二 )

推荐阅读

汽车用品买什么是必备的买车以后有哪些重要的车用品

西梅可以冷冻保存吗怎么吃西梅可以冷冻保存吗

怎么自制减肥营养餐

立秋后的第一杯奶茶是什么意思?

快手小店上传商品审核多久快手商品审核多长时间

炒猪肚用什么配菜好吃炒猪肚用什么配菜

十二星座专属配套服装

关于感恩节的作文600字

人生自古谁无死出自哪首诗人生自古谁无死

2020年07月14日双子座事业爱情运势

绝地求生怎么跑绝地求生快速跑动按键详解

护士节的来历

依维柯宝迪edc灯消不掉怎么回事依维柯宝迪提示灯

请评教是什么意思网上评教是什么意思

机动车检验去哪里办理

冰箱里放三天的饭菜还可以吃吗饭菜放冰箱三天能吃吗

白城到长春白城到长春客车时间表

三国程普怎么死的

狮子座生日狮子座是几月份

好听的双胞胎男孩名字