快捷導(dǎo)航

Java中的布隆過濾器原理實(shí)現(xiàn)和應(yīng)用

更新時(shí)間：2023年04月23日 10:22:42 作者：.番茄炒蛋

Java中的布隆過濾器是一種基于哈希函數(shù)的數(shù)據(jù)結(jié)構(gòu)，能夠高效地判斷元素是否存在于一個(gè)集合中。它廣泛應(yīng)用于緩存、網(wǎng)絡(luò)協(xié)議、數(shù)據(jù)查詢等領(lǐng)域，在提高程序性能和減少資源消耗方面具有顯著優(yōu)勢(shì)

介紹

本文全部代碼地址

布隆過濾器是一種高效的數(shù)據(jù)結(jié)構(gòu),用于判斷一個(gè)元素是否存在于一個(gè)集合中.它的主要優(yōu)點(diǎn)是速度快,空間占用少,因此在需要快速判斷某個(gè)元素是否在集合中的場(chǎng)合得到廣泛引用.

布隆過濾器就是一個(gè)大型的位數(shù)組和幾個(gè)不一樣的無偏hash函數(shù).所謂無偏就是能夠把元素的hash值算的比較均勻.當(dāng)布隆過濾器說某個(gè)值存在時(shí),這個(gè)值可能不存在;當(dāng)它說某個(gè)值不存在時(shí),那就肯定不存在.

向布隆過濾器中添加key時(shí),會(huì)使用多個(gè)hash函數(shù)對(duì)key進(jìn)行hash算得一個(gè)整數(shù)索引值然后對(duì)應(yīng)位數(shù)數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算得到一個(gè)位置,每個(gè)hash函數(shù)都會(huì)算得一個(gè)不同的位置.再把位數(shù)組的這幾個(gè)位置都置為1就完成了add操作.

向布隆過濾器詢問key是否存在時(shí),跟add一樣,也會(huì)把hash的幾個(gè)位置都算出來,看看數(shù)組中這幾個(gè)位置是否都為1,只要有一個(gè)位為0,那么就說明布隆過濾器中這個(gè)key不存在.如果都是1,這并不能說明這個(gè)key就一定存在,只是極有可能存在,因?yàn)檫@些位置被置為1可能是因?yàn)槠渌膋ey存在所致.如果這個(gè)位數(shù)組長(zhǎng)度比較大,存在概率就會(huì)很大,如果這個(gè)位數(shù)組長(zhǎng)度比較小,存在的概率就會(huì)降低.

這種方法適用于數(shù)據(jù)命中不高、數(shù)據(jù)相對(duì)固定、實(shí)時(shí)性低(通常是數(shù)據(jù)集較大) 的應(yīng)用場(chǎng)景,代碼維護(hù)較為復(fù)雜,但是緩存空間占用很少.

實(shí)現(xiàn)

初始化數(shù)據(jù)

DROP TABLE IF EXISTS `user`;
CREATE TABLE `user`  (
    `id` varchar(50) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NOT NULL,
    `name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL,
    `address` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL,
    PRIMARY KEY (`id`) USING BTREE
    ) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;
INSERT INTO `user` VALUES ('be079b29ddc111eda9b20242ac110003', '張三', '北京市海淀區(qū)xx街道123號(hào)');
INSERT INTO `user` VALUES ('be079b53ddc111eda9b20242ac110003', '李四', '上海市徐匯區(qū)xx路456號(hào)');
INSERT INTO `user` VALUES ('be079b95ddc111eda9b20242ac110003', '王五', '廣州市天河區(qū)xx街道789號(hào)');
INSERT INTO `user` VALUES ('be079ba4ddc111eda9b20242ac110003', '趙六', '深圳市南山區(qū)xx路321號(hào)');
INSERT INTO `user` VALUES ('be079bb8ddc111eda9b20242ac110003', '周七', '成都市高新區(qū)xx街道654號(hào)');
INSERT INTO `user` VALUES ('be079bc5ddc111eda9b20242ac110003', '黃八', '武漢市江漢區(qū)xx街道234號(hào)');
INSERT INTO `user` VALUES ('be079bd4ddc111eda9b20242ac110003', '羅九', '南京市秦淮區(qū)xx路567號(hào)');
INSERT INTO `user` VALUES ('be079be2ddc111eda9b20242ac110003', '錢十', '重慶市渝北區(qū)xx街道890號(hào)');
INSERT INTO `user` VALUES ('be079befddc111eda9b20242ac110003', '周十一', '長(zhǎng)沙市岳麓區(qū)xx路432號(hào)');
INSERT INTO `user` VALUES ('be079bfbddc111eda9b20242ac110003', '吳十二', '西安市雁塔區(qū)xx街道765號(hào)');

代碼實(shí)現(xiàn)

這里只展示關(guān)于布隆過濾器的核心代碼

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;
        // 計(jì)算bit數(shù)組長(zhǎng)度
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        // 計(jì)算hash方法執(zhí)行次數(shù)
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }
    public int[] murmurHashOffset(T value) {
        int[] offset = new int[numHashFunctions];
        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 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;
    }
    /**
     * 計(jì)算bit數(shù)組長(zhǎng)度
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            // 設(shè)定最小期望長(zhǎng)度
            p = Double.MIN_VALUE;
        }
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
    /**
     * 計(jì)算hash方法執(zhí)行次數(shù)
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
}

@Slf4j
@Configuration
public class BloomFilterConfig implements InitializingBean {
    @Autowired
    private StringRedisTemplate template;
    @Autowired
    private UserService userService;
    public static final String BLOOM_REDIS_PREFIX = "bloom_user";
    @Bean
    public 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注入
     *
     * @return
     */
    @Bean
    public BloomRedisService bloomRedisService() {
        BloomRedisService bloomRedisService = new BloomRedisService();
        bloomRedisService.setBloomFilterHelper(initBloomFilterHelper());
        bloomRedisService.setRedisTemplate(template);
        return bloomRedisService;
    }
    /**
     * 初始化方法,將數(shù)據(jù)庫(kù)中的id加入到布隆過濾器
     * 也可以不必實(shí)現(xiàn){@link InitializingBean}使用{@link javax.annotation.PostConstruct}注解
     *
     * @throws Exception
     */
    @Override
    public void afterPropertiesSet() throws Exception {
        List<String> idList = userService.getAllUserId();
        log.info("加載用戶id到布隆過濾器當(dāng)中,size:{}", idList.size());
        if (!CollectionUtils.isEmpty(idList)) {
            idList.forEach(item -> {
                bloomRedisService().addByBloomFilter(BLOOM_REDIS_PREFIX, item);
            });
        }
    }
}

public class BloomRedisService {
    private StringRedisTemplate redisTemplate;
    private BloomFilterHelper bloomFilterHelper;
    public void setBloomFilterHelper(BloomFilterHelper bloomFilterHelper) {
        this.bloomFilterHelper = bloomFilterHelper;
    }
    public void setRedisTemplate(StringRedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
    }
    /**
     * 根據(jù)給定的布隆過濾器添加值
     */
    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);
        }
    }
    /**
     * 根據(jù)給定的布隆過濾器判斷值是否存在
     */
    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;
    }
}

@Configuration
public class InterceptorConfiguration implements WebMvcConfigurer {
    @Override
    public void addInterceptors(InterceptorRegistry registry) {
        //注冊(cè)攔截器
        registry.addInterceptor(authInterceptorHandler())
                .addPathPatterns("/user/get/{id}");
    }
    @Bean
    public BloomFilterInterceptor authInterceptorHandler(){
        return new BloomFilterInterceptor();
    }
}

@Slf4j
public class BloomFilterInterceptor implements HandlerInterceptor {
    @Autowired
    private BloomRedisService bloomRedisService;
    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {
        String currentUrl = request.getRequestURI();
        PathMatcher matcher = new AntPathMatcher();
        //解析出pathvariable
        Map<String, String> pathVariable = matcher.extractUriTemplateVariables("/user/get/{id}", currentUrl);
        //布隆過濾器存儲(chǔ)在redis中
        String id = pathVariable.get("id");
        if (bloomRedisService.includeByBloomFilter(BloomFilterConfig.BLOOM_REDIS_PREFIX, id)) {
            log.info("{}極有可能存在,繼續(xù)向下執(zhí)行;", id);
            return true;
        }
        /*
         * 不在本地布隆過濾器當(dāng)中，直接返回驗(yàn)證失敗
         * 設(shè)置響應(yīng)頭
         */
        log.info("{}不存在,直接返回失敗;", id);
        response.setHeader(HttpHeaders.CONTENT_TYPE, MediaType.APPLICATION_JSON_VALUE);
        response.setCharacterEncoding(StandardCharsets.UTF_8.toString());
        response.setStatus(HttpStatus.NOT_FOUND.value());
        Result res = new Result(HttpStatus.NOT_FOUND.value(), "用戶不存在!", null);
        String result = new ObjectMapper().writeValueAsString(res);
        response.getWriter().print(result);
        return false;
    }
}