布隆过滤器是否好用，得看哈希函数写成啥样

作者：小傅哥

2022-10-12
北京
本文字数：2816 字
阅读完需：约 9 分钟

作者：小傅哥

博客：https://bugstack.cn

沉淀、分享、成长，让自己和他人都能有所收获！😄

一、前言

布隆过滤器的历史

布隆过滤器由 Burton Howard Bloom 于 1970 年提出，它是一种节省空间的概率数据结构，包括一个很长的二进制向量和一些列随机映射函数。

二、布隆过滤器结构

布隆过滤器是一个基于数组和哈希函数散列元素的结构，很像 HashMap 的哈希桶。布隆过滤器可以用于检测一个元素是否在集合中。它的优点是空间效率和查询时间比一般算法要好很多，但也有一定概率的误判性。如 HashMap 出现哈希碰撞💥

赵敏：无忌，成昆上了光明顶！
张无忌：咱们过滤器年久失修，已经不准了！
张无忌：布隆过滤器的长度太小，哈希计算单一。导致谢飞机、拎瓢冲、成昆，三个人的哈希值都是相同的，所以没法判断成昆是否上了光明顶。咱们只能快些上山了，沿途小心。
杨左使：老大，我现在就去维修一下。布隆过滤器的优化方式可以通过增加长度和多样新计算哈希解决。

三、布隆过滤器实现

布隆过滤器的实现条件包括可以存放二进制元素的 BitSet 以及多样性的哈希计算函数。

public class BloomFilter {
    private static final HashGenerator.HashGroup[] GROUPS = new HashGenerator.HashGroup[]{HashGenerator.HashGroup.G1, HashGenerator.HashGroup.G2, HashGenerator.HashGroup.G3, HashGenerator.HashGroup.G4};
    private final BitSet bits;      private HashGenerator[] generators;
}

复制代码

所有的元素存放都经过多样的哈希计算存放到 BitSet 中，这样可以尽可能的分散元素，减少误判性。

源码地址：https://github.com/fuzhengwei/java-algorithms
本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/bloom_filter

1. 哈希函数

private int hashG1(String value) {    int hash = 0;    for (int idx = 0; idx < value.length(); idx++) {        char c = value.charAt(idx);        hash = (hash << 5) + hash + c;        hash &= hash;        hash = Math.abs(hash);    }    return hash % (seed * size - 1);}
private int hashG2(String value) {    int hash = 7397;    for (int idx = 0; idx < value.length(); idx++) {        char c = value.charAt(idx);        hash = (hash << 5) + hash + c;    }    return Math.abs(hash % seed * (size - 1));}
private int hashG3(String value) {    int hash = 0;    for (int idx = 0; idx < value.length(); idx++) {        char c = value.charAt(idx);        hash = (hash << 5) + hash + c;        hash += c;        hash &= hash;    }    return Math.abs(hash % (seed * size - 1));}
private int hashG4(String value) {    int h;    return (value == null) ? 0 : Math.abs(seed * (size - 1) & ((h = value.hashCode()) ^ (h >>> 16)));}

复制代码

这里提供了四种哈希计算的方式，相当于每一个哈希计算都是一次扰动处理。一个元素的存放可以经过四次哈希，尽量让元素值做到散列。

2. 构建容器

public BloomFilter(int size, int[] seeds) {    bits = new BitSet(size);    generators = new HashGenerator[seeds.length];    for (int i = 0; i < seeds.length; i++) {        generators[i] = new HashGenerator(size, seeds[i], GROUPS[i % GROUPS.length]);    }}

复制代码

构造函数根据所需创建的容器大小和哈希种子来初始化布隆过滤器。

3. 添加元素

public void add(String value) {    for (HashGenerator generator : generators) {        int hash = generator.doHash(value);        bits.set(hash, true);    }}

复制代码

添加元素时按照元素初始化时的哈希计算种类，获取哈希并存放。

4. 比对元素

public boolean contains(String value) {    boolean ret = true;    for (HashGenerator generator : generators) {        ret = ret && bits.get(generator.doHash(value));    }    return ret;}

复制代码

比对元素时用的是同一类哈希计算方式，并且把这些哈希值 && 计算。用 N 个比特位置记录一个值更准确

四、布隆过滤器测试

单元测试

@Testpublic void test() {    String val00 = "小傅哥";    String val01 = "https://bugstack.cn";    String val02 = "https://github.com/fuzhengwei/CodeGuide";    String val03 = "https://github.com/fuzhengwei";    BloomFilter filter = new BloomFilter(Integer.MAX_VALUE, new int[]{7, 19, 43, 77});    filter.add(val00);    filter.add(val01);    filter.add(val02);    logger.info("测试结果 val00：{} 布隆过滤器：{}", val00, filter.contains(val00));    logger.info("测试结果 val01：{} 布隆过滤器：{}", val01, filter.contains(val01));    logger.info("测试结果 val02：{} 布隆过滤器：{}", val02, filter.contains(val02));    logger.info("测试结果 val02：{} 布隆过滤器：{}", val03, filter.contains(val03));}

复制代码

可以看到这里初始化了一个比较大的布隆过滤器，并且提供了 4 个随机种子；7, 19, 43, 77计算哈希值。

测试结果

21:33:22.790 [main] INFO bloom_filter.__test__.BloomFilterTest - 测试结果 val00：小傅哥 布隆过滤器：true21:33:22.794 [main] INFO bloom_filter.__test__.BloomFilterTest - 测试结果 val01：https://bugstack.cn 布隆过滤器：true21:33:22.794 [main] INFO bloom_filter.__test__.BloomFilterTest - 测试结果 val02：https://github.com/fuzhengwei/CodeGuide 布隆过滤器：true21:33:22.795 [main] INFO bloom_filter.__test__.BloomFilterTest - 测试结果 val02：https://github.com/fuzhengwei 布隆过滤器：false

Process finished with exit code 0

复制代码

通过测试可以看到，存放的 val00、val01、val02 分别可以验证出 true 没有存放的 val03 验证为 fasle

五、常见面试题

布隆过滤器的使用场景？
布隆过滤器的实现原理和方式？
如何提高布隆过滤器的准确性？
有哪些中哈希计算方式？
都有哪些类型的布隆过滤器实现？Google 开源的 Guava 中自带的布隆过滤器、Redis 中的布隆过滤器(https://github.com/RedisBloom/RedisBloom)

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/307ad49cbe786e4c5a834a42c】。文章转载请联系作者。

小傅哥

关注

沉淀、分享、成长，让自己和他人都有所收获 2019-04-03 加入

作者小傅哥，一线互联网 java 工程师、架构师，开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言，也搞过C#、PHP，是一个技术活跃的折腾者。

发布

暂无评论

创作场景

布隆过滤器是否好用，得看哈希函数写成啥样

一、前言

二、布隆过滤器结构

三、布隆过滤器实现

1. 哈希函数

2. 构建容器

3. 添加元素

4. 比对元素

四、布隆过滤器测试

五、常见面试题

小傅哥

评论