16

ハッシュマップでは、提供されたキーのハッシュコードを使用して、値をハッシュテーブルに配置します。ハッシュセットでは、オブジェクトハッシュコードを使用して、基になるハッシュテーブルに値を配置します。つまり、ハッシュマップの利点は、キーとして何を使用するかを柔軟に決定できるため、このような優れた処理を実行できることです。

Map<String,Player> players = new HashMap<String,Player>();

これにより、プレーヤー名などの文字列をプレーヤー自体にマップできます。

私の質問は、キーのハッシュコードが変更されたときにルックアップがどうなるかということです。

これは、キーが変更されることを期待も望まないので、ハッシュマップにとってそれほど大きな懸念事項ではないと思います。前の例では、プレーヤーの名前が変更された場合、そのプレーヤーではなくなります。ただし、キーを使用してプレーヤーを検索することはできますが、名前ではない他のフィールドを変更すると、将来の検索が機能します。

ただし、ハッシュセットでは、オブジェクト全体のハッシュコードがアイテムの配置に使用されるため、誰かがオブジェクトをわずかに変更した場合、オブジェクト全体のハッシュコードに依存するため、そのオブジェクトの将来のルックアップはハッシュテーブル内の同じ位置に解決されなくなります。これは、データがハッシュセットに入ると、変更してはならないことを意味しますか？または、再ハッシュする必要がありますか？それとも自動的に行われますか？何が起こっている？

4

4 に答える 4

20

あなたの例では、文字列は不変であるため、そのハッシュコードは変更できません。しかし、仮に、オブジェクトのハッシュコードがハッシュテーブルのキーである間に変更された場合、ハッシュテーブルのルックアップに関する限り、オブジェクトはおそらく消えます。関連する質問へのこの回答でより詳細に説明しました： https ：//stackoverflow.com/a/13114376/139985 。（元の質問はについてですHashSetが、aHashSetは実際には隠蔽HashMapされているため、回答はこの場合もカバーします。）

HashMapまたはTreeMapのいずれかのキーが、それぞれのhashcode()/equals(Object)またはコントラクトに影響を与える方法で変更されたcompare(...)場合compareTo(...)、データ構造は「破損」すると言っても過言ではありません。

これは、データがハッシュセットに入れられたら、変更してはならないことを意味しますか？

はい。

または、再ハッシュする必要がありますか？それとも自動的に行われますか？

自動的に再ハッシュされることはありません。キーのHashMapハッシュコードが変更されたことに気付かないでしょう。実際、HashMapサイズ変更時にハッシュコードの再計算を取得することもできません。データ構造は元のハッシュコード値を記憶しているため、ハッシュテーブルのサイズが変更されたときにすべてのハッシュコードを再計算する必要がありません。

キーのハッシュコードが変更されることがわかっている場合は、キーを変更する前にテーブルからエントリを削除し、後で追加し直す必要があります。（キーを変更した後にremove/しようとすると、エントリが見つからない可能性があります。）putremove

何が起こっている？

何が起こっているのかというと、あなたは契約に違反したということです。そうしないでください！

契約は2つのもので構成されています：

  1. のjavadocで指定されている標準のハッシュコード/equalsコントラクトObject。

  2. オブジェクトのハッシュコードがハッシュテーブルのキーである間は変更してはならないという追加の制約。

後者の制約はHashMap javadocで具体的に述べられていませんが、javadocは次のようにMap述べています。

注：可変オブジェクトをマップキーとして使用する場合は、細心の注意を払う必要があります。equalsオブジェクトがマップのキーであるときに、オブジェクトの値が比較に影響を与える方法で変更された場合、マップの動作は指定されません。

平等に（通常）影響する変更は、ハッシュコードにも影響します。実装レベルでは、HashMapエントリのキーのハッシュコードが変更された場合、エントリは通常、HashMap間違ったハッシュバケットに配置され、ルックアップを実行するメソッドからは見えなくなります。

于 2012-11-01T12:52:06.820 に答える
3

あなたの例では、キーは不変の文字列です。したがって、キーのハッシュコードは変更されません。キーのハッシュコードが変更されたときに何が起こるかは未定義であり、「奇妙な」動作につながります。以下の例を参照してください。1、false、および2が出力されます。オブジェクトはセットに残りますが、セットは壊れているように見えます（containsはfalseを返します）。

Setのjavadocから抽出：

注：可変オブジェクトをセット要素として使用する場合は、細心の注意を払う必要があります。オブジェクトがセット内の要素であるときに、等しい比較に影響を与える方法でオブジェクトの値が変更された場合、セットの動作は指定されません。この禁止の特殊なケースは、セットがそれ自体を要素として含むことは許可されないということです。

public static void main(String args[]) {
    Set<MyObject> set = new HashSet<>();
    MyObject o1 = new MyObject(1);
    set.add(o1);
    o1.i = 2;
    System.out.println(set.size());       //1
    System.out.println(set.contains(o1)); //false
    for (MyObject o : set) {
        System.out.println(o.i);          //2
    }
}

private static class MyObject {
    private int i;

    public MyObject(int i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return i;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final MyObject other = (MyObject) obj;
        if (this.i != other.i) return false;
        return true;
    }
}
于 2012-11-01T12:42:46.457 に答える
0

はHashSetによってバックアップされますHashMap。

javadocsから。

このクラスは、ハッシュテーブル（実際にはHashMapインスタンス）に裏打ちされたSetインターフェイスを実装します。

したがって、ハッシュコードを変更すると、オブジェクトにアクセスできるかどうか疑問に思います。

内部実装の詳細

のadd実装HashSetは

 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
 }

キーは要素であり、値はPRESENTと呼ばれる単なるダミーオブジェクトです。

contains実装は

public boolean contains(Object o) {
        return map.containsKey(o);
}
于 2012-11-01T12:36:49.860 に答える
0

Javaのハッシュでは、元の参照が単に見つかりません。現在のハッシュコードに対応するバケットで検索されましたが、見つかりませんでした。

事後にこれから回復するには、ハッシュkeySetを繰り返し処理する必要があり、containsメソッドで見つからないキーはすべてイテレーターで削除する必要があります。マップからキーを削除してから、新しいキーで値を保存することをお勧めします。

于 2012-11-01T12:43:42.167 に答える