3

オブジェクトごとに同じ値を返すのは非効率的であることを理解していますが、個別のインスタンスに対して個別の値を返すのが最も効率的なアプローチですか？

各オブジェクトが異なるhashCode値を取得する場合、これはそれらをArrayListに格納するのと同じではありませんか？

4

5 に答える 5

4

hashCodeと一致してequalsいる必要があります。これが最優先事項です。2つのオブジェクトが等しくない場合、これが望ましいでしょう。オブジェクトの状態が32ビットを超える場合、完全に拡散されたハッシュコードを提供することは理論的に不可能であることに注意してください。

于 2012-07-20T12:02:02.403 に答える
3

いいえ、実際にはそうではありません。

オブジェクトがHashMapに格納されると仮定すると（またはSet ...は関係ありません。ここでは、簡単にするためにHashMapを使用します）、hashCodeメソッドがオブジェクトを均等に分散する方法で結果を返すようにします。できるだけ。

ハッシュコードは、等しくないオブジェクトに対して一意である必要がありますが、これが常に真であるとは限りません。一方、a.equals(b)trueの場合、a.hashCode() == b.hashCode()。これは、オブジェクトコントラクトと呼ばれます。

これに加えて、パフォーマンスの問題もあります。2つの異なるオブジェクトが同じhashCodeを持つたびに、それらはHashMapの同じ位置にマップされます（別名、それらは衝突します）。これは、HashMap実装がこの衝突を処理する必要があることを意味します。これは、単にエントリを格納および取得するよりもはるかに複雑です。

値がマップ全体に均等に分散されるという事実に依存するアルゴリズムもたくさんあり、衝突の数が増えるとパフォーマンスが急速に低下します（一部のアルゴリズムは完全なハッシュ関数を想定しているため、衝突は発生せず、2つの違いはありません値はマップ上の同じ位置にマップされます）。

この良い例は、確率的アルゴリズムやブルームフィルターなどのデータ構造です（最近流行しているように見える例を使用するため）。

于 2012-07-20T12:05:38.693 に答える
1

衝突を避けるために、hashCode（）をできるだけ変化させたいと思います。衝突がない場合、各キーまたは要素はそれ自体で基になる配列に格納されます。（ArrayListに少し似ています）

問題は、hashCode（）が異なっていても、衝突が発生する可能性があることです。これは、考えられるすべてのhashCodeのバケットがなく、この値をより小さな範囲に減らす必要があるために発生します。たとえば、16個のバケットがあり、範囲は0〜15です。これを行う方法は複雑ですが、すべてのhashCodeが異なっていても、衝突が発生する可能性があることがわかります（可能性は低いですが）。

これは、サービス拒否攻撃の懸念事項です。通常、文字列の衝突率は低くなりますが、同じハッシュコードを持つ文字列を意図的に作成することもできます。この質問は、hashCodeが0の文字列のリストを提供します。String のhashCode（）が0をキャッシュしないのはなぜですか？

于 2012-07-20T12:14:50.610 に答える
0

hashCode（）メソッドは、オブジェクトをArrayListに配置するのには適していません。毎回同じオブジェクトに対して同じ値を返しますが、2つのオブジェクトが同じハッシュコードを持っている可能性があります。

したがって、hashCodeメソッドは、たとえばHashMapにアイテムを格納するときに、キーObjectで使用されます。

于 2012-07-20T12:04:27.147 に答える
0

HashMapクラスの主要なデータ構造は次のとおりです。

Entry[] table;

Entryクラス（Map.Entryを実装する静的パッケージ保護クラス）は、実際にはリンクリストスタイルの構造であることに注意することが重要です。

要素を配置しようとすると、最初にキーのハッシュコードが計算され、次にバケット番号に変換されます。「バケット」は、上記の配列へのインデックスです。

バケットが見つかると、そのバケット内で正確なキーの線形検索が実行されます（信じられない場合は、HashMapコードを参照してください）。見つかった場合、値が置き換えられます。そうでない場合は、キーと値のペアがそのバケットの最後に追加されます。

このため、hashcode（）値は一意である必要はありませんが、一意で均等に分散されているほど、バケット間で値が均等に分散される可能性が高くなります。hashcode（）メソッドがすべてのインスタンスに対して同じ値を返す場合、それらはすべて同じバケットに入れられるため、get（）メソッドは1つの長い線形検索になり、O（N）が生成されます。

値が分散しているほど、バケットは小さくなり、したがって線形探索コンポーネントは小さくなります。一意の値は、一定時間のルックアップO（1）を生成します。

于 2012-07-20T13:13:56.073 に答える