私が知っているハッシュ構造 - HashTable、HashSet & HashMap。
それらはすべてバケット構造を使用していますか?つまり、2 つのハッシュコードがまったく同じである場合 、一方の要素が他方を上書きせず、そのハッシュコードに関連付けられた同じバケットに配置されますか?
2722 次
7 に答える
8
Java ライブラリの Sun の現在の実装、IdentityHashMapおよび使用中の内部実装でThreadLocalは、プローブ構造が使用されます。
Java でハッシュ テーブルをプローブする際の一般的な問題は、hashCode比較的equalsコストがかかることです。したがって、ハッシュ値をキャッシュする必要があります。参照とプリミティブを混在させた配列を持つことはできないため、比較的複雑なことを行う必要があります。一方、 を使用==して一致をチェックしている場合は、パフォーマンスの問題なしに多くの参照をチェックできます。
IIRC では、Azul には高速な同時 2 次プロービング ハッシュ マップがありました。
于 2009-11-24T17:53:35.203 に答える
6
ハッシュの衝突を処理するために、各バケットでリンクされたリストが使用されます。JavaHashSetは実際には下位の によって実装されてHashMapいるため(すべてのキーがすべての で同じシングルトン値にマップされているHashSet)、同じバケット構造を使用していることに注意してください。
要素が追加されると、最後に追加される前に、リンクされたリスト内のすべての項目に対して( を介して)その等価性がチェックされます。.equalsしたがって、リンクされたリストが大きくなると、これは高価なチェックになる可能性があるため、ハッシュの衝突があることは特に悪いことです。
于 2009-11-24T17:48:40.910 に答える
5
Java ハッシュ構造はすべて、ハッシュを実行するときに衝突に対処するためにチェーンの形式を使用していると思います。これにより、同じハッシュを持つアイテムがリストに配置されます。
Javaがハッシュベースのデータ構造にオープンアドレッシングを使用しているとは思いません（オープンアドレッシングは、テーブルにオープンスリットが見つかるまで、再試行シーケンスに基づいてハッシュを再計算します）
于 2009-11-24T17:44:32.337 に答える
4
いいえ --オープン アドレス指定は、ハッシュ テーブルを表す代替方法です。オブジェクトは、リンクされたリストに存在する代わりに、テーブルに直接格納されます。特定のインデックスに格納できるオブジェクトは 1 つだけなので、衝突の解決はより複雑になります。
同じインデックスに別のオブジェクトが既に存在するオブジェクトを追加する場合、プローブ シーケンスを使用して、新しいオブジェクトを格納する新しいインデックスを決定します。オブジェクトを削除する場合は、「ここにオブジェクトがあった」というマーカーを残す必要があるため、オブジェクトの削除もより複雑です。詳細については、ウィキペディアを参照してください。
オープン アドレッシングは、保存されるオブジェクトが小さく、めったに削除されない場合に適しています。リンクされたリストをたどる余分なレベルの間接化を行う必要がないため、オープン アドレス指定によりキャッシュ パフォーマンスが向上しました。
あなたが言及したクラス -- HashTable、HashSet、およびHashMapはオープン アドレッシングを使用しませんが、オープン アドレッシングを実装し、それらのクラスと同じ API を提供する新しいクラスを簡単に作成できます。
于 2009-11-24T17:54:25.937 に答える
2
API は動作を定義し、ハッシュ衝突の管理方法の内部は API の保証に影響しません...不適切なハッシュ値計算のパフォーマンスへの影響は別の話です。すべてを 42 にハッシュして、それがどのように動作するかを見てみましょう。
于 2009-11-24T17:52:11.493 に答える
0
マップとセットは、HashSetまたはHashMapの動作を決定するインターフェースです。HashSetはセットであるため、セットのように動作します（つまり、複製は許可されません）。HashMapはマップのように機能します。同様のハッシュコードでキーを上書きすることはありませんが、同じ正確なキーが再度使用されると、キーが上書きされます。これは、マップを内部的にサポートしているデータ構造に関係なく同じです。詳細については、SetsとHashMapsのjavadocを参照してください。
これらの構造の1つの特定の実装について何か質問するつもりでしたか？
于 2009-11-24T18:20:25.290 に答える
-3
HashSet を除きます。セットは定義上、一意の要素です。
これは間違いでした。以下のコメントをご覧ください。
于 2009-11-24T17:41:03.637 に答える