public
Last active

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

  • Download Gist
hash_table.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.