Wie Sets als Schlüssel in Java Karten verwenden

Question

ich eine Karte haben, die ein Set für den Schlüsseltyp verwendet, wie folgt aus:

Map<Set<Thing>, Val> map; 

Als ich map.containsKey (myBunchOfThings) abfragen, gibt es falsch ist, und Ich verstehe nicht warum. Ich kann durch jeden Schlüssel im Schlüsselsatz iterieren und verifizieren, dass es einen Schlüssel gibt, der (1) denselben hashCode hat, und (2) ist gleich() zu myBunchOfThings.

System.out.println(map.containsKey(myBunchOfThings)); // false. 
for (Set<Thing> k : map.keySet()) { 
    if (k.hashCode() == myBunchOfThings.hashCode() && k.equals(myBunchOfThings) { 
    System.out.println("Fail at life."); // it prints this. 
    } 
} 

Verstehe ich den Vertrag für containsKey nur grundlegend falsch? Gibt es ein Geheimnis, Sets (oder allgemeiner Sammlungen) als Schlüssel für Maps zu verwenden?

Answer 1

Der Schlüssel sollte nicht mutiert sein, während er in der Karte verwendet wird. Die Map java doc sagt:

Hinweis: große Sorgfalt, wenn veränderbare Objekte als Kartenschlüssel verwendet werden ausgeübt werden müssen. Das Verhalten einer Karte ist nicht angegeben, wenn der Wert eines Objekts in einer Weise geändert wird, dass Vergleiche wirkt sich gleich, während das Objekt ein Schlüssel in der Karte ist. Ein Sonderfall dieses Verbots ist, dass es nicht zulässig ist, dass eine Karte selbst als Schlüssel enthält. Während es zulässig ist, dass eine Karte selbst als Wert enthält, ist extreme Vorsicht empfohlen: Die Methoden equals und hashCode sind nicht mehr gut auf eine solche Karte definiert.

wusste, dass ich dieses Problem, aber bisher noch nie den Test gemacht. Ich erarbeiten dann ein bisschen mehr:

Map<Set<String>, Object> map = new HashMap<Set<String>, Object>(); 

    Set<String> key1 = new HashSet<String>(); 
    key1.add("hello"); 

    Set<String> key2 = new HashSet<String>(); 
    key2.add("hello2"); 

    Set<String> key2clone = new HashSet<String>(); 
    key2clone.add("hello2"); 

    map.put(key1, new Object()); 
    map.put(key2, new Object()); 

    System.out.println(map.containsKey(key1)); // true 
    System.out.println(map.containsKey(key2)); // true 
    System.out.println(map.containsKey(key2clone)); // true 

    key2.add("mutate"); 

    System.out.println(map.containsKey(key1)); // true 
    System.out.println(map.containsKey(key2)); // false 
    System.out.println(map.containsKey(key2clone)); // false (*) 

    key2.remove("mutate"); 

    System.out.println(map.containsKey(key1)); // true 
    System.out.println(map.containsKey(key2)); // true 
    System.out.println(map.containsKey(key2clone)); // true 

Nach key2 mutiert ist, wird die Karte nicht mehr enthalten. Wir könnten denken, dass die Karte die Daten "indiziert", wenn sie hinzugefügt wird, und wir würden dann erwarten, dass sie immer noch den Schlüssel2-Klon enthält (Zeile markiert mit *). Aber lustig genug, das ist nicht der Fall.

Also, wie der Java-Doc sagt, Schlüssel sollten nicht mutiert sein, sonst ist das Verhalten nicht näher. Zeitraum.

Ich denke, das passiert in Ihrem Fall.

Answer 2

Haben Sie das Set nach dem Einfügen geändert? Wenn dies der Fall ist, ist es möglich, dass das Set in einen anderen Bucket als den, in dem es sich befindet, sortiert wird. Beim Iterieren findet es Ihr Set, weil es in der ganzen Map aussieht.

Ich glaube, der Vertrag für HashMap heißt Sie nicht die Hash-Code für Objekte erlaubt als Schlüssel verwendet zu modifizieren,

Answer 3

Sind Sie den genauen Satz vorbei (das Set Sie suchen möchten), wenn für den Schlüssel zu vergleichen ?

Answer 4

Sie sollten sich bemühen, unveränderliche Typen als Schlüssel für Map s zu verwenden. Sammlungen und Mengen sind im Allgemeinen sehr leicht veränderbar, so dass es normalerweise keine gute Idee ist, diesen Weg zu wählen.

Wenn Sie viele Schlüsselwerte als Map Schlüssel verwenden möchten, sollten Sie eine Klassenimplementierung verwenden, die für diesen Zweck entwickelt wurde, wie Apache Commons Collections MultiKey.

Wenn Sie ein Set oder eine Collection wirklich als Schlüssel verwenden müssen, machen Sie es zunächst unveränderlich (Collections.unmodifiableSet(...)) und behalten Sie dann keinen Verweis auf das veränderbare Backing-Objekt.

Eine weitere Schwierigkeit bei der Verwendung von Sammlungen als Schlüssel besteht darin, dass sie in einer anderen Reihenfolge erstellt werden können. Nur eine sortierte Sammlung hat eine hohe Wahrscheinlichkeit von Übereinstimmungen. Wenn Sie zum Beispiel eine sequenziell geordnete ArrayList verwenden, aber die Liste beim zweiten Mal anders aufbauen, wird der Schlüssel nicht übereinstimmen - der Hash-Code und die Reihenfolge der Werte sind unterschiedlich.

BEARBEITEN: Ich stehe korrigiert auf diese Aussage unten, nie Set für einen Ket verwenden musste. Ich habe gerade einen Teil der hashCode-Implementierung in AbstractHashSet gelesen. Dies verwendet eine einfache Summe aller Werte und ist daher nicht von der Reihenfolge abhängig. Equals überprüft auch, ob eine Menge alle Werte in der anderen Menge enthält. Dies trifft jedoch immer noch auf andere Arten von Sammlungen in Java zu (ArrayList-Reihenfolge spielt eine Rolle).

Wenn Ihre Sammlung tatsächlich eine HashSet ist, kann die Erstellungsreihenfolge auch wichtig sein. In der Tat wird eine Hash-verwaltete Sammlung jeglicher Art noch problematischer, da jede Kapazitätsänderung eine Neuerstellung der gesamten Sammlung auslöst, die die Elemente neu anordnen kann. Denken Sie an Kollisionen von Hashwerten, die in der Reihenfolge gespeichert sind, in der die Kollision auftritt (eine einfache verknüpfte Kette aller Elemente, in denen der transformierte Hashwert derselbe ist).