Java ハッシュマップは本当に O(1) ですか?

https://stackoverflow.com/questions/1055243

20-08-2019
|

質問

SO re Java ハッシュマップとそのハッシュマップに関する興味深い主張をいくつか見てきました。 O(1) 検索時間。誰かこれがそうなる理由を説明できますか？これらのハッシュマップが、私が購入したハッシュアルゴリズムのいずれかと大きく異なる場合を除き、衝突を含むデータセットが常に存在するはずです。

この場合、ルックアップは次のようになります。 O(n) それよりも O(1).

誰かが彼らかどうか説明してもらえますか？は O(1)、もしそうなら、どのようにしてこれを達成しますか?

解決

のHashMapの特定の機能は、たとえば、バランスの取れた木は、その行動が確率論とは違っているということです。これらのケースでは、その通常最も参考になる起こる最悪の場合の事象の確率の面で複雑さについて話をします。ハッシュマップについては、当然のことではマップがあることを起こるかフルに関して衝突した場合です。衝突が推定するのはとても簡単です。

P <サブ>衝突 = N /容量

だから、要素の控えめな数のハッシュ・マップは、少なくとも一つの衝突を経験するかなり可能性があります。ランダウの記号は、私たちはより魅力的な何かを行うことができます。任意の、固定された定数kのためにそれを観察します。

O（N）= O（K×n個）

私たちは、ハッシュマップのパフォーマンスを向上させるために、この機能を使用することができます。私たちは、代わりに、せいぜい2回の衝突の可能性を考えることができます。

P <サブ>衝突X 2 =（N /容量）²

これははるかに低いです。 1回の余分の衝突を処理するコストはビッグO性能とは無関係であるので、我々は実際にアルゴリズムを変更することなく、パフォーマンスを改善する方法を見つけました！私たちは、これをgeneralzieすることができます。

P <サブ>衝突X K =（N /容量）^K

そして今、我々は、衝突のいくつかの任意の数を無視して、私たちが占めているよりも多くの衝突の無視できるほど小さな可能性で終わることができます。あなたは、すべてのアルゴリズムの実際の実装を変更することなく、正しいKを選択することにより、任意に小さなレベルに確率を得ることができます。

私たちは、ハッシュマップはO（1）アクセス権を持っていると言って、このことについて話をを高い確率でののの

他のヒント

あなたは平均的なケース（予想される）ランタイムと最悪の場合の動作をミックスするように見えます。前者は、実際に（すなわち、完全なハッシュを使用していない）、一般的にハッシュテーブルのO（N）であるが、これは実際にはめったに関連している。

半分まともなハッシュと結合された任意の信頼できるハッシュテーブルの実装は、分散の非常に狭いマージン内、予想場合には（実際には、2）非常に小さな因子とO（1）の検索性能を有します。

Javaでは、HashMapのは、バケツを見つけるためにハッシュコードを使用することによって動作します。各バケットには、そのバケットに存在するアイテムのリストです。項目は、比較のために等号を使用して、走査されます。アイテムを追加するときに特定の負荷割合に達すると、ハッシュマップのサイズが変更されます。

だから、時にはそれがいくつかの項目と比較する必要がありますが、一般的にはO（N）よりもO（1）に非常に近いです。実用的な目的のために、それはあなたが知っておく必要があるのすべてです。

（1）Oする各ルックアップは、単一のアイテムを調べることを意味するものではないことに注意してください - それは、アイテムの平均数が一定w.r.t.ままでチェックすることを意味コンテナ内のアイテムの数。それは100品目とコンテナ内のアイテムを見つけるために、平均4つの比較にかかるのであれば、それはまた、10000の項目とコンテナ内のアイテムを見つけるために、4つの比較の平均を取るべきである、との項目の任意の他の数（のために常にあります特にハッシュテーブルはリハッシュ、及びアイテムの非常に小さい数があるときれる点）の周りに分散のビット

衝突がO（1）動作を有するから容器を妨げないので、限りバケット当たりのキーの平均数は、結合した固定内に留まるように

私は、これは古い質問ですけど、それへの新しい答えは実際にあります。

あなたは要素の数は任意に大きくなるにつれて、最終的にはあなたが一定の時間内に検索することができません（とO-表記は用語で定義されているため、ハッシュ・マップが、厳密に言えば、本当にO(1)ではないことですね任意の大きさを得ることができます数字の）。

しかし、リアルタイムの複雑さがO(n)ということにはならない - バケットは線形リストとして実装されなければならないことを言って何のルールはありませんので。

彼らは実際の時間TreeMapsを行う閾値を超えたら、

は、実際には、Java（登録商標）8がO(log n)としてバケットを実装します。

のバケットの数は、（それを呼び出すB）次いで、ルックアップが実際にはO（n）であり、（通常の場合）一定に保たれている場合。
nが大きくなるように、各バケット平均N / Bの要素数。衝突解決は、通常の方法のいずれか（例えば、リンクリスト）で行われている場合、検索はO（N / B）= O（N）。

O表記はnが大きいと大きくなるときに何が起こるかについてです。特定のアルゴリズムに適用した場合には、誤解を招くことができ、ハッシュテーブルは点における場合です。我々は、我々が対処するために期待しているどのように多くの要素に基づいてバケット数を選択します。 nがbとほぼ同じサイズである場合、ルックアップはほぼ一定時間であるが、我々はO、それを呼び出すことはできません（1）Oは、nー→∞のような限界の観点から定義されているからである。

O(1+n/k)はバケットの数である

k。

実装セットは、次にk = n/alpha場合O(1+alpha) = O(1)が一定であるので、

はalphaある。

ハッシュテーブルルックアップが O(1) であるという標準的な説明は、厳密な最悪の場合のパフォーマンスではなく、平均的な場合の予想時間を指していることが判明しました。チェーンとの衝突を解決するハッシュテーブル (Java のハッシュマップなど) の場合、これは技術的には O(1+α) です。良いハッシュ関数, ここで、α はテーブルの負荷率です。保存するオブジェクトの数がテーブルサイズよりも大きい定数倍以下である限り、依然として一定です。

厳密に言えば、O( を必要とする入力を構築することが可能であることも説明されています。n) 決定論的ハッシュ関数の検索。しかし、最悪の場合を考えるのも興味深いです 期待される これは平均の検索時間とは異なります。連鎖を使用すると、これは O(1 + 最長連鎖の長さ) になります。たとえば、Θ(log n /ログログ n) α=1の場合。

一定時間で予想される最悪の場合のルックアップを実現する理論的な方法に興味がある場合は、以下を読むことができます。動的完全ハッシュこれにより、別のハッシュテーブルとの衝突が再帰的に解決されます。

これはあなたのハッシュ関数は非常に良好である場合にのみ、O（1）です。 Javaのハッシュテーブルの実装が悪いハッシュ関数を防ぐことはできません。

あなたはそれが検索時間程度ですので、質問に関連していないアイテムを追加するか、しない場合は、テーブルを成長させる必要があるかどうか。

HashMapの内部要素は、リンクされたリスト（ノード）の配列として格納され、アレイ内の各リンクされたリストは、1つ以上のキーの一意のハッシュ値のバケットを表す。
ハッシュマップのエントリを追加するとき、キーのハッシュコードは、アレイ内のバケットの位置を決定するために使用される、ようなもの：

location = (arraylength - 1) & keyhashcode

ここで＆はビット単位のAND演算子を表します。

例：100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

は、get操作中には、キーのバケットの位置を決定するのと同じ方法を使用しています。各キーは、各キーの一意のバケツにユニークなハッシュコードと結果を持っている最良のケースでは、この場合には、getメソッドはバケットの位置を決定するために時間を費やして、一定のO（1）の値を取得します。

最悪のケースの下で、すべてのキーが同じハッシュコードを持ち、同じバケットに記憶された

、これはO（N）につながる全体のリストを横断することになる。

のJava 8の場合には、リンクリストバケットは（ログn）サイズが8つ以上に大きくなった場合、これはOの最悪の場合の検索効率を低下させるのTreeMapに置き換えられます。

これは、基本的には、アルゴリズム自体は実際に変更されないように、ほとんどのプログラミング言語の中で最もハッシュテーブルの実装のために行きます。

テーブルに存在する衝突がない場合は、

、あなただけの単一のルックアップを行う必要があり、そのため、実行時間はO（1）です。現在の衝突がある場合は、O（n）の方のパフォーマンスが駆動し、複数のルックアップを行う必要があります。

それはあなたが衝突を避けるために選択したアルゴリズムに依存します。あなたの実装はその後、別のチェーンを使用している場合は、すべてのデータ要素が同じ値（例えばハッシュ関数のお粗末な選択）にハッシュされた場合、最悪のシナリオが発生します。その場合に、データの検索は、リンクされたリスト、すなわちO（N）で線形検索と変わりません。しかし、その出来事の確率は無視できる程度であり、ルックアップ最高の平均場合は一定のまま、すなわちO（1）。

（あなたのプロファイラがそうでなければ、あなたに伝えていない限り。）

学者はさておき、実用的な観点から、ハッシュマップは取るに足らないパフォーマンスへの影響を持つものとして受け入れられるべきである。

も異なるのみハッシュコードは、すべてのハッシュコードの常に異なるバケットている理論的な場合には、O（1）が存在します。そうでなければ、それはハッシュマップの増分で、すなわち一定のオーダーである、検索のその順序は一定のままでます。

もちろん、ハッシュマップの性能は、指定されたオブジェクトのハッシュコード（）関数の品質に基づいて決まります。関数は、衝突の可能性は非常に低くなるように実装されている場合しかし、それは非常に良好なパフォーマンス（これは厳密にはの中のO（1）ではないすべてのの可能ケースを持っていますが、それは、ほとんどのの例）。

例えばOracleのJREのデフォルトの実装では、乱数を使用することである（それが変化しないようにオブジェクト・インスタンスに格納されている - それはまた、バイアスされたロックを無効にし、それが他の議論'S）のでチャンス衝突の非常に低いです。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow