【アルゴリズムの勉強】Rubyでハッシュ法(チェイン法)を使用してデータの追加・検索・削除を行う
概要
ハッシュ法(チェイン法)を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。
チェイン法とは
衝突を起こしたキー同士をポインタでつなぐ方式を連鎖法と呼ぶ。テーブルの各番地にはキーそのものではなく、同族キーを保持するリンクリストを格納する。
Rubyで実装
original_data = [3, 6, 10, 12, 13, 15, 31, 40] KEY = 0 NEXT = 1 def create_hash_table(table_size) return Array.new(table_size) end def get_hash_value(key, table_size) return key % table_size end def add_data(key, hash_table, table_size) hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] while !target.nil? if target[KEY] == key puts "この値は既に追加済みです" return end target = target[NEXT] end data = [key, hash_table[hash_value]] hash_table[hash_value] = data end def delete_data(key, hash_table, table_size) hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] past_target = nil while !target.nil? if target[KEY] == key if past_target == nil hash_table[hash_value] = target[NEXT] else past_target[NEXT] = target[NEXT] end return end past_target = target target = target[NEXT] end puts "#{key}は見つかりませんでした" end def search(key, hash_table, table_size) hash_value = get_hash_value(key, table_size) target = hash_table[hash_value] while !target.nil? if target[KEY] == key puts "#{key}はハッシュテーブルに存在します" return end target = target[NEXT] end puts "#{key}は見つかりませんでした" end table_size = 5 hash_table = create_hash_table(table_size) p hash_table # => [nil, nil, nil, nil, nil] # 元のデータをハッシュテーブルに追加 original_data.each{|data| add_data(data, hash_table, table_size) } p hash_table # => [[40, [15, [10, nil]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil] # 新しくデータを追加 add_data(35, hash_table, table_size) p hash_table # => [[35, [40, [15, [10, nil]]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil] # 検索 search(15, hash_table, table_size) # => 15はハッシュテーブルに存在します # 削除 delete_data(15, hash_table, table_size) p hash_table # => [[35, [40, [10, nil]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil]