回顾

上一节我们简单介绍了 BloomFilter 的原理，并且介绍了 guava BloomFilter 的使用。

今天让我们更上一层楼，实现一个属于自己的 BoolFilter。

实现原理

原理回顾

布隆过滤器在本质上是二进制向量。

在高层级上，布隆过滤器以下面的方式工作：

添加元素到过滤器。

对元素进行几次哈希运算，当索引匹配哈希的结果时，将该位设置为 1 的。

如果要检测元素是否属于集合，使用相同的哈希运算步骤，检查相应位的值是1还是0。这就是布隆过滤器明确元素不存在的过程。如果位未被设置，则元素绝不可能存在于集合中。

当然，一个肯定的答案意味着，要不就是元素存在于集合中，要不就是遇见了哈希冲突。

实现思路

我们再加入一个元素时，通过多种不同的 hash 算法，然后设置到 bit 数组中。

判断是否存在的时候，也对元素采用多种不同的 hash 算法，如果都为 true，则说明可能存在。如果有不为 true 的，说明一定不不存在。

自己实现简单版本

hash 算法

可以参考 hash 算法介绍

• IHash.java

public interface IHash {    /**     * 根据 key 获取对应的hash值     * @param key 字符串     * @return hash 值     */    int hashIndex(final String key);}

三个简单的实现：

• HashOne

public class HashOne implements IHash {    @Override    public int hashIndex(String key) {        int hash = 0;        for(int i = 0; i 

• HashTwo

public class HashTwo implements IHash {    @Override    public int hashIndex(String key) {        final int p = 16777619;        int hash = (int) 2166136261L;        for(int i = 0 ; i > 7;        hash += hash <> 17;        hash += hash <

• HashThree

public class HashThree implements IHash {    @Override    public int hashIndex(String key) {        int hash, i;        for (hash = 0, i = 0; i > 6);        }        hash += (hash <> 11);        hash += (hash <

Bloom Fliter 实现

• IBloomFilter.java

public interface IBloomFilter {    /**     * 添加一个元素     * @param key  元素     */    void add(final String key);    /**     * 可能包含元素     * @param key 元素     * @return 可能包含     */    boolean mightContains(final String key);}

• SimpleBloomFilter.java

import com.github.houbb.guava.learn.bloom.hash.HashOne;import com.github.houbb.guava.learn.bloom.hash.HashThree;import com.github.houbb.guava.learn.bloom.hash.HashTwo;public class SimpleBloomFilter implements IBloomFilter {    private final int size;    private boolean[] array;    public SimpleBloomFilter(int size) {        this.size = size;        this.array = new boolean[size];    }    @Override    public void add(String key) {        // 做三次 hash        int hashOne = new HashOne().hashIndex(key);        int hashTwo = new HashTwo().hashIndex(key);        int hashThree = new HashThree().hashIndex(key);        this.array[hashOne%array.length] = true;        this.array[hashTwo%array.length] = true;        this.array[hashThree%array.length] = true;    }    @Override    public boolean mightContains(String key) {        // 做三次 hash        int hashOne = new HashOne().hashIndex(key);        int hashTwo = new HashTwo().hashIndex(key);        int hashThree = new HashThree().hashIndex(key);        if(!array[hashOne]) {            return false;        }        if(!array[hashTwo]) {            return false;        }        if(!array[hashThree]) {            return false;        }        return true;    }}

测试验证

maven 引入

    com.github.houbb    bloom-filter    0.0.1

例子

String text1 = "hello";String text2 = "world";BloomFilterBs bloomFilterBs = BloomFilterBs        .newInstance()        .add(text1)        .add(text2);Assert.assertTrue(bloomFilterBs.mightContains(text1));Assert.assertFalse(bloomFilterBs.mightContains("other"));

性能问题

当然我们实现版本的性能可能相对一般，可以参考下 guava 的实现。

后续我们有时间可以阅读下 guava BoolmFilter 的源码。

小结

本节回顾了 Bloom Filter 的实现思路，并且通过 java 实现了属于我们自己的布隆过滤器。

工作中就算不使用自己造的轮子，知其然知其所以然，有问题自己也知道大概的排查方向。

目前的版本非常的简陋，还有很多可以改进的地方，我们后续可以阅读下 guava 的源码，并化为己用。

布隆过滤器使用也不存在需要注意的点，下一节我们来讲一讲使用的最佳实践。

觉得本文对你有帮助的话，欢迎点赞评论收藏关注一波。你的鼓励，是我最大的动力~

不知道你有哪些收获呢？

或者有其他更多的想法，欢迎留言区和我一起讨论，期待与你的思考相遇。