An associative array in Ruby

hash_table.rb

#!/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