google / leveldb

LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values.
BSD 3-Clause "New" or "Revised" License
36.29k stars 7.8k forks source link

question about bloom.cc #1103

Closed infdahai closed 1 year ago

infdahai commented 1 year ago

I learn the source code https://github.com/google/leveldb/blob/main/util/bloom.cc#L40-#L51 .

dst->resize(init_size + bytes, 0);
    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
    char* array = &(*dst)[init_size];
    for (int i = 0; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }

when init_size equals to 0, dst push probes at pos 0. so the result reflects that [bitpos / 8] will not be equal to 0. Is that true?

emmm, please forgive me if I misunderstood this.