杂：位图与布隆过滤器

我们经常有这样的需求：判断一个订单是否存在，判断一个URL路径是否访问过。常规情况下我们可以将存在的订单ID或者已经访问过的URL做成集合，然后通过判断是否在集合中来确认是否存在或者是否访问过。那么我们也同样的可以想到通过hash算法将已存在的订单ID或者已经访问过的URL做映射到一个array的index上，通过检查对于index的值是否为true来判断是否存在。

但是，实际上我们并不需要一个array来存储true和false，二进制01本身就能表示true和false，这就是位图。Java自带的BitSet就是一个位图，可以操作单独的某位数据。

public class BitSet implements Cloneable, java.io.Serializable {
    /**  
    * The internal field corresponding to the serialField "bits". 
    */
    private long[] words;
}

BitSet使用一个long数组表示一个长度为64 × len 位的长度的位图（len是数组长度）。假设我们1000w数据，那么至少需要156,250长度的long数组，大概需要1.2MB的连续内存，极其节省内存。

那么我们的重点就应该集中在使用更加快速且均匀的hash算法的选择，比如MurmurHash或者CityHash。但是不论是何种hash算法，都存在hash冲突的可能，那么我们需要想办法降低hash冲突，我们可以应用多次不同的hash算法进行多次设置，这就是布隆过滤器(BloomFilter)的原理。

         [A]
    hash1/\hash2
   index1  index2

首先我们实现位图如下：

package cn.lishiyuan.algorithm.bit;  
  
/**  
 * 位图  
 */  
public class BitMap {  
  
    private final long[] bits;  
  
    private final int size;  
  
  
    public BitMap(int size) {  
        this.bits = new long[size];  
        this.size = 64 * size;  
    }  
  
    // 反转  
    public void flip(long index) {  
        // 防止溢出  
        index = index % size;  
        int wordIndex = (int) (index / 64);     // 确定在哪个 long 元素里  
        long bitIndex = index % 64;      // 确定在这个 long 中的哪一位  
        bits[wordIndex] ^= (1L << bitIndex);  // 设置这一位为 1    
    }  
  
    public int set(long index) {  
        // 防止溢出  
        index = index % size;  
        int wordIndex = (int) (index / 64);     // 确定在哪个 long 元素里  
        long bitIndex = index % 64;      // 确定在这个 long 中的哪一位  
        bits[wordIndex] |= (1L << bitIndex);  // 设置这一位为 1        
        return 1;  
    }  
  
    public int get(long index) {  
        // 防止溢出  
        index = index % size;  
        int wordIndex = (int) (index / 64);     // 确定在哪个 long 元素里  
        long bitIndex = index % 64;      // 确定在这个 long 中的哪一位  
        long l = bits[wordIndex] & (1L << bitIndex);// 设置这一位为 1        
        return l!=0 ? 1 : 0;  
    }  
  
    public boolean getBoolean(long index) {  
        return get(index) == 1;  
    }  
}

这里的实现和Java自带的bitset一样使用一个long数组来表示位图。主要功能是对某一个位进行单独设置与读取的能力。

基于位图，组合Hash计算多次index，我们得到了BloomFilter

package cn.lishiyuan.algorithm.bit;  
  
  
import java.nio.charset.StandardCharsets;  
  
/**  
 * 布隆过滤器  
 */  
public class BloomFilter {  
    private final BitMap map;  
    private long count;  
  
    public BloomFilter(int size) {  
        this.map= new BitMap(size);  
        this.count = 0;  
    }  
  
    public boolean contains(String word) {  
        return contains(word.getBytes(StandardCharsets.UTF_8));  
    }  
  
    public boolean contains(byte[] word) {  
        long murIndex = MurmurHash.hash64(word);  
        // 防止出现负数  
        murIndex = Math.abs(murIndex);  
        long metIndex = MetroHash.hash64(word);  
        // 防止出现负数  
        metIndex = Math.abs(metIndex);  
        return map.getBoolean(murIndex) && map.getBoolean(metIndex);  
    }  
  
    public void put(String word) {  
        put(word.getBytes(StandardCharsets.UTF_8));  
    }  
  
    public void put(byte[] word) {  
        // 防止出现负数  
        long murIndex = MurmurHash.hash64(word);  
        murIndex = Math.abs(murIndex);  
        long metIndex = MetroHash.hash64(word);  
        metIndex = Math.abs(metIndex);  
  
        map.set(murIndex);  
        map.set(metIndex);  
        count++;  
    }  
  
    public long getCount(){  
        return count;  
    }  
  
}

这里使用MetroHash和MurmurHash进行双重Hash，降低冲突可能性。