Skip to content

Instantly share code, notes, and snippets.

@dabit
Last active May 16, 2023 16:57
Show Gist options
  • Save dabit/5592821 to your computer and use it in GitHub Desktop.
Save dabit/5592821 to your computer and use it in GitHub Desktop.
Code example for my blogpost Hash lookup in Ruby, why is it so fast?
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
@cagmz
Copy link

cagmz commented Sep 20, 2019

Nice work!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment