マップとハッシュ

• ハッシュマップ

ハッシュマップ

基本的な考え方

　頻繁に追加・削除される大量のデータから、ある文字列をキーにして目的の値を素早く取り出したい場合に有効。

1. ハッシュ表を用意する
2. ハッシュ値を決める
3. データを格納する
4. データを検索する
5. データを削除する

　以上を実装する必要がある。

def makeHash1(str, hashmax)
  hash = 0
  n = 0
  str.each_byte{|byte|
    hash += byte
  }
  return hash % hashmax
end

def makeHash2(str, hashmax)
  hash = 0
  weight = 0
  str.each_byte do |byte|
    if weight > 7
      weight = 0
    end
    hash += byte << (4 * weight)
    weight += 1
  end
  return hash % hashmax
end

puts "makeHash1を使った場合"
p makeHash1("this", 100)       # => 40
p makeHash1("itsh", 100)       # => 40

puts "makeHash2を使った場合"
p makeHash2("this", 100)       # => 0
p makeHash2("itsh", 100)       # => 85

　ハッシュ表のサイズは素数にするのが一般的。よく使われる値としては、
　「89, 179, 503, 1009, 2003, 3001, 4001, 5003, 10007」

　しかし、それでも重複を完全に避けられるわけではない。対策としては、

1. 同じハッシュ値を持つデータをリストにする
• リストではなく2分木を使う
2. ハッシュ表の次の位置に入れてしまう
• 最初に衝突が起きた位置から k^2 番目の位置にデータを入れる

class WordSet
  attr_reader :english, :japanese
  def initialize( english, japanese )
    @english = english
    @japanese = japanese
  end
end

class HashTable
  attr_accessor :data, :size
  def initialize
    @data = Array.new
    @size = nil
  end
end


class Dictionary
  def main()
    words = [
      WordSet.new("dolphin", "イルカ"),
      WordSet.new("beluga", "シロイルカ"),
      WordSet.new("grampus", "シャチ"),
      WordSet.new("medusa", "海月")
      ]
    hashTable = HashTable.new
    initHashTable(hashTable, 503)
    
    words.each do |word|
      addDataToMap(hashTable, word)
    end
    
    action = nil
    while action != 0
    p hashTable.data.size
    p hashTable
      puts "1:検索 2:削除 3:全表示 0:終了"
      action = gets.chomp.to_i
      case action
        when 1
          puts "検索する英単語を入力して下さい"
          key = gets.chomp
          japanese = getDataFromMap(hashTable, key)
          if japanese != nil
            puts "#{key} の和訳は 「#{japanese}」です。"
          else
            puts "#{key}が見つからなかった"
          end
        when 2
          puts "削除する英単語を入力して下さい"
          key = gets.chomp
          wordFound = deleteDataFromMap(hashTable, key)
          if wordFound != nil
            puts "#{key}をマップから削除しました"
          else
            puts "#{key}が見つからなかった"
          end
        when 3
          printAllData(hashTable)
      end
    end
  end
  
  private
  def makeHash2( str, hashMax )
    hash = 0
    weight = 0
    
    str.each_byte do |byte|
      if weight > 7
        weight = 0
      end
      hash += byte << (4 * weight)
      weight += 1
    end
    return hash % hashMax
  end
  
  def reHash( hashTable, firstHash )
    hashValue = firstHash
    # firstValue から k^2 だけ後ろにある空き位置を探す
    # 「k > ハッシュ表サイズの半分」となったら、それ以降の探索は無駄
    k = 1
    while k < hashTable.size / 2
      if hashTable.data[hashValue] != nil
        return hashValue
      end
      k += 1
    end
    # 空き位置が見つからなければ -1 を返す
    return -1
  end
  
  def addDataToMap( hashTable, newData )
    # 英単語を元にハッシュ値を生成
    hashValue = makeHash2(newData.english, hashTable.size)
    
    # hash の位置がすでに埋まっていたら、再ハッシュを行う
    if hashTable.data[hashValue] != nil
      hashValue = reHash(hashTable, hashValue)
      if hashValue == -1
        puts "#{newData.english} をマップに挿入しようと試みましたが、空き位置がありませんでした"
        return
      end
    end
    # hashValue の位置に newData を格納
    hashTable.data[hashValue] = newData
  end
  
  def getDataFromMap( hashTable, key )
    # 探索を開始するハッシュ値を求める
    hashValue = makeHash2(key, hashTable.size)
    word = nil
    # 探索
    k = 0
    while k <= hashTable.size / 2
      word = hashTable.data[(hashValue + k * k) % hashTable.size]
      if word != nil
        if key == word.english
          return word.japanese
        end
      end
      k += 1
    end
    return nil
  end
  
  def deleteDataFromMap( hashTable, key )
    # 探索を開始するハッシュ値を求める
    hashValue = makeHash2(key, hashTable.size)
    word = nil
    k = 0
    while k < hashTable.size / 2
      word = hashTable.data[(hashValue + k * k) % hashTable.size]
      if word != nil
        if key == word.english
          hashTable.data[(hashValue + k * k) % hashTable.size] = nil
          return word
        end
      end
      k += 1
    end
    return nil
  end
  
  def initHashTable( hashTable, size )
    i = 0
    while i < size
      hashTable.data[i] = nil
      i += 1
    end
    hashTable.size = size
  end
  
  def printAllData( hashTable )
    n = 0
    while n < hashTable.size
      if hashTable.data[n] != nil
        puts "#{n} :¥t#{hashTable.data[n].english}¥t#{hashTable.data[n].japanese}"
      end
      n += 1
    end
  end
end

dictionary = Dictionary.new
dictionary.main