hash_functions.cr

# Benchmark of djb2, sdbm and lose lose hashing algorithms
# Algorithm descriptions: http://www.cse.yorku.ca/~oz/hash.html

# Output
#
# ===== djb2 =====
# Values: 5000000
# Collisions: 2988
# Time: 0.76589
# 
# ===== sdbm =====
# Values: 5000000
# Collisions: 2997
# Time: 1.16046
# 
# ===== lose =====
# Values: 5000000
# Collisions: 4995266
# Time: 0.463994




require "secure_random"

COUNT = 5_000_000

def rand_str
  SecureRandom.random_bytes(rand(10)+5).map(&.chr).join("")
end

# Generate random strings
strs = [] of String
COUNT.times { strs << rand_str }
strs.uniq!


def djb2(str : String) : UInt32
  hash = 5381_u32
  str.each_byte do |byte|
    hash = (hash << 5) + hash + byte
  end
  hash
end

def sdbm(str : String) : UInt32
  hash = 0_u32
  str.each_byte do |byte|
    hash = (hash << 6) + (hash << 16) - hash + byte
  end
  hash
end

def lose(str : String) : UInt32
  hash = 3231_u32
  str.each_byte do |byte|
    hash = hash + byte
  end
  hash
end


macro test_alg(name)
  def test_{{name}}(strs)
    hashes = Set(UInt32).new
    collision_count = 0

    strs.each do |str|
      hash = {{name}}(str)
      if hashes.includes?(hash)
        collision_count += 1
      else
        hashes << hash
      end
    end

    start_time = Time.now
    strs.each { |str| {{name}}(str) }
    duration = Time.now - start_time

    puts "Values: #{strs.size}"
    puts "Collisions: #{collision_count}"
    puts "Time: #{duration.to_f}"
  end

  puts "===== {{name}} ====="
  test_{{name}}(strs)
  puts
end


test_alg djb2
test_alg sdbm
test_alg lose