Guava -- Bloom Filter原理

@Test
   public void test() {
       // 100w bit长度 ,0.01%误判率
       // bf对象则会生成 299534 个long数组,使用13次hash计算.
       BloomFilter<String> bf = BloomFilter
           .create(Funnels.stringFunnel(Charset.defaultCharset()), 100 * 10000, 0.0001d);
       
       System.out.println(bf.test("quding")); // false
       bf.put("quding"); // bitCount=13
       System.out.println(bf.test("quding")); // true
       bf.put("quding1"); // bitCount=26

   }

static final class LockFreeBitArray {
    private static final int LONG_ADDRESSABLE_BITS = 6;
    // long数组,表示超长bit位,使用Atomic提供原子操作能力,保证线程安全
    final AtomicLongArray data;
    // 当前数组中为1的bit位数量,其实现可以看错JDK8中的LongAdder
    private final LongAddable bitCount;
    
    LockFreeBitArray(long bits) {
        // 初始化时传入bit位,然后按照64位进行拆分计算,比如传入146bits,则会拆分位long[3]数组
      this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
    }
}

boolean set(long bitIndex) {
    if (get(bitIndex)) {
      return false;
    }
    // 定位到long数组对应的下标
    int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
    // 左移,将对应位置的bit位置为1,其他全是0
    long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex

    long oldValue;
    long newValue;
    do {
      oldValue = data.get(longIndex);
      // 或操作将对应bit位变成1
      newValue = oldValue | mask;
      if (oldValue == newValue) {
        return false;
      }
      // CAS保证原子性
    } while (!data.compareAndSet(longIndex, oldValue, newValue));

    // We turned the bit on, so increment bitCount.
    bitCount.increment();
    return true;
  }

MURMUR128_MITZ_32() {
    @Override
    public <T> boolean put(
        T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
      long bitSize = bits.bitSize();
      // 计算出一个hash值
      long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
      // 取低32位
      int hash1 = (int) hash64;
      // 取高32位
      int hash2 = (int) (hash64 >>> 32);

      boolean bitsChanged = false;
      // 根据hash次数分别计算出hash值,然后设置到bits数组中
      for (int i = 1; i <= numHashFunctions; i++) {
        int combinedHash = hash1 + (i * hash2);
        // Flip all the bits if it's negative (guaranteed positive number)
        if (combinedHash < 0) {
          combinedHash = ~combinedHash;
        }
        // 填充bits位
        bitsChanged |= bits.set(combinedHash % bitSize);
      }
      return bitsChanged;
    }
}

BF.RESERVE {key} {error_rate} {size}  初始化一个布隆过滤器
BF.ADD {key} {item}  添加单个元素
BF.EXISTS {key} {item} 是否存在
bf.madd {key} {item} [item...]  添加多个元素
BF.MEXISTS {key} {item} [item...]  判断多个元素是否存在