Ruby でハッシュテーブルを実装する (オープンアドレス法)

ここを参考にした.
http://www.geocities.jp/ky_webid/algorithm/015.html

元の記事だと空や削除済みを表現するのに定数を使っていたけど, こっちでは Rubyish にダックタイピングでやってみた.
(全体的にはそんな Rubyish になってないけど)

hash_table.rb

# coding: utf-8
class HashTable
  TABLE_SIZE = 10

  class Bucket
    attr_reader :key, :value

    def initialize(key, value)
      @key, @value = key, value
    end

    def empty?
      false
    end

    def deleted?
      false
    end
  end

  class EmptyBucket
    [:key, :value].each do |method|
      class_eval "def #{method}; nil; end"
    end

    def empty?
      true
    end

    def deleted?
      false
    end
  end

  class DeletedBucket < EmptyBucket
    def empty?
      false
    end

    def deleted?
      true
    end
  end

  def initialize
    @table = Array.new(TABLE_SIZE).map{ EmptyBucket.new }
  end

  def []=(key, value)
    hash_key = hash(key)
    @table.each do
      bucket = @table[hash_key]
      if bucket.empty? or bucket.deleted?
        @table[hash_key] = Bucket.new(key, value)
        return value
      end
      raise '既にキーが存在します' if bucket.key == key
      hash_key = rehash(hash_key)
    end
    raise 'テーブルがいっぱいです'
  end

  def [](key)
    hash_key = hash(key)
    @table.each do |n|
      bucket = @table[hash_key]
      break if bucket.empty?
      return bucket.value if not bucket.deleted? and bucket.key == key
      hash_key = rehash(hash_key)
    end
    nil
  end

  def delete(key)
    hash_key = hash(key)
    @table.each do
      bucket = @table[hash_key]
      break if bucket.empty?
      if not bucket.deleted? and bucket.key == key
        @table[hash_key] = DeletedBucket.new
        return
      end
      hash_key = rehash(hash_key)
    end
    raise 'キーが見つかりません'
  end

  private
  def hash(key)
    key % TABLE_SIZE
  end

  def rehash(key)
    (key + 1) % TABLE_SIZE
  end
end

hash_table_spec.rb

# coding: utf-8
require './hash_table'

describe HashTable do
  let(:table) { HashTable.new }

  describe '#[]' do
    subject { table[0] }

    context '存在しないキーを指定したとき' do
      it { should be_nil }
    end

    context 'キーに値をセットしたとき' do
      before { table[0] = :foo }
      it { should == :foo }
    end

    context 'ハッシュが競合したとき' do
      before do
        table[0] = :foo
        table[10] = :bar
      end

      it { table[0].should == :foo }
      it { table[10].should == :bar }
    end

    context 'キーが削除されたとき' do
      before do
        table[0] = :foo
        table.delete 0
      end
      it { should be_nil }
    end
  end

  describe '#[]=' do
    context '既にキーが存在するとき' do
      before { table[0] = :foo }
      it 'エラーを投げる' do
        proc { table[0] = :bar }.should raise_error
      end
    end

    context 'テーブルがいっぱいのとき' do
      before { HashTable::TABLE_SIZE.times {|n| table[n] = n } }
      it 'エラーを投げる' do
        proc { table[999] = :foo }.should raise_error
      end
    end
  end

  describe '#delete' do
    context 'キーが存在しないとき' do
      it 'エラーを投げる' do
        proc { table.delete 0 }.should raise_error
      end
    end

    context 'ハッシュが競合したとき' do
      before do
        table[0] = :foo
        table[10] = :bar
        table.delete 10
      end

      it '正しくキーを削除する' do
        table[0].should == :foo
        table[10].should be_nil
      end
    end
  end
end