SO re Java ハッシュマップとそのO(1)検索時間に関する興味深い主張を見てきました。誰かがなぜそうなのか説明できますか? これらのハッシュマップが、私が購入したハッシュ アルゴリズムのいずれかと大きく異なる場合を除き、衝突を含むデータセットが常に存在する必要があります。
その場合、ルックアップはO(n)ではなくO(1).
誰かがO(1) であるかどうかを説明できますか?もしそうなら、どうやってこれを達成したのでしょうか?
質問する
140577 次
15 に答える
140
HashMap の特定の機能は、たとえばバランスの取れたツリーとは異なり、その動作が確率的であることです。このような場合、通常、最悪の事態が発生する確率という観点から複雑さについて話すことが最も役に立ちます。ハッシュ マップの場合は、もちろん、マップがたまたまどのくらいいっぱいになるかに関して衝突が発生する場合です。衝突はかなり簡単に見積もることができます。
p衝突= n / 容量
そのため、要素の数が少ないハッシュ マップでも、少なくとも 1 回は衝突が発生する可能性があります。Big O 記法を使用すると、より説得力のあることができます。任意の固定定数 k について観察します。
O(n) = O(k * n)
この機能を使用して、ハッシュ マップのパフォーマンスを向上させることができます。代わりに、最大 2 回の衝突の確率について考えることができます。
p衝突 x 2 = (n / 容量) 2
これははるかに低いです。1 つの余分な衝突を処理するコストは Big O のパフォーマンスとは無関係であるため、アルゴリズムを実際に変更せずにパフォーマンスを改善する方法を見つけました。これを一般化できます
p衝突 xk = (n / 容量) k
そして今、任意の数の衝突を無視して、説明しているよりも多くの衝突が発生する可能性がほとんどないことになります。アルゴリズムの実際の実装を変更することなく、正しい k を選択することで、任意の小さなレベルまで確率を得ることができます。
これについては、ハッシュマップには高い確率でO(1) アクセスがあると言って話します
于 2009-06-28T17:33:11.813 に答える
40
最悪の場合の動作と平均的な場合の（予想される）実行時間を混同しているようです。前者は確かに一般的なハッシュテーブルではO（n）です（つまり、完全なハッシュを使用していません）が、これが実際に関連することはめったにありません。
信頼できるハッシュテーブルの実装は、半分まともなハッシュと組み合わされて、非常に狭い分散マージン内で、予想されるケースでは非常に小さい係数（実際には2）でO（1）の取得パフォーマンスを示します。
于 2009-06-28T17:09:21.127 に答える
38
Javaでは、HashMapはどのように機能しますか?
- を使用
hashCodeして、対応するバケットを特定します [バケット コンテナ モデル内]。 - 各バケットは、そのバケットに存在するアイテムのリスト (または Java 8 以降のツリー) です。
- 項目は 1 つずつスキャンされ
equals、比較に使用されます。 - さらに項目を追加すると、特定の負荷率に達すると HashMap のサイズが変更されます。
したがって、いくつかの項目と比較する必要がある場合もありますが、一般的にはO(n)よりもO (1)にはるかに近いです。
実用上、知っておく必要があるのはこれだけです。
于 2009-06-28T16:54:49.367 に答える
32
o（1）は、各ルックアップが単一のアイテムのみを検査することを意味するのではないことに注意してください。つまり、チェックされるアイテムの平均数は、コンテナー内のアイテムの数に対して一定のままです。したがって、100個のアイテムを含むコンテナ内のアイテムを見つけるのに平均4回の比較が必要な場合、10000個のアイテムを含むコンテナ内のアイテムを見つけるには、平均4回の比較も必要です。特にハッシュテーブルが再ハッシュされるポイントの周り、およびアイテムの数が非常に少ない場合は、多少の差異があります。
したがって、バケットごとのキーの平均数が一定の範囲内にある限り、衝突によってコンテナーがo（1）操作を実行できなくなることはありません。
于 2009-06-28T17:04:59.680 に答える
4
バケットの数 (b と呼びます) が一定に保たれている場合 (通常の場合)、ルックアップは実際には O(n) になります。
n が大きくなると、各バケット内の要素数の平均は n/b になります。競合の解決が通常の方法のいずれか (たとえば、リンクされたリスト) で行われる場合、ルックアップは O(n/b) = O(n) です。
O表記は、nがどんどん大きくなったときに何が起こるかについてです。特定のアルゴリズムに適用すると誤解を招く可能性があり、ハッシュ テーブルはその好例です。処理する予定の要素の数に基づいて、バケットの数を選択します。n が b とほぼ同じサイズの場合、ルックアップはほぼ一定時間ですが、O は n → ∞ という極限で定義されているため、O(1) とは言えません。
于 2009-06-28T18:05:53.950 に答える
2
HashMap 内の要素は、連結リスト (ノード) の配列として格納されます。配列内の各連結リストは、1 つ以上のキーの一意のハッシュ値のバケットを表します。
HashMap にエントリを追加する際、キーのハッシュコードを使用して配列内のバケットの場所を特定します。次のようになります。
location = (arraylength - 1) & keyhashcode
ここで & は、ビットごとの AND 演算子を表します。
例えば：100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
取得操作中、同じ方法を使用して、キーのバケットの場所を決定します。最良のケースでは、各キーに一意のハッシュコードがあり、キーごとに一意のバケットになります。この場合、get メソッドはバケットの場所を特定し、定数 O(1) である値を取得するためだけに時間を費やします。
最悪の場合、すべてのキーが同じハッシュコードを持ち、同じバケットに格納されます。これにより、O(n) につながるリスト全体をトラバースすることになります。
Java 8 の場合、サイズが 8 を超えると、Linked List バケットが TreeMap に置き換えられます。これにより、最悪の場合の検索効率が O(log n) に低下します。
于 2016-12-01T16:29:22.593 に答える
2
ハッシュ テーブル ルックアップが O(1) であるという標準的な説明は、厳密な最悪の場合のパフォーマンスではなく、平均的な場合の予想時間を指すことを確立しました。(Java のハッシュマップのように) 連鎖による衝突を解決するハッシュ テーブルの場合、これは技術的には O(1+α) であり、適切なハッシュ関数を使用します。ここで、α はテーブルの負荷係数です。格納しているオブジェクトの数が、テーブル サイズよりも一定の係数を超えない限り、一定です。
また、厳密に言えば、任意の決定論的ハッシュ関数に対してO( n ) ルックアップを必要とする入力を構築できることも説明されています。しかし、平均検索時間とは異なる、最悪の場合の予想時間を考慮することも興味深いことです。連鎖を使用すると、これは O(1 + 最長連鎖の長さ) になります。たとえば、α=1 の場合、 Θ(log n / log log n ) です。
一定時間の最悪の場合のルックアップを実現するための理論的な方法に興味がある場合は、別のハッシュ テーブルとの衝突を再帰的に解決する動的完全ハッシュについて読むことができます。
于 2009-06-28T17:42:55.077 に答える
2
ハッシュ関数が非常に優れている場合にのみ O(1) です。Java ハッシュ テーブルの実装は、不適切なハッシュ関数から保護しません。
アイテムを追加するときにテーブルを拡張する必要があるかどうかは、ルックアップ時間に関するものであるため、質問には関係ありません。
于 2009-06-28T18:23:29.570 に答える
1
衝突を回避するために選択したアルゴリズムによって異なります。実装で個別のチェーンを使用する場合、すべてのデータ要素が同じ値にハッシュされるという最悪のシナリオが発生します（たとえば、ハッシュ関数の選択が不十分）。その場合、データルックアップはリンクリスト、つまりO（n）での線形検索と同じです。ただし、その可能性はごくわずかであり、ルックアップは最良であり、平均的なケースは一定のままです。つまり、O（1）です。
于 2009-06-28T17:15:38.043 に答える
1
アルゴリズム自体は実際には変更されないため、これは基本的に、ほとんどのプログラミング言語のほとんどのハッシュ テーブルの実装に当てはまります。
テーブルに衝突が存在しない場合は、検索を 1 回実行するだけでよいため、実行時間は O(1) です。衝突が存在する場合は、複数のルックアップを行う必要があり、O(n) に向かってパフォーマンスが低下します。
于 2009-06-28T17:03:15.750 に答える
1
理論的な場合にのみ、ハッシュコードが常に異なり、すべてのハッシュコードのバケットも異なる場合、O(1) が存在します。それ以外の場合、順序は一定です。つまり、ハッシュマップの増分では、検索の順序は一定のままです。
于 2015-10-19T11:36:26.437 に答える
0
もちろん、ハッシュマップのパフォーマンスは、指定されたオブジェクトの hashCode() 関数の品質に基づいて異なります。ただし、衝突の可能性が非常に低くなるように関数が実装されている場合、非常に優れたパフォーマンスが得られます (これはすべての可能なケースで厳密に O(1) ではありませんが、ほとんどの場合です)。
たとえば、Oracle JRE のデフォルトの実装では、乱数を使用することになっています (乱数は、変更されないようにオブジェクト インスタンスに格納されますが、バイアス ロックも無効になりますが、それは別の議論です)。したがって、衝突の可能性は次のようになります。とても低い。
于 2009-06-28T16:55:09.757 に答える