データ構造におけるロビンフードハッシュ
このセクションでは、ロビンフッドハッシュスキームとは何かを説明します。このハッシュは、オープンアドレス法の手法の1つです。これは、より公平な衝突解決戦略を使用して、要素の検索時間を均等化しようとします。挿入しようとしているときに、要素xを位置xiに挿入したいが、すでに要素yがy jに配置されている場合 =x i 、次に2つの要素のうち若い方が先に進む必要があります。したがって、i≤jの場合、位置x i + 1にxを挿入しようとします。 、x i + 2 等々。それ以外の場合は、xを位置x iに格納します 、y j + 1の位置にyを挿入してみます 、y j + 2 など。
Devroyeらによると。ロビンフッド挿入アルゴリズムを使用して、サイズが𝑚=Α𝑛である最初は空のテーブルでn回の挿入を実行した後、最悪の場合の検索時間の期待値は-
であることを示します。$$ E [W] =\ Theta（log \：log \：n）$$
-
データ構造のRツリー
ここにR-Treesデータ構造が表示されます。 Rツリーは、特別なデータインデックスを効率的に格納するために使用されます。この構造は、特別なデータクエリとストレージを保持するのに非常に役立ちます。このRツリーには実際のアプリケーションがいくつかあります。これらは以下のようなものです- 多次元情報の索引付け ゲームデータの処理 地理空間座標を保持する 仮想マップの実装 Rツリーの一例は以下のようなものです。 対応するRツリーは次のようになります- Rツリーのプロパティ Rツリーは、単一のルート、内部、およびリーフノードで構成されています ル
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ