Skip to content

Instantly share code, notes, and snippets.

@fauxparse
Created August 16, 2016 02:00
Show Gist options
  • Save fauxparse/b364b4026a9fb6c6979471c956663ece to your computer and use it in GitHub Desktop.
Save fauxparse/b364b4026a9fb6c6979471c956663ece to your computer and use it in GitHub Desktop.
Toy hashmap implementation
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment