23

java.lang.Object の equals() 関数をオーバーライドする場合、javadoc は次のように提案しています。

通常、このメソッドがオーバーライドされるときは常に、hashCode メソッドをオーバーライドする必要があります。これは、等しいオブジェクトには等しいハッシュ コードが必要であるという、hashCode メソッドの一般的な規約を維持するためです。

hashCode() メソッドは、オブジェクトごとに一意の整数を返す必要があります (これは、メモリ位置に基づいてオブジェクトを比較する場合に簡単に実行できます。オブジェクトの一意の整数アドレスを返すだけです)。

各オブジェクトのプロパティのみに基づいて一意の整数を返すには、hashCode() メソッドをどのようにオーバーライドする必要がありますか?


public class People{
   public String name;
   public int age;

   public int hashCode(){
      // How to get a unique integer based on name and age?
   }
}
/*******************************/
public class App{
   public static void main( String args[] ){
       People mike = new People();
       People melissa = new People();
       mike.name = "mike";
       mike.age = 23;
       melissa.name = "melissa";
       melissa.age = 24;
       System.out.println( mike.hasCode() );  // output?
       System.out.println( melissa.hashCode(); // output?
   }
}
4

8 に答える 8

29

オブジェクトのハッシュコードが完全に一意である必要があるとは言いませんが、2 つの等しいオブジェクトのハッシュコードが同じハッシュコードを返すというだけです。2 つの等しくないオブジェクトが同じハッシュコードを返すことは完全に合法です。ただし、一連のオブジェクトに対するハッシュコードの分布が一意であるほど、ハッシュコードを使用する HashMap やその他の操作から得られるパフォーマンスが向上します。

IntelliJ Idea などの IDE には、equals と hashCode の組み込みジェネレーターがあり、ほとんどのオブジェクトに対して "十分な" コードを作成するのに非常に優れています (おそらく、手作りの非常に巧妙なハッシュ関数よりも優れています)。

たとえば、これは Idea が People クラス用に生成する hashCode 関数です。

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}
于 2009-01-04T01:39:43.970 に答える
9

マークがすでに対処しているため、hashCode の一意性については詳しく説明しません。あなたのPeopleクラスでは、まず人の平等が何を意味するかを決める必要があります。平等は名前だけに基づいているのかもしれませんし、名前と年齢に基づいているのかもしれません。ドメイン固有のものになります。平等は名前と年齢に基づいているとしましょう。あなたのオーバーライドequalsは次のようになります

public boolean equals(Object obj) {
    if (this==obj) return true;
    if (obj==null) return false;
    if (!(getClass().equals(obj.getClass())) return false;
    Person other = (Person)obj;
    return (name==null ? other.name==null : name.equals(other.name)) &&
        age==other.age;
}

オーバーライドするときはいつでも、オーバーライドequalsする必要がありますhashCode。さらに、hashCodeその計算で使用したフィールドよりも多くのフィールドを使用することはできませんequals。ほとんどの場合、さまざまなフィールドのハッシュ コードを追加または排他的または排他的にする必要があります (hashCode は計算が高速である必要があります)。したがって、有効なhashCodeメソッドは次のようになります。

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age;
}

以下は有効ではないフィールドequals(高さ)を使用しているため、有効ではないことに注意してください。この場合、2 つの「等しい」オブジェクトが異なるハッシュ コードを持つ可能性があります。

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}

また、2 つの等しくないオブジェクトが同じハッシュ コードを持つことは完全に有効です。

public int hashCode() {    
    return age;    
}

この場合、ジェーンの年齢 30 はボブの年齢 30 と等しくありませんが、両方のハッシュ コードは 30 です。これは有効ですが、ハッシュ ベースのコレクションのパフォーマンスには望ましくありません。

于 2009-01-04T01:48:43.047 に答える
8

別の質問では、すべてのプログラマーが知っておくべき基本的な低レベルの事柄があるかどうかを尋ねます。ハッシュ ルックアップはその 1 つだと思います。だからここに行きます。

ハッシュ テーブル (実際のクラス名を使用していないことに注意してください) は、基本的にリンクされたリストの配列です。テーブルで何かを見つけるには、まずその何かのハッシュコードを計算し、次にテーブルのサイズでそれを変更します。これは配列へのインデックスであり、そのインデックスでリンクされたリストを取得します。次に、オブジェクトが見つかるまでリストをたどります。

配列の取得は O(1) であり、リンクされたリストのトラバーサルは O(n) であるため、オブジェクトが異なるリストにハッシュされるように、可能な限りランダムな分布を作成するハッシュ関数が必要です。すべてのオブジェクトはハッシュコードとして値 0 を返す可能性があり、ハッシュ テーブルは引き続き機能しますが、基本的に配列の要素 0 にある長いリンク リストになります。

また、通常は配列を大きくする必要があるため、オブジェクトが長さ 1 のリストに含まれる可能性が高くなります。たとえば、Java HashMap は、マップ内のエントリ数が 75 を超えると配列のサイズを大きくします。配列のサイズの %。ここにはトレードオフがあります。非常に少ないエントリでメモリを浪費する巨大な配列を持つか、配列内の各要素が 1 つ以上のエントリを持つリストである小さな配列を持つことができ、トラバースに時間がかかります。完全なハッシュは、各オブジェクトを配列内の一意の場所に割り当て、スペースを無駄にしません。

「完全なハッシュ」という用語は実際の用語であり、場合によっては、各オブジェクトに一意の番号を提供するハッシュ関数を作成できます。これは、すべての可能な値のセットを知っている場合にのみ可能です。一般的なケースでは、これを達成することはできず、同じハッシュコードを返す値がいくつかあります。これは単純な数学です。4 バイトを超える文字列がある場合、一意の 4 バイト ハッシュコードを作成することはできません。

1 つの興味深い情報: ハッシュ配列は通常、素数に基づいてサイズ設定されます。これは、ハッシュコードが実際にどれほどランダムであるかに関係なく、結果を変更するときにランダム割り当ての可能性を最大限に高めるためです。

コメントに基づいて編集：

1) リンクされたリストは、同じハッシュコードを持つオブジェクトを表す唯一の方法ではありませんが、これは JDK 1.5 HashMap で使用される方法です。単純な配列よりもメモリ効率は劣りますが、再ハッシュ時のチャーンが少なくなることは間違いありません (エントリをあるバケットからリンク解除して別のバケットに再リンクできるため)。

2) JDK 1.4 以降、HashMap クラスは 2 の累乗のサイズの配列を使用します。それ以前は 2^N+1 を使用していましたが、これは N <= 32 に対して素数であると私は信じています。 Neil Coffey が指摘したように。個人的には、これは時期尚早の最適化ではないかと疑問に思いますが、HashMap の作成者のリストを考えると、実際にメリットがあると思います。

于 2009-01-04T03:23:53.040 に答える
1

一般に、可能なハッシュ コード (整数) よりも多くの値があるため、ハッシュ コードを一意にすることはできません。適切なハッシュ コードでは、値が整数全体に分散されます。悪いものは常に同じ値を与える可能性があり、それでも論理的には正しく、許容できないほど非効率的なハッシュ テーブルにつながるだけです。

ハッシュ テーブルが正しく機能するには、等しい値のハッシュ値が同じである必要があります。そうしないと、ハッシュ テーブルにキーを追加してから、別のハッシュ コードを使用して同等の値で検索しようとしても見つからない可能性があります。または、異なるハッシュ コードを使用して等しい値を配置し、ハッシュ テーブルの異なる場所に 2 つの等しい値を配置することもできます。

実際には、通常、hashCode() メソッドと equals() メソッドの両方で考慮されるフィールドのサブセットを選択します。

于 2009-01-04T08:48:43.103 に答える
0

あなたはそれを誤解していると思います。ハッシュコードは、すべてのオブジェクトで同一にする必要はありませんが、各オブジェクトに対して一意である必要はありません (結局のところ、これはハッシュ コードです)。ただし、等しいすべてのオブジェクトと同一である必要があります。そうしないと、標準コレクションのようなものが機能しません (たとえば、ハッシュ セットで何かを検索しても、それが見つからないなど)。

単純な属性の場合、一部の IDE にはハッシュコード関数ビルダーがあります。

IDE を使用しない場合は、Apahce Commons とクラス HashCodeBuilder の使用を検討してください。

于 2009-01-04T01:46:50.723 に答える
0

これは、ドキュメントがハッシュコードメソッドについて教えてくれるものです

@ javadoc

Java アプリケーションの実行中に同じオブジェクトに対して複数回呼び出された場合は常に、オブジェクトの equals 比較で使用される情報が変更されていない限り、hashCode メソッドは一貫して同じ整数を返す必要があります。この整数は、あるアプリケーションの実行から同じアプリケーションの別の実行まで一貫性を保つ必要はありません。

于 2010-01-02T15:17:24.240 に答える
0

hashCode の唯一の契約上の義務は、一貫性を保つことです。hashCode 値の作成に使用されるフィールドは、equals メソッドで使用されるフィールドと同じかサブセットである必要があります。これは、効率的ではありませんが、すべての値に対して 0 を返すことは有効であることを意味します。

単体テストで hashCode が一貫しているかどうかを確認できます。私はEqualityTestCaseという抽象クラスを作成しました。これは、いくつかの hashCode チェックを行います。テスト ケースを拡張し、2 つまたは 3 つのファクトリ メソッドを実装するだけです。このテストは、hashCode が効率的かどうかをテストするという非常に大雑把な作業を行います。

于 2009-10-18T22:33:08.093 に答える
0

同じタイプの個別のインスタンスの一意性を決定するビジネス キーの概念があります。ターゲット ドメイン (フリート システム内の車両など) とは別のエンティティをモデル化する特定のタイプ (クラス) ごとに、1 つ以上のクラス フィールドで表されるビジネス キーが必要です。メソッド equals() と hasCode() は両方とも、ビジネス キーを構成するフィールドを使用して実装する必要があります。これにより、両方の方法が互いに一貫していることが保証されます。

于 2010-12-18T19:58:00.237 に答える