bloomfilter.rb

require 'zlib'

class BloomFilter
  def initialize(length = 100, hashes = 3, data = []) 
    @hashes = hashes
    @length = length
    @bits = Array.new(@length)
    @inserted = 0 

    add(data)
  end 

  def add(data)
    case data
      when Array then
        data.each { |item| item_add(item) }
      when String then
        item_add(data)
    end 
  end 

  def include?(item)
    srand(Zlib.crc32(item))
    @hashes.times { return false unless @bits[rand(@length)] }
    true
  end 

  def false_positive_prob
    (1.0 - (1.0 - 1.0/@length)**(@hashes * @inserted))**@hashes
  end 

  private

  def item_add(item)
    srand(Zlib.crc32(item))
    @hashes.times { @bits[rand(@length)] = true }
    @inserted += 1
  end 
end