performance - ハッシュ テーブルの連鎖

Question

連鎖のあるハッシュテーブルがある場合:

各キーのリストを順番に維持すると、ハッシュテーブルでの検索、挿入、および削除の実行時間に影響するかどうか疑問に思っていますか?

Answer 1

理論的には: はい。平均的なケースでは、アイテムがチェーン上にあるかどうかを確認するために、チェーンの半分を歩くだけで済みます。

実際には、チェーンは通常非常に短いため、おそらく大きな違いはなく、コードの複雑さが増すと、主に「挿入」の場合に数サイクルかかることになります。

ところで: ほとんどの場合、スロットの数はハッシュ値の「キースペース」よりもかなり小さいです。スペースに余裕がある場合は、チェーン ノードにハッシュ値を格納すると、ホップごとにハッシュ値を再計算する手間が省け、最終的な比較のほとんどを回避できます。もちろん、これは空間<-->時間のトレードオフです。次のように:

struct hashnode **this;
for (this=& table[slot] ; *this; this = &(*this)->link) {
    if ((*this)->hash != the_hash) continue;
    if (compare ((*this)->payload , the_value)) continue;
    break;
 }
 /* at this point "this" points to the pointer that points to the wanted element,
    or to the NULL-pointer where it should be inserted.

    For the sorted-list example, you should instead break out of the loop
    if the compare function returns > 0, and handle that special case here.

 */

Answer 2

仮説として、最初に発生する衝突の数を軽減するために、ハッシュ アルゴリズムとマップ サイズを選択しました。その時点で、任意の位置に非常に小さなリスト (理想的には 1 つまたは 2 つの要素) を配置する必要があるため、チェーン内でソートされた構造を維持するための余分な労力は、そのバケット内の少数のアイテムを反復するだけではありません。

Answer 3

はい、もちろん。ハッシュテーブルに対して通常引用される O(1) は、完全なハッシュを想定しています。つまり、同じでない 2 つの項目が同じハッシュに解決されることはありません。

実際には、そうではありません。（十分に大きなデータセットの場合）常に衝突が発生します。また、衝突は、チェーンを使用しているか、他の衝突解決手法を使用しているかに関係なく、ルックアップ時の作業が増えることを意味します。

そのため、適切に設計/作成され、ハッシュ テーブルのキーとして使用するデータに適切に一致する優れたハッシュ関数を選択することが非常に重要です。実際には、異なるタイプのデータは、異なるハッシュ関数でより適切にハッシュされます。