让你彻底搞懂布隆过滤器！实现一个自己的BloomFilter 回顾上一节我们简单介绍了B

回顾上一节我们简单介绍了 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);}

【让你彻底搞懂布隆过滤器！实现一个自己的BloomFilter】三个简单的实现：

HashOne

public class HashOne implements IHash {@Overridepublic 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 {@Overridepublic 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 {@Overridepublic 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];}@Overridepublic void add(String key) {// 做三次 hashint 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;}@Overridepublic boolean mightContains(String key) {// 做三次 hashint 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.houbbbloom-filter0.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 的源码，并化为己用。
布隆过滤器使用也不存在需要注意的点，下一节我们来讲一讲使用的最佳实践。