Evolving NaiveHash into RubyHash

naive_hash.rb

# Copy NaiveHash (end of this file) and rename to RubyHash.
#
# Try using RubyHash in irb/pry and store some data in it
# and notice it has problems with remembering all of your data due
# to RubyHash not handling hash collisions:
#
# require_relative 'ruby_hash'
# h = RubyHash.new
# ('a'..'z').each do |char|
#   h[char] = char.upcase
# end
# p h # Where'd the alphabet go?
#
# Improve RubyHash one step at a time in the order given below.
#
# Be sure to commit your changes to your data structures repo after 
# each step:
#
# 1. RubyHash doesn't yet handle collisions. If 2 different keys resolve
#    to the same hash index, only one key will be stored.
#
#    Handle collisions by allowing multiple key-value pairs to be kept
#    at the same index in @data. One way to do this is to introduce an
#    Array that holds all the key-value pairs located at the same index.
#
#    An example value of how `@data` could be in this scenario:
#
#    [
#      # Index 0, one pair, no collision
#      [ [:a_key, "a value"] ],
#
#      # Index 1, two colliding pairs
#      [ [:another_key, "another value"], [:yet_another_key, "yet another value"] ],
#
#      # Index 2, zero pairs
#      []
#    ]
#
#    Modify the methods on RubyHash to ensure they work correctly with
#    these changes.
#
# 2. Define a delete(key) method that deletes the relevant pair and
#    and returns the *value* from the deleted key-value pair.
#
# 3. Add a keys method to return all keys as an Array (order of keys
#    does not matter).
#
# 4. Add a key?(key) method that returns true if the given key
#    is in use, false otherwise.
#
# 5. Write a values method to return all values (no keys) as an Array
#    (order is not important).
#
# 6. Increase capacity to *twice the current capacity* and rehash when
#    4 collisions occur at the same index.
#
#    Add a log line to the method that grows the capacity:
#    puts "Growing capacity to #{new_capacity}!"
#
#    Run the following lines of code in irb/pry and notice the capacity
#    growing multiple times:
#
#    require_relative 'ruby_hash'
#    h = RubyHash.new
#    ('a'..'z').each { |char| h[char.to_sym] = char.upcase }
#
#    How large did the capacity grow to for the above code?
#
# 7. Using Prime numbers as capacities helps reduce the likelihood of
#    collisions.
#
#    Increase capacity to *the first prime number greater than twice the
#    current capacity* and rehash when 4 collisions occur at the same
#    index.
#
#    You can use Ruby's `Prime` to identify prime numbers with
#    `require 'prime'`
#
#    Docs: http://ruby-doc.org/stdlib-2.2.4/libdoc/prime/rdoc/Prime.html
#
#    Once implemented, repeat the experiment from the previous step.
#
#    How large did the capacity grow with the prime number capacities?

class NaiveHash

  attr_accessor :capacity, :data

  def initialize
    self.capacity = 3
    self.data = Array.new(capacity)
  end

  def []=(key, value)
    pair = [key, value]
    data[index(key)] = pair
    value # Return value to behave like Hash
  end

  def [](key)
    pair = data[index(key)]
    key_found = (pair && key == pair[0])
    key_found ? pair[1] : nil
  end

  private

  def index(key)
    key.hash % capacity
  end

end