【アルゴリズムの勉強】Rubyでハッシュ法(オープンアドレス法)を使用してデータの追加・検索・削除を行う
概要
ハッシュ法(オープンアドレス法)を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。
オープンアドレス法とは
衝突が発生した際、テーブル中の空いている別の番地を探す方式を開番地法と呼ぶ。その方法としてハッシュ関数とは別の関数を用いて次の候補となる番地を求める。別の番地を探す関数は繰り返し適用することによってテーブル内の全ての番地を走査できるように選ぶ。
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は見つかりませんでした