Last active

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

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

View hash_table.rb
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.