回顾

上一节我们简单介绍了 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 < key.length(); i++) {
            hash = 33 * hash + key.charAt(i);
        }

        return Math .abs(hash);
    }

}

• 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 < key.length(); i++) {
            hash = (hash ^ key.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash);
    }
}

• HashThree

public class HashThree implements IHash {

    @Override
    public int hashIndex(String key) {
        int hash, i;

        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }

        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return Math.abs(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;
    }
}

小结

当然我们实现版本的性能比较差，可以参考下 guava 的实现。

本文简单介绍了布隆过滤器的发展历史和应用场景，并给出了 guava BloomFliter 使用案例。希望大家对 bloom filter 有一个最基本的认识。

下一节我们将和大家一起实现属于自己的布隆过滤器。

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

不知道你有哪些收获呢？或者有其他更多的想法，欢迎留言区和我一起讨论，期待与你的思考相遇。