2

I am reading the Bloom Filter implementation written in ruby. It should have k hash functions, but it looks like the same hash function is being used with different seed values. Is this a common way to implement this Data Structure, or is this just an exercise in this case?

https://github.com/igrigorik/bloomfilter-rb/blob/master/examples/pure-ruby-bf.rb

def make_mask(key)
    @__mask.clear
    0.upto(@num_hashes.to_i - 1) do |i|
      hash = Zlib.crc32(key, i + @seed)
      @__mask.set(hash % @size, 1)
    end
    return @__mask
  end
3

Yes, literature indicates that it is ok, and common, to reuse a hash function to produce k hash functions, specifically if the hash function takes a seed value. This is apparently the case in the Ruby sample you provided. For large k, finding unique hash functions can be challenging. Of course, this supposes a good hash function, in the first place.

Not only can a hash function be reused, but a single hash value can be sliced into separate bit fields. This helps runtime efficiency in that it reduces the number of actual hash calls to be made, and since we know that k dominates the performance of the algorithm, this might be a valuable optimization. For a good hash function, the bit regions of a single hash value should be independent hash keys in their own right. In other words, I can call hash(i) to produce a 64-bit result, then slice that into 4 x 16-bit sub-keys which can produce a k of 4. Much more efficient than iterating through 4 hash calls. When you consider we usually mod the hash value by a small bucket size anyway, we are often not using the full potential of a hash key for a hash table, and Bloom filters give us a better way to do that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.