Ruby でハッシュテーブルを実装する

ハッシュテーブルというデータ構造について理解するために書いた.

ここを参考に.
http://www.geocities.jp/ky_webid/algorithm/014.html

hash_table.rb

# coding: utf-8
class HashTable
  class Bucket
    attr_reader :key, :value, :next_cell

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

  TABLE_SIZE = 10

  def initialize
    @table = Array.new(TABLE_SIZE)
  end

  def []=(key, value)
    raise '既に存在するキーです' unless self[key].nil?

    hash_key = hash(key)
    cell = Bucket.new(key, value, @table[hash_key])
    @table[hash_key] = cell
  end

  def [](key)
    hash_key = hash(key)
    cell = @table[hash_key]
    while cell do
      return cell.value if cell.key == key
      cell = cell.next_cell
    end
  end

  private
  def hash(key)
    key % TABLE_SIZE
  end
end

hash_table_spec.rb

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

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

  context 'キーに値が存在しないとき' do
    subject { table[0] }
    it { should be_nil }
  end

  context 'キーに値が存在するとき' do
    before { table[0] = :foo }
    subject { table[0] }
    it { should == :foo }
  end

  context '既に値が存在するキーにもう一度値をセットしたとき' do
    before { table[0] = :foo }
    it 'エラーを投げる' do
      proc { table[0] = :bar }.should raise_error
    end
  end

  context 'ハッシュが競合するキーに値をセットしたとき' do
    before do
      table[0] = :foo
      table[10] = :bar
    end

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

データ構造がどういう風になっているか, pp で示してみる.

test.rb

require './hash_table'
require 'pp'

ht = HashTable.new
ht[0] = :foo
ht[1] = :bar
ht[10] = :baz # 0 とハッシュが競合

pp ht

# <HashTable:0x007fa0c282cbd8
 @table=
  [#<HashTable::Bucket:0x007fa0c282ca98
    @key=10,
    @next_cell=
     #<HashTable::Bucket:0x007fa0c282cb38 @key=0, @next_cell=nil, @value=:foo>,
    @value=:baz>,
   #<HashTable::Bucket:0x007fa0c282cae8 @key=1, @next_cell=nil, @value=:bar>,
   nil,
   nil,
   nil,
   nil,
   nil,
   nil,
   nil,
   nil]>