缓存实战（3）让你彻底搞懂布隆过滤器！实现一个自己的BloomFilter

回顾

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

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

思维导图实现原理

原理回顾

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

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

添加元素到过滤器。

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

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

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

实现思路

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

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

源码自己实现简单版本

hash 算法

可以参考 hash 算法介绍

IHash.java

三个简单的实现：

HashOne

HashTwo

HashThree

Bloom Fliter 实现

IBloomFilter.java

SimpleBloomFilter.java

小结

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

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

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

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

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