布隆过滤器（Bloom Filter）1970年由布隆提出。是一个很长的二进制矢量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。
它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。


guava  
com.google.common.hash.BloomFilter

简单使用 


int expectedInsertions = 1000000;
double ffp = 0.1 / 100 ;
// fpp the desired false positive probability
BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, ffp);

for(int i=0;i<expectedInsertions;i++){
	bloomFilter.put(i);
}
// 判断某个数是否存在
boolean flag = bloomFilter.mightContain(999)




关键参数 
expectedInsertions  预估元素个数
ffp  错误率  错误率 越低 ，需要的内存容量越大

当插入的元素数量接近或高于预期值的时，布隆过滤器将会填满，错误率会上升

// 位数  占用空间大小
long numBits = optimalNumOfBits(expectedInsertions, fpp);
// hash函数个数
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    
    
    

应用场景
BigTable 使用BloomFilter，避免在硬盘中寻找不存在的条目。 

LSM (Log Structured Merge Tree) 存储引擎  leveldb  hbase  cassandra 等 也使用类似的机制 
写优化 ， 查找不存在的元素 很耗时 


leveldb 
LSM  Log Structured Merge Tree 
MemTable + ImmutableMemTable + SSTables + log(WAL) + metadata-files



 LSM Tree 要点整理  

 leveldb简介   

 leveldb要点  
	

关键代码 摘录



static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
  
   BloomFilterStrategies.MURMUR128_MITZ_64
   
   
    /** The funnel to translate Ts to bytes */
  private final Funnel<? super T> funnel;

  /**
   * The strategy we employ to map an element T to {@code numHashFunctions} bit indexes.
   */
  private final Strategy strategy;
  
      
      

 long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    
  static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
      p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
  }
  
  static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
  }
  
   static final class BitArray {
    final long[] data;
    long bitCount;

    BitArray(long bits) {
      this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
    }
    
    
    /** Number of bits */
    long bitSize() {
      return (long) data.length * Long.SIZE;
    }

    /** Number of set bits (1s) */
    long bitCount() {
      return bitCount;
    }