bloom filter in 65 minutes in julia.

bloom.jl

#bloom.jl - takes a file, reads binary data from the file and does whatever a
#bloom filter would do.

doc"""
  `BloomFilter{V}`
  defines a bloom filter over a value type V
"""
type BloomFilter{V}
  filter::BitVector
  hashes::Array{Function, 1}
end

function add!{V}(b::BloomFilter{V}, v::V)
  for hash in b.hashes
    b.filter[hash(v) + 1] = true
  end
end

function query{V}(b::BloomFilter{V}, v::V)
  for hash in b.hashes
    b.filter[hash(v) + 1] || return false
  end
  return true
end

function getbyte(v::UInt64, b)
  reinterpret(UInt8, [v])[b]
end

#let's implement murmurhash.
function murmurhash(val::Vector{UInt64}, len, seed::UInt64)
  const m = 0xc6a4a7935bd1e995
  const r = 47
  h = seed $ (len * m)

  trailingbytes = len & 7

  if (trailingbytes == 0)
    count = length(val)
  else
    count = length(val) - 1
  end

  for idx in 1:count
    v = val[idx] * m
    v $= v >> r
    v *= m

    h $= v
    h *= m
  end

  #deal with the last segment of data.
  if ((trailingbytes) != 0)
    lastpart = val[end]
    h $= getbyte(lastpart, trailingbytes - 1) << (8 * (trailingbytes - 1))
  end

  h
end

function getchar(s::String, idx)
  idx > length(s) ? UInt8(0) : UInt8(s[idx])
end

function murmurstring(s::String, modval)
  len = length(s)
  leftovers = len % 8
  fullquads = div(len, 8)
  #allocate the UInt64 array
  uarray = zeros(UInt64, fullquads + (leftovers != 0))
  for idx in 1:(length(uarray) * 8)
    uarray[div((idx - 1), 8) + 1] |= (UInt64(getchar(s, idx)) << ((idx % 8) * 8))
  end
  murmurhash(uarray, len, one(UInt64)) % modval
end

function create_string_murmurbloom(n)
  #assemble a functional that takes a string and performs a murmurhash on it.
  BloomFilter{String}(falses(n), [(s) -> murmurstring(s, n)])
end

#executed test code:
#julia> include("bloom.jl")
#create_string_murmurbloom (generic function with 1 method)
#
#julia> bf = create_string_murmurbloom(10)
#BloomFilter{String}(Bool[false,false,false,false,false,false,false,false,false,false],Function[#1])
#
#julia> bf.hashes[1]("hello")
#0x0000000000000006
#
#julia> add!(bf, "hello")
#
#julia> query(bf, "goodbye")
#false
#
#julia> query(bf, "hello")
#true