マップとハッシュ（ハッシュマップ）

7月 13th, 2008 admin Posted in Ruby, アルゴリズムとデータ構造 |

今回は「アルゴリズムとデータ構造シリーズ」です。前回に続いて第7章「マップとハッシュ」のハッシュマップの実装について。

ハッシュ値が重複した場合の対策

ハッシュ値が重複した場合には「k^2番目に再ハッシュする」という方法で対応した。
たとえばハッシュ値が2だった場合には
・３（２＋１＊１）
・６（２＋２＊２）
・１１（２＋３＊３）
と試していく方法だ。

コード

検索と削除の部分は少しずるをしました。

PLAIN TEXT
RUBY:
  1. #Hash Map
  2. $KCODE = "SJIS"
  3.  
  4. class WordSet
  5.   attr_accessor :english, :japanese
  6.   def initialize(english = nil, japanese = nil)
  7.     @english = english
  8.     @japanese = japanese
  9.   end
  10. end
  11.  
  12. class HashMap
  13.   def initialize(size)
  14.     @hash_table_size = size
  15.     @hash_table = Array.new
  16.   end
  17.  
  18.   def make_hash(str)
  19.     weight = 0
  20.     hash = 0
  21.     str.each_byte{|s|
  22.       weight = 0 if weight> 7
  23.       hash += s * (256 ** weight)
  24.       weight+=1
  25.     }
  26.     hash % @hash_table_size
  27.   end
  28.  
  29.   def add_data(ws)
  30.     hash_val = self.make_hash(ws.english)
  31.  
  32.     unless @hash_table[hash_val].nil?
  33.       hash_val = self.rehash(hash_val)
  34.       if(hash_val == -1)
  35.         printf("%sをマップに挿入しようとしましたが、空き位置がありませんでした",ws.english)
  36.         return
  37.       end 
  38.     end
  39.    
  40.     @hash_table[hash_val] = ws
  41.   end
  42.  
  43.   def rehash(first_hash_val)
  44.     #k^2に再ハッシュする
  45.     (1...(@hash_table_size/2)).each do |k|
  46.       hash_val = (first_hash_val+k*k) % @hash_table_size
  47.       return hash_val if @hash_table[hash_val].nil?
  48.     end
  49.     return -1
  50.   end
  51.  
  52.   def find(str)
  53.     hash_val = self.make_hash(str)
  54.     return @hash_table[hash_val]
  55.   end
  56.  
  57.   def delete(str)
  58.     hash_val = self.make_hash(str)
  59.     @hash_table[hash_val] = nil
  60.     return true
  61.   end
  62.  
  63.   def print_all_data
  64.     @hash_table.each do |val|
  65.       printf("%s\t\t%s\n",val.english,val.japanese) unless val.nil?
  66.     end
  67.   end
  68. end
  69.  
  70. init_data = [
  71.                   WordSet.new("lisp","リスプ"),
  72.                   WordSet.new("C","シー"),
  73.                   WordSet.new("ruby","ルビー"),
  74.                   WordSet.new("perl","パール"),
  75.                   WordSet.new("python","パイソン"),
  76.                   WordSet.new("PHP","ピーエイチピー"),
  77.                   WordSet.new("JavaScript","ジャバスクリプト")
  78.                 ]
  79.                
  80. hash_map = HashMap.new(503)
  81.  
  82. init_data.each do |ws|
  83.   hash_map.add_data(ws)
  84. end
  85.  
  86. i = nil
  87. loop do 
  88.   print "コマンドを入力して下さい\n1:表\ 2:検索 3:削除\n"
  89.   i = gets.chomp.to_i
  90.  
  91.   case i
  92.     when 1
  93.       hash_map.print_all_data
  94.     when 2
  95.       print "検索する文字列を入力してください："
  96.       j = gets.chomp
  97.       if ws = hash_map.find(j)
  98.         printf("%sは日本語で「%s」です。 \n\n",ws.english,ws.japanese)
  99.       else
  100.         print("見つかりませんでした。\n\n")
  101.       end
  102.     when 3
  103.       print "削除する文字列を入力してください："
  104.       j = gets.chomp
  105.       if hash_map.delete(j)
  106.         printf("削除しました。 \n\n")
  107.       else
  108.         print("見つかりませんでした。\n\n")
  109.       end   
  110.   end
  111. end

まとめ

ハッシュというものがどういうものか（そもそもなんでハッシュと呼ばれているのか）わかって非常にすっきりできた。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Leave a Reply