読者です 読者をやめる 読者になる 読者になる

【アルゴリズムの勉強】Rubyでハッシュ法(チェイン法)を使用してデータの追加・検索・削除を行う

概要

ハッシュ法(チェイン法)を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。

チェイン法とは

衝突を起こしたキー同士をポインタでつなぐ方式を連鎖法と呼ぶ。テーブルの各番地にはキーそのものではなく、同族キーを保持するリンクリストを格納する。

ハッシュテーブル - Wikipedia

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]

参考文献、参考リンク