A Look Into Bloom Filters with Ruby

bloom_v1.rb

require "fnv"
require "bitarray"

module BloomFilter
  class V1
    def initialize(opts = {})
      opts = {size: 1024}.merge(opts)
      @bits = BitArray.new opts[:size]
      @fnv = FNV.new
      @size = opts[:size]
    end

    def add(str)
      @bits[i(str)] = 1
    end

    def test(str)
      @bits[i(str)] == 1
    end

    alias_method :insert, :add
    alias_method :include?, :test

    private

    def i(str)
      @fnv.fnv1a_32(str) % @size
    end
  end
end

bloom_v2.rb

require "murmurhash3"
require "bitarray"
require "securerandom"

module BloomFilter
  class V2
    def initialize(opts = {})
      opts = {size: 1024, hashes: 3}.merge(opts)
      @bits = BitArray.new opts[:size]
      @seeds = seed(opts[:hashes])
      @size = opts[:size]
    end

    def add(str)
      set i(str)
    end

    def test(str)
      get i(str)
    end

    alias_method :insert, :add
    alias_method :include?, :test

    private

    def seed(iterations)
      s = []
      iterations.times { s << SecureRandom.hex(3).to_i(16) }
      s
    end

    def hash(str, seed)
      MurmurHash3::V32.str_hash(str, seed)
    end

    def i(str)
      @seeds.map { |seed| hash(str, seed) % @size }
    end

    def get(indexes)
      indexes.all? { |i| @bits[i] == 1 }
    end

    def set(indexes)
      indexes.each { |i| @bits[i] = 1 }
    end
  end
end

dumbfilter.rb

module DumbFilter
  class Array
    def initialize
      @data = []
    end

    def test(str)
      @data.include? str
    end

    def add(str)
      @data << str
    end
  end

  class Hash
    def initialize
      @data = {}
    end

    def test(str)
      @data[str]
    end

    def add(str)
      @data[str] = true
    end

    alias_method :insert, :add
    alias_method :include?, :test
  end
end

Gemfile

source "https://rubygems.org"

gem 'bitarray'
gem 'fnv'
gem 'murmurhash3'
gem 'bloomfilter-rb'