Toy hashmap implementation

hashmap.rb

require 'singleton'

class HashMap
  DEFAULT_SIZE = 256
  DEFAULT_LOAD = 0.75

  def initialize(size: DEFAULT_SIZE, load: DEFAULT_LOAD)
    @size = size
    @load = load
    @count = 0
  end

  def empty?
    count == 0
  end

  def [](key)
    item = get(key)
    if item.empty?
      default_value
    else
      item.value
    end
  end

  def []=(key, value)
    put(key, value)
  end

  def keys
    values.flat_map(&:keys).sort
  end

  def delete(key)
    index = hash(key)
    item = values[index]
    count = values[index].count
    values[index] = values[index].delete(key)
    @count -= count - values[index].count
  end

  def count
    @count
  end

  def default_value
    nil
  end

  private

  def values
    @values ||= Array.new(@size, Empty.instance)
  end

  def hash(key)
    key.chars.inject(0) { |hash, char| ((hash << 1) ^ char.ord) & (@size - 1) }
  end

  def resize!
    old = @values
    @values = nil
    @size = @size * 2

    old.each do |item|
      item.values.each { |item| put(item.key, item.value) unless item.empty? }
    end
  end

  def put(key, value)
    if (item = get(key)).empty?
      item = Item.new(key, value)
      index = hash(item.key)
      item.next_item = values[index]
      values[index] = item
      @count += 1
      resize! if @count > @size * @load
    else
      item.value = value
    end
  end

  def get(key)
    item = values[hash(key)]
    item = item.next_item while !item.empty? && item.key != key
    item
  end

  class Item
    attr_reader :key
    attr_accessor :value, :next_item

    def initialize(key, value)
      @key, @value = key, value
      @next_item = Empty.instance
    end

    def values
      [self] + next_item.values
    end

    def empty?
      false
    end

    def count
      1 + next_item.count
    end

    def keys
      [key] + next_item.keys
    end

    def delete(key)
      if key == @key
        next_item
      else
        @next_item = next_item.delete(key)
        self
      end
    end
  end

  class Empty
    include Singleton

    def keys
      []
    end

    def values
      []
    end

    def empty?
      true
    end

    def next_item
      self
    end

    def count
      0
    end

    def delete(key)
      self
    end
  end
end

hashmap_spec.rb

require './hashmap.rb'

RSpec.describe HashMap do
  subject(:map) { HashMap.new }

  context 'when empty' do
    it { is_expected.to be_empty }

    describe '#count' do
      subject { map.count }
      it { is_expected.to eq 0 }
    end

    describe '#[]' do
      subject { map["fruit"] }
      it { is_expected.to eq nil }
    end

    describe '#[]=' do
      it 'updates the count' do
        expect { map["fruit"] = %w(apples oranges bananas) }.to change { map.count }.by 1
      end
    end

    describe '#keys' do
      subject { map.keys }
      it { is_expected.to be_empty }
    end
  end

  context 'with some content' do
    subject(:map) do
      HashMap.new.tap do |map|
        map["fruit"] = %w(apples oranges bananas)
        map["vegetables"] = %w(potatoes carrots)
        map["meats"] = %w(beef pork chicken lamb)
      end
    end

    it { is_expected.not_to be_empty }

    describe '#count' do
      subject { map.count }
      it { is_expected.to eq 3 }
    end

    describe '#[]' do
      subject { map["fruit"] }
      it { is_expected.to eq %w(apples oranges bananas) }
    end

    describe '#keys' do
      subject { map.keys }
      it { is_expected.to eq %w(fruit meats vegetables) }
    end

    context 're-setting a key' do
      it 'does not change the count' do
        expect { map["fruit"] = %w(pineapples) }
          .not_to change { map.count }
      end
    end

    describe '#delete' do
      %w(fruit vegetables meats).each do |key|
        it "deletes #{key}" do
          expect { map.delete(key) }.to change { map.count }.by -1
        end
      end
    end
  end
end