Skip to content

Instantly share code, notes, and snippets.

@hcgatewood
Last active December 23, 2019 08:23
Show Gist options
  • Save hcgatewood/9645ce9781adc6d008a7 to your computer and use it in GitHub Desktop.
Save hcgatewood/9645ce9781adc6d008a7 to your computer and use it in GitHub Desktop.
An associative array in Ruby
#!/usr/bin/env ruby
# A simple hash table implementation in Ruby using Ruby's built-in
# prehashing methods, chaining, and variable load factors.
#
# Author:: Hunter Gatewood
# A linked-list node with key, value, and next node attributes.
class Node
attr_accessor(:key, :val, :next_node)
def initialize(key, val, next_node = nil)
@key = key
@val = val
@next_node = next_node
end
end
# A basic singly-linked list.
class LinkedList
def initialize(key, val)
@base_node = Node.new(key, val)
end
def nodes
nodes = []
node = @base_node
until node.nil?
nodes << node
node = node.next_node
end
nodes
end
def get_val_from_key(key)
node = @base_node
until node.nil?
return node.val if node.key.equal? key
node = node.next_node
end
nil
end
# Return true if a node was deleted, false otherwise
def del_node(key)
if @base_node.key.equal? key
@base_node = @base_node.next_node
return true
end
node = @base_node
until node.next_node.nil?
if node.next_node.key.equal? key
node.next_node = node.next_node.next_node
return true
end
node = node.next_node
end
false
end
# Return true if a *new* node was added, false otherwise
def add_node(key, val)
node = @base_node
until node.nil?
if node.key.equal? key
node.val = val
return false
end
prev_node = node
node = node.next_node
end
prev_node.next_node = Node.new(key, val)
true
end
end
# Hash table implementation
class HashTable
def initialize(array_size = 2, max_load_factor = 0.67,
min_load_factor = 0.2, num_entries = 0, allow_resize = true)
@array = []
@num_entries = num_entries
@array_size = [array_size, 2].max
@max_load_factor = max_load_factor
@min_load_factor = min_load_factor
@allow_resize = allow_resize
end
def []=(key, val)
key_hash = hash_value(key)
list = @array[key_hash]
if list.nil?
@array[key_hash] = LinkedList.new(key, val)
else
if list.add_node(key, val)
@num_entries += 1
manage_array_size
end
end
end
def delete(key)
key_hash = hash_value(key)
list = @array[key_hash]
if list.nil?
return nil
else
if list.del_node(key)
@num_entries -= 1
manage_array_size
end
end
self
end
def [](key)
list = @array[hash_value(key)]
if list.nil?
return nil
else
list.get_val_from_key(key)
end
end
def inspect
pairs = []
nodes.each { |node| pairs << "#{node.key.inspect}: #{node.val.inspect}" }
"{#{pairs.join(', ')}}"
end
def object_view
method(:inspect).super_method.call
end
private
attr_accessor :allow_resize
def nodes
nodes = []
@array.compact.each { |list| nodes += list.nodes }
nodes
end
def hash_value(key, array_size = @array_size)
key.hash % array_size
end
def manage_array_size
return unless allow_resize
load_factor = @num_entries / @array_size.to_f
if load_factor > @max_load_factor
change_array_size(:up)
elsif load_factor < @min_load_factor
change_array_size(:down)
end
# Catch-all for when max load factor is poorly set
change_array_size(:up) if @num_entries == @array_size
end
def change_array_size(direction)
tmp_nodes = nodes.clone
@array_size = direction == :up ? [@array_size * 2, 2].max : [@array_size / 2, 2].max
@array.clear
@num_entries = 0
@allow_resize = false
tmp_nodes.each { |node| self[node.key] = node.val }
@allow_resize = true
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment