ダイナミックパーフェクトハッシュ

定義

動的完全ハッシュは、ハッシュテーブルデータ構造の衝突を解決するためのプログラミング方法として定義されています。

アプリケーション

この方法は、対応するハッシュテーブルよりもメモリを大量に消費しますが、大量の要素セットに対して高速なクエリ、挿入、および削除を実行する必要がある状況に最適です。

実装

ディーツフェルビンガー他動的ディクショナリアルゴリズムを説明します。m個のアイテムのセットがディクショナリに段階的に追加されると、メンバーシップクエリは常に一定の時間を消費するため、最悪の場合はO（1）であり、必要なストレージの合計はO（m）（線形）です。 O（1）予想される償却挿入および削除時間（償却定数時間）動的な場合、キーがハッシュテーブルに挿入され、それぞれのサブテーブルのエントリが占有されていると、衝突が発生し、サブテーブルは、新しい合計エントリ数とランダムに選択されたハッシュ関数に基づいて再構築されます。第2レベルのテーブルの負荷率は低いままであるため、再構築は頻繁ではなく、挿入の償却済み予想コストと削除の償却済み予想コストはO（1）です。

さらに、トップレベルテーブルまたはサブテーブルの最終的なサイズには、動的な場合の事前知識がありません。テーブルの予想されるO（m）スペースを維持するための1つの手法は、十分な数の挿入と削除が行われたときに完全な再構築を促すことです。挿入または削除の総数が最後の構築時の要素の数を超えている限り、完全な再ハッシュを考慮することにより、挿入および削除の償却済み予想コストはO（1）のままです。