6

Javaコレクションフレームワークで知っているように、すべてのクラスはMap衝突解決にチェーンをIdentityHashMap使用しますが、同じために線形プローブを使用します。

Java ドキュメントを見ると、次のように記載されています。

多くの JRE 実装と操作の組み合わせでは、このクラスは HashMap (線形プローブではなくチェーンを使用) よりも優れたパフォーマンスを発揮します。

私の質問は次のとおりです。

  • 線形プローブのパフォーマンスが優れている場合、実装者がすべての実装ではなく、線形プローブのみを使用した理由IdentityHashMapMap

  • 線形プロービングとチェーンでパフォーマンスが向上する理由。

タンク。

4

3 に答える 3

9

ID ハッシュ マップを作成する場合、互いに等しいが同じオブジェクトではない 2 つのインスタンスが見つかる可能性はありません。またSystem.identityHashCode、 の設計者が事前に知っている衝突の可能性があり、IdentityHashMap非常に小さいことが知られている も使用します。これらの「実験室」の条件下では、線形プロービングがパフォーマンスの点でより良い選択であるように思われます。

クラス ライブラリの設計者が "通常の" ハッシュ マップで線形プローブではなく連鎖を使用した理由は、ハッシュ関数が最適ではない場合でも適切なパフォーマンスを維持したいという願望があるためだと思います。

于 2013-06-19T15:57:45.607 に答える
5

これはいくつかの光を当てるかもしれません（Oracle Webサイトから取得）：

実装上の注意: これは、Sedgewick と Knuth によるテキストなどで説明されている単純な線形プローブ ハッシュ テーブルです。配列はキーと値を交互に保持します。(これは、個別の配列を使用するよりも、大きなテーブルの局所性が優れています。)多くの JRE 実装と操作の組み合わせでは、このクラスは HashMap (線形プローブではなく連鎖を使用) よりも優れたパフォーマンスをもたらします。

ほとんどの実装ではチェーンの方が適しているかもしれませんが、すべての実装でそうであるとは限りません。

編集これも見つかりました。おそらくそれほど重要ではありません（ここから取得）：

プローブを使用する動機は、リンクされたリストをたどるよりもいくらか高速であるということですが、これは、値への参照を配列に直接配置できる場合にのみ当てはまります。他のすべてのハッシュベースのコレクションでは、値だけでなくハッシュ コードも格納されるため、これは実用的ではありません。これは効率上の理由によるものです。get 操作では、正しいキーが見つかったかどうかを確認する必要があります。また、等価性はコストのかかる操作であるため、正しいハッシュ コードがあるかどうかを最初に確認するのが理にかなっています。もちろん、この推論はIdentityHashMap、オブジェクトの等価性ではなくオブジェクトの同一性をチェックする には当てはまりません。

背景/明確化として、 は、2 つのキーが物理的に同じオブジェクトである場合にのみ等しいと見なされるというIdentityHashMap点で、通常HashMapのキーとは異なります。キーの比較には、等しいではなく、同一性が使用されます。

EDIT：答えを見つけるのに役立つ議論（以下のコメントから）：

しようとしている：

ただし、これは、値への参照を配列に直接配置できる場合にのみ当てはまります。他のすべてのハッシュベースのコレクションでは、値だけでなくハッシュ コードも格納されるため、これは実用的ではありません。リンクされたリストのトラバーサルが直接配列よりもコストがかかる場合、hashMap がキー、値、およびハッシュコードを配列に入れ、線形プローブを使用できないのはなぜでしょうか?

wlyles:

スペースの使用が原因である可能性があります。これは、各スロットでより多くのデータを占有します。また、トラバーサルは線形プローブの場合はコストがかからないことを指摘しておく必要がありますが、線形プローブは多くのキーが同じハッシュ値を持つクラスタリングに悩まされることが多いため、全体の検索操作はよりコストがかかる (そして予測しにくい) 可能性があります。@delnan が別のコメントで述べたように、たとえば、キー 1..20 が連続するスロットにハッシュされ、21 番目が 1 番目と同じスロットにハッシュされる場合、それを検索します (または、 1 番目のスロット) には 20 個のプローブが必要です。リストを使用すると、必要なプローブが少なくなります。さらに明確にするために: IdentityHashMap がキー値を比較する方法により、衝突の可能性は非常に低くなります。したがって、線形プロービングの主な弱点である凝集につながる衝突が大幅に回避されます。

さらに明確にするために: IdentityHashMap がキー値を比較する方法により、衝突の可能性は非常に低くなります。したがって、線形プローブの主な弱点である凝集につながる衝突が大幅に回避され、この実装でより望ましいものになります。

于 2013-06-19T15:57:12.963 に答える
-2

ドキュメントから：

実装上の注意: これは、Sedgewick と Knuth によるテキストなどで説明されている単純な線形プローブ ハッシュ テーブルです。配列はキーと値を交互に保持します。(これは、個別の配列を使用するよりも、大きなテーブルの局所性が優れています。)多くの JRE 実装と操作の組み合わせでは、このクラスは HashMap (線形プローブではなく連鎖を使用) よりも優れたパフォーマンスをもたらします。

理由は、このクラスが HashMap よりも優れたパフォーマンスを発揮するためです。

于 2013-06-19T15:56:40.880 に答える