摘要：一般情況下不能從布隆過濾器中刪除元素實現(xiàn)哈希算法在年發(fā)布了一個新的散列函數(shù)。能夠迅速走紅得益于其出色的速度和統(tǒng)計特性。比如哈希函數(shù)個數(shù)取，位數(shù)組大小設(shè)為字符串個數(shù)的倍時，發(fā)生的概率是。

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的，可以用于檢索一個元素是否在一個集合中。

布隆過濾器的原理是，當(dāng)一個元素被加入集合時，通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。

運行快速，內(nèi)存占用小。一般方法是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、哈希表等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間越來越大。同時檢索速度也越來越慢。

隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。

一般情況下不能從布隆過濾器中刪除元素.

public class BloomFilter {
    private final int size;
    private final int hashCount;
    private final BitSet bitSet;

    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.hashCount = hashCount;
        bitSet = new BitSet(size);
    }

    public void add(String key) {
        for (int seed = 1; seed <= hashCount; seed++) {
            int hash = Hashing.murmur3_32(seed).hashBytes(key.getBytes()).asInt();
            int index = Math.abs(hash) % size;
            bitSet.set(index);
        }
    }

    public boolean lookup(String key) {
        for (int seed = 1; seed <= hashCount; seed++) {
            int hash = Hashing.murmur3_32(seed).hashBytes(key.getBytes()).asInt();
            int index = Math.abs(hash) % size;
            if (!bitSet.get(index)) return false;
        }
        return true;
    }
}

Austin Appleby在2008年發(fā)布了一個新的散列函數(shù)——MurmurHash。其最新版本大約是lookup3速度的2倍（大約為1 byte/cycle），它有32位和64位兩個版本。32位版本只使用32位數(shù)學(xué)函數(shù)并給出一個32位的哈希值，而64位版本使用了64位的數(shù)學(xué)函數(shù)，并給出64位哈希值。根據(jù)Austin的分析，MurmurHash具有優(yōu)異的性能，雖然Bob Jenkins 在《Dr. Dobbs article》雜志上聲稱“我預(yù)測MurmurHash比起lookup3要弱，但是我不知道具體值，因為我還沒測試過它”。MurmurHash能夠迅速走紅得益于其出色的速度和統(tǒng)計特性。

guava自帶的Murmur3_32HashFunction：

final class Murmur3_32HashFunction extends AbstractStreamingHashFunction implements Serializable {
  private static final int C1 = 0xcc9e2d51;
  private static final int C2 = 0x1b873593;

  private final int seed;

  Murmur3_32HashFunction(int seed) {
    this.seed = seed;
  }

  @Override
  public int bits() {
    return 32;
  }

  @Override
  public Hasher newHasher() {
    return new Murmur3_32Hasher(seed);
  }

  @Override
  public String toString() {
    return "Hashing.murmur3_32(" + seed + ")";
  }

  @Override
  public boolean equals(@Nullable Object object) {
    if (object instanceof Murmur3_32HashFunction) {
      Murmur3_32HashFunction other = (Murmur3_32HashFunction) object;
      return seed == other.seed;
    }
    return false;
  }

  @Override
  public int hashCode() {
    return getClass().hashCode() ^ seed;
  }

  @Override
  public HashCode hashInt(int input) {
    int k1 = mixK1(input);
    int h1 = mixH1(seed, k1);

    return fmix(h1, Ints.BYTES);
  }

  @Override
  public HashCode hashLong(long input) {
    int low = (int) input;
    int high = (int) (input >>> 32);

    int k1 = mixK1(low);
    int h1 = mixH1(seed, k1);

    k1 = mixK1(high);
    h1 = mixH1(h1, k1);

    return fmix(h1, Longs.BYTES);
  }

  // TODO(kak): Maybe implement #hashBytes instead?
  @Override
  public HashCode hashUnencodedChars(CharSequence input) {
    int h1 = seed;

    // step through the CharSequence 2 chars at a time
    for (int i = 1; i < input.length(); i += 2) {
      int k1 = input.charAt(i - 1) | (input.charAt(i) << 16);
      k1 = mixK1(k1);
      h1 = mixH1(h1, k1);
    }

    // deal with any remaining characters
    if ((input.length() & 1) == 1) {
      int k1 = input.charAt(input.length() - 1);
      k1 = mixK1(k1);
      h1 ^= k1;
    }

    return fmix(h1, Chars.BYTES * input.length());
  }

  private static int mixK1(int k1) {
    k1 *= C1;
    k1 = Integer.rotateLeft(k1, 15);
    k1 *= C2;
    return k1;
  }

  private static int mixH1(int h1, int k1) {
    h1 ^= k1;
    h1 = Integer.rotateLeft(h1, 13);
    h1 = h1 * 5 + 0xe6546b64;
    return h1;
  }

  // Finalization mix - force all bits of a hash block to avalanche
  private static HashCode fmix(int h1, int length) {
    h1 ^= length;
    h1 ^= h1 >>> 16;
    h1 *= 0x85ebca6b;
    h1 ^= h1 >>> 13;
    h1 *= 0xc2b2ae35;
    h1 ^= h1 >>> 16;
    return HashCode.fromInt(h1);
  }

  private static final class Murmur3_32Hasher extends AbstractStreamingHasher {
    private static final int CHUNK_SIZE = 4;
    private int h1;
    private int length;

    Murmur3_32Hasher(int seed) {
      super(CHUNK_SIZE);
      this.h1 = seed;
      this.length = 0;
    }

    @Override
    protected void process(ByteBuffer bb) {
      int k1 = Murmur3_32HashFunction.mixK1(bb.getInt());
      h1 = Murmur3_32HashFunction.mixH1(h1, k1);
      length += CHUNK_SIZE;
    }

    @Override
    protected void processRemaining(ByteBuffer bb) {
      length += bb.remaining();
      int k1 = 0;
      for (int i = 0; bb.hasRemaining(); i += 8) {
        k1 ^= toInt(bb.get()) << i;
      }
      h1 ^= Murmur3_32HashFunction.mixK1(k1);
    }

    @Override
    public HashCode makeHash() {
      return Murmur3_32HashFunction.fmix(h1, length);
    }
  }

  private static final long serialVersionUID = 0L;
}

哈希函數(shù)個數(shù)k、位數(shù)組大小m、加入的字符串?dāng)?shù)量n的關(guān)系：對于給定的m、n，當(dāng) k = ln(2)* m/n 時出錯的概率是最小的。比如哈希函數(shù)個數(shù)k取10，位數(shù)組大小m設(shè)為字符串個數(shù)n的20倍時，false positive發(fā)生的概率是0.0000889。
guava提供的BloomFilter則直接提供了false positive的參數(shù)給你配置。

public static  BloomFilter create(Funnel funnel, long expectedInsertions) {
    return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
  }

BloomFilter——大規(guī)模數(shù)據(jù)處理利器

Bloom Filters by Example

Guava教程-BloomFilter

Hash 函數(shù)概覽

陌生但默默一統(tǒng)江湖的MurmurHash