java - 代码逻辑 Guava 的 mightContain

Question

我正在浏览 Guava 库的代码，我有兴趣了解 mightContain 的概率匹配代码。任何人都可以解释一下他们在代码中做什么，特别是使用按位运算符。 这是代码......

public <T> boolean mightContain(T object, Funnel<? super T> funnel,
        int numHashFunctions, BitArray bits) {
      long hash64 = Hashing.murmur3_128().newHasher().putObject(object, funnel).hash().asLong();
      int hash1 = (int) hash64;
      int hash2 = (int) (hash64 >>> 32);
      for (int i = 1; i <= numHashFunctions; i++) {
        int nextHash = hash1 + i * hash2;
        if (nextHash < 0) {
          nextHash = ~nextHash;
        }
        // up to here, the code is identical with the previous method
        if (!bits.get(nextHash % bits.size())) {
          return false;
        }

Answer 1

假设这是来自 Bloomfilter 的代码类，逻辑是这样的:

给定 key ，对该 key 执行所有选定的哈希。使用每个散列来选择一个位数并检查该位是否已设置。如果过滤器中的该位置未设置任何位，则无法添加此键。

如果发现所有位都已设置，那么我们只能说过滤器可能已添加 key 。这是因为不同的 key (或多个不同 key 的组合)可能会导致设置所有检查的位。

请注意，向过滤器添加 key 几乎具有完全相同的功能，只不过它**设置**生成的所有位。

一个Bloom Filter对象的操作如下。

1. 选择数量个哈希函数，每个函数都会计算过滤器中一个位的位置。 (有关数量的讨论，请参阅 Optimal number of hash functions)。
2. 保存任意长度的位模式 - 长度并不重要，但它应该足够大(有关足够大含义的讨论，请参阅 Probability of false positives)。
3. 每次将 key 添加到过滤器时，都会对该 key 执行所有配置的哈希函数，从而在模式中设置多个位。
4. 要检查 key 是否已添加，请执行所有哈希函数并检查在那里找到的位。如果发现任何值为零，则该 key 肯定尚未添加到过滤器。
5. 如果发现所有位均已设置，则可能已添加此 key 。您需要执行进一步的检查来确认。