データ構造におけるオープンアドレス法によるハッシュ
このセクションでは、オープンアドレス法によるハッシュとは何かを説明します。オープンアドレッシングは、衝突を解決するためのもう1つの手法です。連鎖とは異なり、他のデータ構造に要素を挿入しません。データをハッシュテーブル自体に挿入します。ハッシュテーブルのサイズは、キーの数よりも大きくする必要があります。
オープンアドレッシング技術には、3つの異なる一般的な方法があります。これらのメソッドは-
です-
線形プロービング
-
二次プロービング
-
ダブルハッシュ
この手法では、他のハッシュ手法と同様にハッシュ関数を使用します。場所が空いている場合は、その場所に要素を挿入します。その場所が無料でない場合は、いくつかの方程式を使用して別の無料の要素を見つけます。線形プロービングにはいくつかの線形方程式を使用し、2次プロービングにはいくつかの2次方程式を使用します。
ダブルハッシュでは、衝突が発生したときに、別のハッシュ関数を使用して、その場所に配置します。そのハッシュ関数は二次ハッシュ関数と呼ばれます。衝突がなければ、それは直接使用されません。
-
データ構造の連鎖によるハッシュ
このセクションでは、連鎖によるハッシュとは何かを説明します。連鎖は、衝突解決手法の1つです。衝突を回避することはできませんが、衝突を減らし、同じハッシュ値に対して複数の要素を格納することを試みることはできます。 この手法では、0から6の範囲のハッシュ関数h（x）を想定しています。したがって、7つを超える要素の場合、同じ部屋内に配置されるいくつかの要素が必要です。そのために、それに応じてそれらを保存するためのリストを作成します。毎回、リストの先頭に追加して、O（1）時間で挿入を実行します より良いアイデアを得るために、次の例を見てみましょう。 {15、47、23、34、85、97、65、89
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ