Wikibooks

ハッシュテーブル

ソフトウェア工学における「ハッシュテーブル (Hash Table)」は、データを高速に検索、挿入、削除するためのデータ構造の一つです。ハッシュテーブルは、ハッシュ関数を使用してキーと値を関連付け、キーを介して値にアクセスします。ハッシュ関数は、キーから一意のハッシュ値を計算するために使用されます。

ハッシュテーブルの主な特徴は以下の通りです：

  1. 高速な検索、挿入、削除: ハッシュ関数によって計算されたハッシュ値を使用するため、データの取得や変更が非常に高速に行えます。
  2. キーと値のペア: ハッシュテーブルは、キーと値をペアとして格納します。このため、特定のキーを使用して対応する値に効率的にアクセスできます。
  3. ハッシュ関数による一意性: ハッシュ関数は一意のハッシュ値を生成するように設計されています。ただし、異なるキーが同じハッシュ値を生成する「ハッシュ衝突」が発生する可能性があります。このような衝突を解決するために、通常は衝突解決策が採用されます。
  4. メモリ効率の向上: ハッシュテーブルは、キーと値のペアを格納するための効率的なメモリ構造です。大量のデータを効率的に管理するために使用されます。

ハッシュテーブルは、データベース、キャッシュ、アルゴリズムの実装など、さまざまな領域で広く使用されています。

ハッシュテーブルの種類

編集

ハッシュテーブルには、いくつかの異なる種類があります。主な種類には以下のものがあります：

  1. オープンアドレス法 (Open Addressing):
    オープンアドレス法では、衝突が発生した場合、別の空きスロットを探してキーを格納します。線形探査、二次探査、二重ハッシュ法などの手法があります。
  2. チェイン法 (Separate Chaining):
    チェイン法では、ハッシュテーブルの各スロットに、複数のキーと値のペアを格納するリストや連結リストなどのデータ構造を使用します。衝突が発生した場合、新しいペアをリストに追加します。
  3. パフォレーテッドハッシュテーブル (Perfected Hash Table):
    パフォレーテッドハッシュテーブルは、特定のデータセットに最適化されたハッシュテーブルの形式です。衝突を最小限に抑え、高速な検索を提供するために、ハッシュ関数が事前に計算されています。
  4. 完全ハッシュ関数 (Perfect Hash Function):
    完全ハッシュ関数は、与えられたデータセットに対して衝突が発生しないように設計されたハッシュ関数です。これにより、ハッシュテーブルの性能を向上させることができます。
  5. 動的ハッシュテーブル (Dynamic Hash Table):
    動的ハッシュテーブルは、データの挿入や削除に応じて自動的にサイズを変更することができるハッシュテーブルです。これにより、データセットのサイズが変化する場合でも効率的なデータ管理が可能となります。

これらの種類のハッシュテーブルは、それぞれの利点や用途に応じて選択されます。

オープンアドレス法

編集

オープンアドレス法 (Open Addressing) は、ハッシュテーブル内の衝突解決手法の一つです。衝突が発生した場合、新しい要素を格納するために別の空きスロットを探します。

以下に、オープンアドレス法の詳細を説明します：

  1. 線形探査 (Linear Probing):
    線形探査は、衝突が発生した場合、直接次のスロットに移動し、そこが空いていれば要素を挿入します。空きスロットが見つかるまで、次々と次のスロットをチェックします。ただし、この方法はクラスタリングの問題を引き起こす可能性があります。
  2. 二次探査 (Quadratic Probing):
    二次探査は、線形探査よりもクラスタリングの問題を軽減するために使用されます。衝突が発生した場合、二次関数を使用して次のスロットを計算し、そこが空いていれば要素を挿入します。二次探査では、ステップの数を増やすことで、より広い範囲を探索することができます。
  3. 二重ハッシュ法 (Double Hashing):
    二重ハッシュ法は、線形探査や二次探査の代わりに、2つ目のハッシュ関数を使用して次のスロットを計算します。衝突が発生した場合、元のハッシュ値に加えて、2つ目のハッシュ関数を使用して次のスロットを計算し、そこが空いていれば要素を挿入します。この方法はクラスタリングを回避する上で効果的です。

オープンアドレス法では、要素が削除されると、そのスロットを空にするだけでなく、他の要素の探索が妨げられないように特別な処理が必要です。通常、削除された要素のスロットを特別な値でマークします（例えば、削除されたことを示す特別なフラグを設定します）。

オープンアドレス法は、チェイン法と比較してメモリ使用効率が高く、キャッシュ効率も良いため、特にキャッシュの利用が重要な場合に好まれることがあります。

Ruby

編集

以下は、Rubyで線形探査（Linear Probing）を使用したオープンアドレス法によるハッシュテーブルの実装例です。

hashtable-openaddress-linear-probing.rb
# 線形探査（Linear Probing）を使用したオープンアドレス法によるハッシュテーブルの実装例
class HashTable
  include Enumerable # Enumerableモジュールを含める

  # ハッシュテーブルを初期化します。
  #
  # size - ハッシュテーブルのサイズ
  def initialize(size)
    @keys = Array.new(size)
    @values = Array.new(size)
    def size = @keys.size
  end

  # キーのハッシュ値を計算します。
  #
  # key - ハッシュ値を計算するキー
  def hash(key) = key.hash % size

  # 指定されたキーに値を設定します。
  #
  # key   - 設定する値のキー
  # value - 設定する値
  def []=(key, value)
    index = hash(key)
    while @keys[index] != nil && @keys[index] != key
      # 線形探査: 次のスロットへ移動
      index += 1
      index %= size
    end
    @keys[index] = key
    @values[index] = value
  end

  # 指定されたキーに関連付けられた値を取得します。
  #
  # key - 取得する値のキー
  #
  # 戻り値: 指定されたキーに関連付けられた値。キーが見つからない場合は nil。
  def [](key)
    index = hash(key)
    while @keys[index] != nil
      return @values[index] if @keys[index] == key
      # 線形探査: 次のスロットへ移動
      index += 1
      index %= size
    end
    return nil
  end

  # ハッシュテーブルを走査し、各Key/Valueをブロックに渡します。
  #
  # @yieldparam value [Object] 各ノードの値
  def each(&block)
    return to_enum unless block

    @keys.each_index() { |index|
      yield(@keys[index], @values[index]) if @keys[index]
    }
    self
  end
end

# テストケース
require 'minitest'

class HashTableTest < Minitest::Test
  def setup
    @hash_table = HashTable.new(5)
  end

  def test_set_get_value
    @hash_table["apple"] = 5
    @hash_table["banana"] = 8
    @hash_table["orange"] = 3
    assert_equal 5, @hash_table["apple"]
    assert_equal 8, @hash_table["banana"]
    assert_equal 3, @hash_table["orange"]
    assert_nil @hash_table["grape"]
  end

  def test_to_a
    @hash_table["apple"] = 5
    @hash_table["banana"] = 8
    @hash_table["orange"] = 3

    assert_equal([["apple", 5], ["banana", 8], ["orange", 3]], @hash_table.to_a.sort)
  end

 end

Minitest.run if $PROGRAM_NAME == __FILE__
"https://ja.wikibooks.org/w/index.php?title=ハッシュテーブル&oldid=243705" より作成