hash_table.rb

require 'benchmark'

#
# Code example for my blogpost
#
# Hash lookup in Ruby, why is it so fast?
#

#
# Struct used to store Hash Entries
#
HashEntry = Struct.new(:key, :value)

#
# HashTable class, could be considered the Hash itself, but
# we'll use HashTable instead to avoid naming conflicts.
#
class HashTable
  attr_accessor :bins
  attr_accessor :bin_count

  def initialize
    # Increase the bin number to reduce lookup times
    self.bin_count = 3000000
    self.bins = []
  end

  #
  # Used to push a HashEntry
  #
  def <<(entry)
    index = bin_for(entry.key)
    self.bins[index] ||= []
    self.bins[index] << entry
  end

  #
  # Retrieve a HashEntry by looking for its key
  #
  def [](key)
    index = bin_for(key)
    self.bins[index].detect do |entry|
      entry.key == key
    end
  end

  #
  # Calculate the corresponding bin index
  # depending on the key's hash value.
  #
  def bin_for(key)
    key.hash % self.bin_count
  end
end

#
# Create a HashTable object
#
table = HashTable.new

#
# Create 1,000,000 HashEntries and push them to the
# HashTable
#
(1..1000000).each do |i|
  entry = HashEntry.new i.to_s, "bar#{i}"

  table << entry
end

#
# Try to find an entry at the beginning, middle and end
# of the list.
#
%w(100000 500000 900000).each do |key|
  time = Benchmark.realtime do
    table[key]
  end

  puts "Finding #{key} took #{time * 1000} ms"
end