生活_傻大方

  1. 首页 > 人文 > >

让你彻底搞懂布隆过滤器！实现一个自己的BloomFilter

回顾上一节我们简单介绍了 BloomFilter 的原理 ， 并且介绍了 guava BloomFilter 的使用 。
今天让我们更上一层楼 ， 实现一个属于自己的 BoolFilter 。
让你彻底搞懂布隆过滤器！实现一个自己的BloomFilter文章插图
实现原理原理回顾布隆过滤器在本质上是二进制向量 。
在高层级上 ， 布隆过滤器以下面的方式工作：
添加元素到过滤器 。
对元素进行几次哈希运算 ， 当索引匹配哈希的结果时 ， 将该位设置为 1 的 。
如果要检测元素是否属于集合 ， 使用相同的哈希运算步骤 ， 检查相应位的值是1还是0 。 这就是布隆过滤器明确元素不存在的过程 。 如果位未被设置 ， 则元素绝不可能存在于集合中 。
当然 ， 一个肯定的答案意味着 ， 要不就是元素存在于集合中 ， 要不就是遇见了哈希冲突 。
实现思路我们再加入一个元素时 ， 通过多种不同的 hash 算法 ， 然后设置到 bit 数组中 。
判断是否存在的时候 ， 也对元素采用多种不同的 hash 算法 ， 如果都为 true ， 则说明可能存在 。 如果有不为 true 的 ， 说明一定不不存在 。
让你彻底搞懂布隆过滤器！实现一个自己的BloomFilter文章插图
自己实现简单版本hash 算法可以参考 hash 算法介绍

  • IHash.java
public interface IHash {/*** 根据 key 获取对应的hash值* @param key 字符串* @return hash 值*/int hashIndex(final String key);}三个简单的实现：
  • 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;}}



上一篇：华为 WATCH FIT 开箱评测：外形年轻有活力，性价比高

下一篇：“谁家玉笛暗飞声”——也谈一种聊天机器人的无痕接入