Last active
October 28, 2022 21:28
-
-
Save amiralles/e4a72901a6fff25d1521072c81eb02ed to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class HashTable | |
class Slot | |
attr_accessor :key, :value, :vacated | |
def initialize key, value | |
self.key = key | |
self.value = value | |
self.vacated = true | |
end | |
# Marks the slot as free. | |
def free | |
self.value = nil | |
self.vacated = true | |
end | |
end | |
# Appropiate number of slots for incremental rebuilds. | |
# On production hash tables this array sould contain | |
# way more entries. May the max number of entries | |
# shold be up to a couple of millions. | |
PRIMES = [13, 31, 61, 127, 251, 509] | |
MAX_REBUILDS = 6 # Up most equal to PRIMES.count | |
attr_accessor :size | |
def initialize | |
# To ensure that all slots are visited before any position gets | |
# visited twice, we have to set *slots* to a prime number and make | |
# sure that *h2* returns a possitive number less than slots. | |
# To keep the load factor healthy, the number of *slots* should | |
# roughly two times the number of keys we need to store. | |
# We start with just few entries. | |
@slots = 5 | |
self.size = 0 | |
@rebuilds = 0 | |
@h1 = -> (k) { k % @slots } | |
@h2 = -> (k) { 1 + (k % (@slots - 1)) } | |
fill_table @slots | |
end | |
# Idiomatic way to get an entry. | |
def [](key) | |
get(key) | |
end | |
# Idiomatic way to upsert an entry. | |
def []=(key, value) | |
upsert(key, value) | |
end | |
def delete key | |
find_slot(key)&.free | |
end | |
# Prints the contents of the hash table. | |
# (Mostly for debugging purposes.) | |
def print | |
@table.each do |e| | |
if e | |
puts "#{e.key}: #{e.value}" | |
else | |
puts "empty" | |
end | |
end | |
end | |
private | |
def get key | |
find_slot(key)&.value | |
end | |
def double_hash hashcode, idx | |
h1 = @h1.call(hashcode) | |
h2 = @h2.call(hashcode) | |
((h1 + (idx * h2)) % @slots).abs() | |
end | |
# Initializes the internal storage for the hash table. | |
def fill_table slots | |
@table = [] | |
0.upto(slots - 1) { @table << nil } | |
end | |
# Rebuilds the hash table to accommodate more entries. | |
def rebuild | |
raise "Too many entries." if @rebuilds >= MAX_REBUILDS | |
old = @table | |
@slots = PRIMES[@rebuilds] | |
self.size = 0 | |
fill_table @slots | |
old.each do |e| | |
upsert e.key, e.value if e | |
end | |
@rebuilds += 1 | |
end | |
# Inserts a new entry or updates an existing one. | |
def upsert key, value | |
# Is there enough room for the new entry. | |
rebuild if self.size > (@slots / 2) | |
# If an entry already exists, update an return. | |
if (slot = find_slot(key)) | |
slot.value = value | |
return | |
end | |
# "Double hash" the key to an index position and | |
# insert the new entry. | |
0.upto(@slots - 1) do |i| | |
# We use the hashcode for the key, not the | |
# key itself. | |
index = double_hash key.hash, i | |
slot = @table[index] | |
if slot.nil? || slot.vacated | |
@table[index] = Slot.new key, value | |
self.size += 1 | |
return | |
end | |
end | |
raise "Weak hash function." | |
end | |
# Returns the slot in the table that matches the | |
# given key or nil is there isn't one. | |
def find_slot key | |
# double hash key to index. | |
0.upto(@slots - 1) do |i| | |
# Again, we use the key's hash code | |
# not the key itself. | |
index = double_hash key.hash, i | |
slot = @table[index] | |
return nil if slot.nil? || slot.vacated | |
return slot if slot.key == key | |
end | |
nil | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The
vacated
flag should be false in the initialize block of the Slot :)