12

私は、次のタイトルの記事から引用された段落を読んでいました-Javaの理論と実践：それをハッシュする-hashCode（）とequals（）を効果的かつ正確に定義する

等価性の定義 Object クラスには、オブジェクトの同一性について推論するための 2 つのメソッドがあります。 equals() と hashCode() です。一般に、これらのメソッドのいずれかをオーバーライドする場合は、両方をオーバーライドする必要があります。これは、それらの間に維持する必要がある重要な関係があるためです。特に、equals() メソッドに従って 2 つのオブジェクトが等しい場合、それらは同じ hashCode() 値を持っている必要があります(ただし、逆は一般に当てはまりません)。[強調は私が追加しました]

私の質問は、「逆は一般的に真実ではありませんが」、段落の後半に関連しています。クラスの 2 つの異なるインスタンスが同じ hashCode を持っているが、等しくないということはどうして可能なのでしょうか?

4

8 に答える 8

17

簡単に言えば、 hashcode () は何らかの式によってハッシュを生成する関数であるため、いくつかの衝突が発生する可能性があり、2 つの異なる値が同じハッシュコードを持つことが判明する可能性があります。

mod を 6 で単純にハッシュコードを計算すると、2 つの異なる値が同じハッシュコードを持つ可能性があります。

于 2012-10-03T11:51:45.393 に答える
5

あなたは考えることができhashes to be a bucketます..

  • 2 つのオブジェクトが等しい場合、それらは同じバケットに入れられます(同じハッシュコードを持ちます)。
  • ただし、2 つのオブジェクトが同じバケット(同じハッシュコードを持つ) に入ったとしても、それらが等しい必要があるという意味ではありません。
  • また、2 つのオブジェクトが等しくない場合でも、同じハッシュ コードを持つことができることに注意してください。明らかに、これは上記の 2 つの点から推測されます。

したがって、ハッシュコードはそのバケットのハッシュ値に他なりません.ハッシュコードの計算に使用されるアルゴリズムに応じて、任意の数のオブジェクトが同じハッシュコードを持つことができます..

理想的なアルゴリズムは、オブジェクトごとに異なるハッシュコードを生成するアルゴリズムです。したがって、理想的には1 objectあたりがありbucketます..もちろん、これは完璧なケースですが、不可能かもしれません..

もちろん、バケットには、いくつかのプロパティに基づいて複数のオブジェクトが含まれる場合があります..

于 2012-10-03T11:54:35.713 に答える
4

ハッシュコードは、等価性をチェックする労力を軽減するものと考えてください。2 つのオブジェクトが等しい場合、それらは間違いなく同じハッシュコードを持ちます。ただし、2 つのオブジェクトのハッシュコードが同じである場合、数学的には類似性が高くても、同じではない可能性があります。考え方としては、アヒルを動物園のゾウと比較することを考えてみてください。それらは非常に似ておらず、異なる抽象ハッシュコードを持つため、同じかどうかを確認するために足や翼などを比較する必要はありません。ただし、アヒルと白鳥を比較する場合、それらは非常に類似しており、同じ抽象的なハッシュコードを持っているため、各動物の非常に細かい特徴を比較して同等性を確認する必要があります。比較される 2 つの要素間の極端さを減らすと、抽象的なハッシュコードはより具体的になります。アヒルと白鳥を比較すると、アヒルとゾウを比較するよりも具体的なハッシュコードが得られるように、異なる品種のアヒルを比較すると、ハッシュコードがさらに具体的になり、同じ品種の 2 羽のアヒルの DNA を比較すると、ハッシュコードがさらに具体的になります。この回答は、ハッシュコードの概念を理解するための考え方を作成するように設計されています。これを読んだ後、この回答のコンテキストでハッシュコードという単語の理解を曖昧にする必要があります。

于 2016-12-27T02:54:44.050 に答える
3

本当は逆だと思う

equals() メソッドに従って 2 つのオブジェクトが等しくない場合、それらは A DIFFERENT hashCode() 値を持つ必要があります

通常、値のセットをより低いカーディナリティのハッシュコードのセットにマップしようとしているため、一般的なケースで一意のハッシュを生成することは不可能であるため、これは明らかに当てはまりません。

于 2012-10-03T11:52:09.833 に答える
2

例を使って説明します。hashCode()文字列が文字列の長さに基づいているとしましょう 。この場合、"foo"とのハッシュ コード"bar"は同じです。しかし、"foo"それ自体は と等しくありません"bar"。

has コードは一種の式を実装しているためです。各オブジェクトの has コードを決定することはできますが、ハッシュ コードからオブジェクトを復元することはできません。同じハッシュ コードを持つ複数のオブジェクトが存在する可能性があります。

于 2012-10-03T11:54:40.550 に答える
1

hashCode()たとえば、常に返すように実装を定義できます1。これは完全に有効です: 異なるインスタンス ( ではないequal) が同じ を持つことができますhashCode。しかしHashMaps、Setsやその他のタイプのコレクションでこれらのオブジェクトをルックアップする実行時のパフォーマンスは非常に低くなります (それらはすべて内部的に同じバケットに到達するためです。同じバケット内のオブジェクトのリストをトラバースする必要があるため、ルックアップのパフォーマンスは からO(1)まで低下します)。 O(n)）。

Java で HashMaps がどのように機能するかについても検討してください。

于 2012-10-03T11:54:44.520 に答える
0

通常、オブジェクトのハッシュ コードは、元のオブジェクトよりもはるかに小さくなります。これがハッシュ関数の目的の 1 つです。したがって、n個の異なるオブジェクト（クラスのすべての順列など）がある場合、それらをm（m <n）の異なる、（元のオブジェクトよりも）小さい一意のコードでコーディングすることはできないと想像できます。

于 2012-10-03T11:55:43.777 に答える
0

例を示しましょう：

文字列の HashCode が次のようになるとします: hashCode = 各文字の ASCII コードの合計 (しかし、実際のハッシュはもっと複雑です)

例: "abc" のハッシュ コードは次のような形式で計算されます: 49+50+51 = 150

「acb」のハッシュコードは次のようになります: 49+51+50 = 150

等々。ご覧のとおり、hashcode=150 の文字列は多数ありますが、それらは等しくありません。

于 2012-10-03T12:04:50.583 に答える