summary:
オープンアドレッシングでは,すべてのキーと値のペアをハッシュテーブル自体に格納するため,外部のデータ構造[例：連結リスト]を使用しない.そのため,適切に管理すればメモリの局所性[キャッシュ効率]が良くなり,チェイニング[Chaining]方式よりも効率的になることがある.
主な探索方法としては,線形探索法[Linear Probing],二次探索法[Quadratic Probing],ダブルハッシング[Double Hashing]などがある.
線形探索法では衝突が発生すると順番に次のスロットを調べるが,クラスタリング[データの偏り]が発生しやすいという欠点がある.
オープンアドレッシングの性能は負荷率[ロードファクター]に大きく依存し,負荷率が高くなるとパフォーマンスが急激に低下する.そのため,一般的にはテーブルが一定の割合[通常70～80％]まで埋まったら,テーブルサイズを拡張するリハッシュが必要となる.
また,オープンアドレッシングでは要素の削除処理に注意が必要である.単純に要素を削除すると探索チェーンが切断されるため,特別な削除済みマーカーを使用するか,他の要素を再配置する必要がある.
Mathematics is the language with which God has written the universe.