19

java.util.HashMap私はとの内部実装を理解しようとしてきましたjava.util.HashSet。

以下は、しばらくの間私の頭に浮かんだ疑問です。

  1. @Override public int hashcode()HashMap / HashSetでの重要性は何ですか？このハッシュコードは内部でどこで使用されていますか？
  2. 私は一般的に、HashMapのキーがのStringようになるのを見てきましたmyMap<String,Object>。someObjectのように（文字列ではなく）値をマップできますmyMap<someObject, Object>か？これが成功するために私が従う必要があるすべての契約は何ですか？

前もって感謝します ！

編集：

  1. キーのハッシュコード（チェック！）は、値がハッシュテーブルにマップされる実際のものであると言っていますか？そして、myMap.get(someKey);Javaが内部的に呼び出しsomeKey.hashCode()て、ハッシュテーブル内の数値を取得し、結果の値を探しますか？

回答：はい。

編集2：

  1. でjava.util.HashSet、ハッシュテーブル用に生成されたキーはどこからですか？追加するのはオブジェクトからですか。mySet.add(myObject);次にmyObject.hashCode()、これをハッシュテーブルのどこに配置するかを決定しますか？（HashSetではキーを提供しないため）。

回答：追加されたオブジェクトがキーになります。値はダミーです！

4

9 に答える 9

15

質問 2 への答えは簡単です。はい、好きなオブジェクトを使用できます。String 型のキーを持つマップは、ネーム サービスの典型的なデータ構造であるため、広く使用されています。Map<Car,Vendor>ただし、一般に、またはのような任意の 2 つの型をマップできますMap<Student,Course>。

hashcode() メソッドについては、前に答えたようなものです - equals() をオーバーライドするときはいつでも、契約に従うために hashcode() をオーバーライドする必要があります。一方、equals() の標準実装に満足している場合は、hashcode() に触れるべきではありません (これにより、契約が破られ、等しくないオブジェクトに対して同一のハッシュコードが生成される可能性があるため)。

実用的な補足事項: eclipse (およびおそらく他の IDE も同様) は、クラス メンバーに基づいて、クラスの equals() と hashcode() の実装のペアを自動生成できます。

編集

追加の質問について: はい、正確に。HashMap.get(Object key); のソース コードを見てください。key.hashcode を呼び出して、内部ハッシュ テーブル内の位置 (ビン) を計算し、その位置の値を返します (存在する場合)。

ただし、「手作り」の hashcode/equals メソッドには注意してください。オブジェクトをキーとして使用する場合は、後でハッシュコードが変更されないようにしてください。そうしないと、マップされた値が見つからなくなります。つまり、equals と hashcode を計算するために使用するフィールドは、final (またはオブジェクトの作成後は「変更不可」) である必要があります。

String nameandとの連絡先がありString phonenumber、両方のフィールドを使用して equals() と hashcode() を計算するとします。次に、彼の携帯電話番号を使用して "John Doe" を作成し、彼をお気に入りのドーナツ ショップにマップします。hashcode() は、ハッシュ テーブルのインデックス (ビン) を計算するために使用され、そこにドーナツ ショップが格納されます。

ここで、彼が新しい電話番号を持っていることを知り、John Doe オブジェクトの電話番号フィールドを変更します。これにより、新しいハッシュコードが生成されます。そして、このハッシュコードは新しいハッシュ テーブル インデックスに解決されます。これは通常、John Does のお気に入りのドーナツ ショップが格納されていた場所ではありません。

問題は明らかです。この場合、「John Doe と特定の電話番号」ではなく、「John Doe」をドーナツ ショップにマップする必要がありました。そのため、自動生成された equals/hashcode に注意して、それらが本当に必要なものであることを確認する必要があります。不要なフィールドが使用され、HashMaps と HashSets に問題が発生する可能性があるためです。

編集 2

オブジェクトを HashSet に追加すると、オブジェクトは内部ハッシュ テーブルのキーになり、値は設定されますが使用されません (オブジェクトの静的インスタンスにすぎません)。openjdk 6 (b17) の実装は次のとおりです。

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;

public boolean add(E e) {
  return map.put(e, PRESENT)==null;
}
于 2009-11-23T09:16:47.367 に答える
6

ハッシュ コンテナーは、コンテナーの内容を "バケット" に分割することで、格納されている要素にすばやくアクセスできるようHashMapにします。HashSet

たとえば、数値のリスト:1, 2, 3, 4, 5, 6, 7, 8に保存されているListものは、(概念的に) メモリ内では次のようになります[1, 2, 3, 4, 5, 6, 7, 8]。

同じ数値セットを a に格納すると、次のSetようになります[1, 2] [3, 4] [5, 6] [7, 8]。この例では、リストは 4 つのバケットに分割されています。

ここで、と6の両方から値を見つけたいとします。リストでは、リストの先頭から始めて、6 になるまで各値をチェックする必要があります。これには 6 つのステップが必要です。セットを使用して正しいバケットを見つけ、そのバケット内の各項目 (この例では 2 つだけ) をチェックして、これを 3 ステップのプロセスにします。このアプローチの価値は、データが増えるほど劇的に増加します。ListSet

しかし、どのバケットを調べるかをどのようにして知ったのでしょうか? そこでhashCodeメソッドの出番です。アイテムを探すバケットを決定するには、Java ハッシュ コンテナーを呼び出しhashCode、その結果に何らかの関数を適用します。この関数は、検索を可能な限り高速化するために、バケットの数とアイテムの数のバランスをとろうとします。

検索中に正しいバケットが見つかると、そのバケット内の各項目がリストのように一度に 1 つずつ比較されます。そのため、オーバーライドするときに もオーバーライドhashCodeする必要がありますequals。したがって、任意のタイプのオブジェクトにequalsとメソッドの両方がある場合、 のキーまたは のエントリhashCodeとして使用できます。これらのメソッドを正しく実装するために従わなければならない契約があります。これに関する正規のテキストは、Josh Bloch の優れた本「Effective Java: Item 8: Always override hashCode when you override equals」からのものです。MapSet

于 2009-11-23T09:48:39.367 に答える
5

HashMap/HashSetでの@Overridepublicint hashcode（）の重要性は何ですか？

これにより、マップのインスタンスは、マップのコンテンツに応じて有用なハッシュコードを生成できます。同じコンテンツの2つのマップは、同じハッシュコードを生成します。内容が異なる場合、ハッシュコードも異なります。

このハッシュコードは内部でどこで使用されていますか？

一度もない。このコードは存在するだけなので、マップを別のマップのキーとして使用できます。

someObjectのように（ではなくString）値をマッピングできますmyMap<someObject, Object>か？

はい。ただしsomeObject、オブジェクトではなくクラスである必要があります（名前は、オブジェクトを渡したいことを示していますSomeObject。タイプを参照していることを明確にする必要があります）。

これが成功するために私が従う必要があるすべての契約は何ですか？

クラスはとを実装する必要がhashCode()ありequals()ます。

[編集]

キーのハッシュコード（チェック！）は、値がハッシュテーブルにマップされる実際のものであると言っていますか？

はい。

于 2009-11-23T09:00:52.657 に答える
5

はい。HashMap では、任意のオブジェクトをキーとして使用できます。そのためには、次の手順に従う必要があります。

  1. equals をオーバーライドします。

  2. hashCode をオーバーライドします。

両方のメソッドのコントラクトは、java.lang.Object のドキュメントに非常に明確に記載されています。http://java.sun.com/javase/6/docs/api/java/lang/Object.html

はい、 hashCode() メソッドは HashMap によって内部的に使用されるため、適切な値を返すことはパフォーマンスにとって重要です。

HashMap の hashCode() メソッドは次のとおりです。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

上記のコードから明らかなように、各キーの hashCode は、マップの hashCode() に使用されるだけでなく、キーと値のペアを配置するバケットを見つけるためにも使用されます。そのため、 hashCode() は HashMap のパフォーマンスに関連しています

于 2009-11-23T09:04:59.590 に答える
3
  1. ObjectJavaのすべてにhashCode()メソッドが必要です。HashMapとHashSetは例外ではありません。このハッシュコードは、ハッシュマップ/セットを別のハッシュマップ/セットに挿入する場合に使用されます。
  2. HashMap/のキーとして任意のクラスタイプを使用できますHashSet。これには、hashCode()メソッドが等しいオブジェクトに対して等しい値を返すこと、およびequals()メソッドがコントラクト（再帰的、推移的、対称的）に従って実装されている必要があります。のデフォルトの実装はObjectすでにこれらのコントラクトに従いますが、参照の同等性ではなく値の同等性が必要な場合は、それらをオーバーライドすることをお勧めします。
于 2009-11-23T09:02:35.940 に答える
2

hashcode()equals（）と、Javaの一般的なハッシュテーブル（さらに言えば、.NETも）の間には複雑な関係があります。ドキュメントから引用するには：

public int hashCode()

オブジェクトのハッシュコード値を返します。このメソッドは、によって提供されるようなハッシュテーブルの利益のためにサポートされていjava.util.Hashtableます。

hashCodeの一般的なコントラクトは次のとおりです。

  • Javaアプリケーションの実行中に同じオブジェクトで複数回呼び出される場合は常に、オブジェクトのequals比較で使用される情報が変更されていない限り、hashCodeメソッドは一貫して同じ整数を返す必要があります。この整数は、アプリケーションのある実行から同じアプリケーションの別の実行まで一貫している必要はありません。
  • equals（Object）メソッドに従って2つのオブジェクトが等しい場合、2つのオブジェクトのそれぞれでhashCodeメソッドを呼び出すと、同じ整数の結果が生成される必要があります。
  • equals（）メソッドに従って2つのオブジェクトが等しくない場合、2つのオブジェクトのそれぞれでメソッドjava.lang.Objectを呼び出すと、hashCode異なる整数の結果が生成される必要はありません。ただし、プログラマーは、等しくないオブジェクトに対して個別の整数結果を生成すると、ハッシュテーブルのパフォーマンスが向上する可能性があることに注意する必要があります。

合理的に実用的である限りhashCode、クラスによって定義されたメソッドObjectは、個別のオブジェクトに対して個別の整数を返します。（これは通常、オブジェクトの内部アドレスを整数に変換することによって実装されますが、この実装手法はJava™プログラミング言語では必要ありません。）

この線

@Overrides public int hashCode()

hashCode()メソッドがオーバーライドされたことを通知するだけです。これは通常、タイプをキーとして使用しても安全であることを示していますHashMap。

equals()そして、はい、あなたはキーとしてhashCode()の契約に従うどんなオブジェクトでも簡単に使うことができHashMapます。

于 2009-11-23T09:01:49.887 に答える
2

アーロン・ディグラは完全に正しいです。人々が気付いていないように見える興味深い追加の注記は、キー オブジェクトの hashCode() メソッドが逐語的に使用されていないことです。実際、これは HashMap によって再ハッシュされます。つまり、hash(someKey.hashCode))はhash()内部ハッシュ メソッドを呼び出します。

これを確認するには、ソースを見てください: http://kickjava.com/src/java/util/HashMap.java.htm

この理由は、hashCode() の実装が不十分な人がいて、hash() 関数がより良いハッシュ分散を提供するためです。これは基本的にパフォーマンス上の理由から行われます。

于 2009-11-23T09:35:55.227 に答える
2

質問 2 の答えとして、Hashmap のキーとして使用できる任意のクラスを使用できますが、ベスト プラクティスは、不変クラスを HashMap のキーとして使用することです。または、少なくとも「hashCode」と「equals」の実装がクラスの属性の一部に依存している場合は、これらの属性を変更するメソッドを提供しないように注意する必要があります。

于 2009-11-23T09:36:49.720 に答える
0

HashSet、HashTable、HashMap などのコレクション クラスの HashCode メソッド – ハッシュ コードは、ハッシュの目的でサポートされているオブジェクトの整数値を返します。オブジェクトの内部アドレスを整数に変換することで実装されます。equals メソッドをオーバーライドするすべてのクラスで、ハッシュ コード メソッドをオーバーライドする必要があります。HashCode方式の三大連絡先

  • 2 つの等しいオブジェクトの acc。equal メソッドに接続し、両方のオブジェクトに対して HashCode を呼び出すと、同じ整数値が生成されます。

  • 1 つのオブジェクトに対して複数回呼び出されている場合は、定数の整数値を返す必要があります。

  • 2 つの等しくないオブジェクトの acc。equal メソッドに変換し、両方のオブジェクトに対して HashCode メソッドを呼び出す場合、異なる値を生成する必要はありません。

于 2012-04-03T09:07:11.633 に答える