浙江龙网

  1. 首页 > 生活百科 > >

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+"");});}}}

推荐阅读


上一篇：[CG从零开始] 6. 加载一个柴犬模型学习UV贴图

下一篇：.Net WebApi 中的 FromBody FromForm FromQuery FromHeader FromRoute