ハッシュテーブルには、いくつかの異なる種類があります。主な種類には以下のものがあります：
オープンアドレス法では、衝突が発生した場合、別の空きスロットを探してキーを格納します。線形探査、二次探査、二重ハッシュ法などの手法があります。
チェイン法では、ハッシュテーブルの各スロットに、複数のキーと値のペアを格納するリストや連結リストなどのデータ構造を使用します。衝突が発生した場合、新しいペアをリストに追加します。
パフォレーテッドハッシュテーブルは、特定のデータセットに最適化されたハッシュテーブルの形式です。衝突を最小限に抑え、高速な検索を提供するために、ハッシュ関数が事前に計算されています。
完全ハッシュ関数は、与えられたデータセットに対して衝突が発生しないように設計されたハッシュ関数です。これにより、ハッシュテーブルの性能を向上させることができます。
動的ハッシュテーブルは、データの挿入や削除に応じて自動的にサイズを変更することができるハッシュテーブルです。これにより、データセットのサイズが変化する場合でも効率的なデータ管理が可能となります。
これらの種類のハッシュテーブルは、それぞれの利点や用途に応じて選択されます。
オープンアドレス法 (Open Addressing) は、ハッシュテーブル内の衝突解決手法の一つです。衝突が発生した場合、新しい要素を格納するために別の空きスロットを探します。
以下に、オープンアドレス法の詳細を説明します：
線形探査は、衝突が発生した場合、直接次のスロットに移動し、そこが空いていれば要素を挿入します。空きスロットが見つかるまで、次々と次のスロットをチェックします。ただし、この方法はクラスタリングの問題を引き起こす可能性があります。
二次探査は、線形探査よりもクラスタリングの問題を軽減するために使用されます。衝突が発生した場合、二次関数を使用して次のスロットを計算し、そこが空いていれば要素を挿入します。二次探査では、ステップの数を増やすことで、より広い範囲を探索することができます。
二重ハッシュ法は、線形探査や二次探査の代わりに、2つ目のハッシュ関数を使用して次のスロットを計算します。衝突が発生した場合、元のハッシュ値に加えて、2つ目のハッシュ関数を使用して次のスロットを計算し、そこが空いていれば要素を挿入します。この方法はクラスタリングを回避する上で効果的です。
オープンアドレス法では、要素が削除されると、そのスロットを空にするだけでなく、他の要素の探索が妨げられないように特別な処理が必要です。通常、削除された要素のスロットを特別な値でマークします（例えば、削除されたことを示す特別なフラグを設定します）。
オープンアドレス法は、チェイン法と比較してメモリ使用効率が高く、キャッシュ効率も良いため、特にキャッシュの利用が重要な場合に好まれることがあります。
以下は、Rubyで線形探査（Linear Probing）を使用したオープンアドレス法によるハッシュテーブルの実装例です。
[https://paiza.io/projects/hh9XqBhsrevkGSyic9y9nw?language=ruby hashtable-openaddress-linear-probing.rb]:
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(█)
    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__