68

各要素のキーがあり、配列への要素のインデックスがわからない場合、ハッシュテーブルのパフォーマンスは配列よりも優れています（O（1）対O（n））。

何故ですか？つまり、キーがあり、ハッシュします。ハッシュがあります。アルゴリズムは、このハッシュをすべての要素のハッシュと比較するべきではありませんか？記憶の性質の裏にはいくつかのトリックがあると思いますね。

4

7 に答える 7

99

各要素のキーがあり、配列への要素のインデックスがわからない場合、ハッシュテーブルは配列よりも優れたパフォーマンスを発揮します (O(1) 対 O(n))。

ハッシュ テーブル検索は、平均的なケースで O(1) を実行します。最悪の場合、衝突があり、ハッシュ関数が常に同じスロットを返す場合、ハッシュ テーブル検索は O(n): を実行します。「これは遠い状況だ」と思うかもしれませんが、適切な分析はそれを考慮する必要があります。この場合、配列や連結リスト (O(n)) のように、すべての要素を反復処理する必要があります。

何故ですか？つまり: 私にはキーがあり、それをハッシュします.. ハッシュを持っています.. アルゴリズムはこのハッシュをすべての要素のハッシュと比較すべきではありませんか? メモリ配置の背後にあるトリックがあると思いますね。

あなたはキーを持っています、あなたはそれをハッシュします.. あなたはハッシュを持っています: 要素が存在するハッシュテーブルのインデックス (それが以前に配置されていた場合)。この時点で、O(1) のハッシュ テーブル レコードにアクセスできます。負荷率が小さい場合、そこに複数の要素が表示される可能性はほとんどありません。したがって、最初に表示される要素は、探している要素である必要があります。それ以外の場合、複数の要素がある場合は、その位置にある要素を探している要素と比較する必要があります。この場合、O(1) + O(number_of_elements) になります。

平均的なケースでは、ハッシュ テーブル検索の複雑さは O(1) + O(load_factor) = O(1 + load_factor) です。

最悪の場合、load_factor = n であることを思い出してください。したがって、検索の複雑さは最悪の場合 O(n) になります。

「メモリ処理の背後にあるトリック」の意味がわかりません。いくつかの観点では、ハッシュ テーブル (その構造と連鎖による衝突解決) は「スマート トリック」と見なすことができます。

もちろん、ハッシュテーブルの分析結果は数学で証明できます。

于 2012-08-19T09:17:19.743 に答える
57

配列の場合：値がわかっている場合は、（ソートされていない限り）平均して値の半分を検索してその場所を見つける必要があります。

ハッシュあり：位置は値に基づいて生成されます。したがって、その値を再度指定すると、挿入時に計算したのと同じハッシュを計算できます。複数の値が同じハッシュになる場合があるため、実際には、各「場所」自体が、その場所にハッシュされるすべての値の配列（またはリンクリスト）になります。この場合、（ハッシュが悪い場合を除いて）このはるかに小さい配列のみを検索する必要があります。

于 2012-08-18T18:09:46.830 に答える
28

ハッシュテーブルはもう少し複雑です。ハッシュ％の値に基づいて、要素を異なるバケットに配置します。理想的な状況では、各バケットに保持されるアイテムは非常に少なく、空のバケットは多くありません。

キーがわかったら、ハッシュを計算します。ハッシュに基づいて、検索するバケットがわかります。また、前述のように、各バケット内のアイテムの数は比較的少なくする必要があります。

ハッシュテーブルは、空のバケットに多くのメモリを消費しないようにしながら、バケットを可能な限り小さくするために、内部で多くの魔法をかけています。また、キー->ハッシュ関数の品質に大きく依存します。

ウィキペディアは、ハッシュテーブルの非常に包括的な説明を提供します。

于 2012-08-18T18:05:45.193 に答える
10

ハッシュ テーブルは、ハッシュ内のすべての要素を比較する必要はありません。キーに従ってハッシュコードを計算します。たとえば、キーが 4 の場合、ハッシュコードは - 4*x*y のようになります。これで、ポインターはどの要素を選択するかを正確に認識します。

一方、配列の場合は、配列全体を走査してこの要素を検索する必要があります。

于 2016-04-02T18:35:10.140 に答える
-6

あなたはそこであなた自身の質問に答えたと思います。「アルゴリズムはこのハッシュをすべての要素のハッシュと比較すべきではありません」。これは、検索対象のインデックスの場所がわからない場合に行うことです。各要素を比較して、探している要素を見つけます。

たとえば、文字列の配列内で「Car」というアイテムを探しているとしましょう。すべてのアイテムを確認し、 item.Hash() == "Car".Hash() をチェックして、それが探しているアイテムであることを確認する必要があります。明らかに、常に検索するときにハッシュを使用しませんが、例は有効です。次に、ハッシュテーブルがあります。ハッシュテーブルが行うことは、スパース配列、または上記の人のようにバケットの配列を作成することです。次に、「Car」.Hash() を使用して、「Car」アイテムが実際にスパース配列のどこにあるかを推測します。これは、項目を見つけるために配列全体を検索する必要がないことを意味します。

于 2012-08-18T18:11:57.530 に答える