簡易的なBloomFilterの実装

bloom_filter.rb

require 'murmurhash3'

class BloomFilter

  SEED_BASE = 0xFBA4C795

  attr_reader :bits
  attr_reader :hash_funcs
  attr_reader :tweak

  def initialize(n, k, tweak)
    @bits = Array.new(n, 0) # ビット列
    @tweak = tweak # 乱数
    @hash_funcs = k # ハッシュ関数の数
  end

  # フィルタに要素を追加
  def add(data)
    calc_index(data).each do |i|
      bits[i] = 1
    end
  end

  # フィルタに要素が登録されているか確認
  def contains?(data)
    calc_index(data).map{|i|bits[i]}.find{|i| i == 0}.nil?
  end

  private

  def calc_index(data)
    list = []
    hash_funcs.times do |i|
      seed = (i * SEED_BASE + tweak) & 0xffffffff
      hash = MurmurHash3::V32.str_hash(data, seed)
      list << hash % bits.length
    end
    list
  end
end