【Ruby】【アルゴリズム】ハッシュテーブルの実装。衝突回避あり（一次団子現象回避Ver）

ハッシュテーブルとは

ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB

あえて、ハッシュ値が衝突するデータを追加していく。

ハッシュ値計算方法

  def _make_hash(str)
    size = self.array.size
    result = 0
    str.bytes.to_a.each_with_index do |ch, idx|
      result += ch << (4* (idx % 8))
    end
    result = result % size
  end

　
（例）

"abc" はアスキーコード[65, 66, 67]。
よって、(65*16**0 + 66*16**1 +67*16**2 ) %16 で 1

　
テーブルサイズを16にすることで、先頭以外の文字はhash値に影響しない。
言い換えると、"abc"も"a"も"aka"も全部 hash値が1なので、衝突しやすい。

作成したコード

class MyData
  attr_accessor :english, :japanese
  def initialize(english, japanese)
    @english = english
    @japanese = japanese
  end
  
end

class HashMap
  attr_accessor :array
  def initialize(size)
    @array = Array.new(size)
  end
  def clear
    @array.clear
  end

  #ハッシュ値を計算
  def _make_hash(str)
    size = self.array.size
    result = 0
    str.bytes.to_a.each_with_index do |ch, idx|
      result += ch << (4* (idx % 8))
    end
    result = result % size
  end
  def re_hash(hash)
    k =1
    max =  Math.sqrt(self.array.size).ceil
    while k < max do
      return hash + k*k if self.array[hash + k*k].nil?
      k += 1
    end
    -1
  end
  def add(data)
    hash = _make_hash(data.english)
    return self.array[hash] = data if self.array[hash].nil?
    hash = re_hash(hash)
    raise "mou ippai" if hash == -1    
    return self.array[hash] = data
  end

  def search(str)
    hash = _make_hash(str)
    return "naiyo" if self.array[hash].nil?
    k =0
    max =  Math.sqrt(self.array.size).ceil
    while k < max do
      data = self.array[hash + k*k]
      return data.japanese if data.english == str
      k += 1
    end
    "naiyo"
  end

  # pメソッド表示用
  def inspect
    self.array.delete(nil)
    self.array
  end
end

def dump(hash_map)
  p hash_map.array
end

hash_map = HashMap.new(16)
#ハッシュ値が同じ(0)データを追加する
hash_map.add(MyData.new("pen","enpitsu"))
hash_map.add(MyData.new("people","hitobito"))
hash_map.add(MyData.new("popular","ninki"))
hash_map.add(MyData.new("pop","karoyaka"))

dump(hash_map) #値が0,1,4,9 番目に格納されている
p hash_map

p hash_map.search("udon")
p hash_map.search("pokopen")

hash_map.add(MyData.new("poor","shishou")) #衝突によるエラー

実行結果

"p"はhash値が0。

[#<MyData:0x2b28fd0 @english="pen", @japanese="enpitsu">, #<MyData:0x2b28f40 @english="people", @japanese="hitobito">, nil, nil, #<MyData:0x2b28e80 @english="popular", @japanese="ninki">, nil, nil, nil, nil, #<MyData:0x2b28d48 @english="pop", @japanese="karoyaka">, nil, nil, nil, nil, nil, nil]
[#<MyData:0x2c78f58 @english="pen", @japanese="enpitsu">, #<MyData:0x2c78ec8 @english="people", @japanese="hitobito">, #<MyData:0x2c78e08 @english="popular", @japanese="ninki">, #<MyData:0x2c78cd0 @english="pop", @japanese="karoyaka">]
"naiyo"
"naiyo"
C:/h1.rb:43:in `add': mou ippai (RuntimeError)

ここでHashクラスの実装が見れるが良く分からず。