【アルゴリズムの勉強】Rubyでハッシュ法（オープンアドレス法）を使用してデータの追加・検索・削除を行う

Ruby アルゴリズム

概要

ハッシュ法（オープンアドレス法）を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。

オープンアドレス法とは

衝突が発生した際、テーブル中の空いている別の番地を探す方式を開番地法と呼ぶ。その方法としてハッシュ関数とは別の関数を用いて次の候補となる番地を求める。別の番地を探す関数は繰り返し適用することによってテーブル内の全ての番地を走査できるように選ぶ。

ハッシュテーブル - Wikipedia

Rubyで実装

OCCUPIED = 0
EMPTY = 1
DELETED = 2
KEY = 0
STATUS = 1
ALONE = true

def create_hash_table(table_size)
  return Array.new(table_size, [nil, EMPTY])
end

def get_hash_value(key, table_size)
  return key % table_size
end

def get_rehash_value(hash_value, table_size)
  return (hash_value + 1) % table_size
end

def add_data(key, hash_table, table_size)
  result = search(key, hash_table, table_size)
  if result != nil
    puts "この値は既に追加済みです"
    return
  end
  hash_value = get_hash_value(key, table_size)
  target = hash_table[hash_value]

  table_size.times {|index|
    if target[STATUS] == EMPTY || target[STATUS] == DELETED
      hash_table[hash_value] = [key, OCCUPIED]
      p hash_table
      return
    end
    hash_value = get_rehash_value(hash_value, table_size)
    target = hash_table[hash_value]
  }
  puts "値を追加するスペースが存在しません"
end

def delete_data(key, hash_table, table_size)
  result = search(key, hash_table, table_size)
  return if result.nil?
  result[STATUS] = DELETED
  p hash_table
end

def search(key, hash_table, table_size, is_alone = false)
  hash_value = get_hash_value(key, table_size)
  target = hash_table[hash_value]
  table_size.times {|index|
    if target[STATUS] == EMPTY || target[STATUS] == DELETED
      puts "#{key}は見つかりませんでした" if is_alone
      return nil
    end
    if target[STATUS] == OCCUPIED && target[KEY] == key
      puts "#{key}はハッシュテーブルに存在します" if is_alone
      return target
    end
    hash_value = get_rehash_value(hash_value, table_size)
    target = hash_table[hash_value]
  }
  return nil
end

table_size = 5
hash_table = create_hash_table(table_size)
p hash_table
# => [[nil, 1], [nil, 1], [nil, 1], [nil, 1], [nil, 1]]

add_data(13, hash_table, table_size)
# => [[nil, 1], [nil, 1], [nil, 1], [13, 0], [nil, 1]]
add_data(3, hash_table, table_size)
# => [[nil, 1], [nil, 1], [nil, 1], [13, 0], [3, 0]]
add_data(4, hash_table, table_size)
# => [[4, 0], [nil, 1], [nil, 1], [13, 0], [3, 0]]
add_data(9, hash_table, table_size)
# => [[4, 0], [9, 0], [nil, 1], [13, 0], [3, 0]]
add_data(12, hash_table, table_size)
# => [[4, 0], [9, 0], [12, 0], [13, 0], [3, 0]]
add_data(12, hash_table, table_size)
# => この値は既に追加済みです
add_data(11, hash_table, table_size)
# => 値を追加するスペースが存在しません
search(4, hash_table, table_size, ALONE)
# => 4はハッシュテーブルに存在します
delete_data(12, hash_table, table_size)
# => [4, 0], [9, 0], [12, 2], [13, 0], [3, 0]]
search(12, hash_table, table_size, ALONE)
# => 12は見つかりませんでした

参考文献、参考リンク