Iterationsreihenfolge von HashSet

Question

Wenn jedes Objekt, das zu einem java.util.HashSet hinzugefügt wird, Object.equals() und Object.hashCode() deterministisch implementiert, ist die Iterationsreihenfolge über das HashSet garantiert identisch für jeden identischen Satz von Elementen hinzugefügt, unabhängig der Reihenfolge, in der sie hinzugefügt wurden?

Bonusfrage: Was ist, wenn der Anzeigenauftrag identisch ist?

(Unter der Annahme, Sun JDK6 mit gleicher HashSet Initialisierung.)

Edit: Meine ursprüngliche Frage nicht klar war. Es geht nicht um den allgemeinen Vertrag von HashSet, sondern darum, was Suns Implementierung von HashSet in JDK6 als Garantien für Determinismus bietet. Ist es von Natur aus nicht deterministisch? Was beeinflusst die Reihenfolge des Iterators?

Answer 1

Absolut nicht.

Der Auftrag beeinflusst direkt die Iteration, um, wenn Sie einen Eimer Kollision haben:

Wenn zwei Elemente in dem gleichen Eimer am Ende, die ersten, die auch eingesetzt worden ist, wird der erste, der während der Iteration zurückgebracht werden, um zumindest dann, wenn die Implementierung der Kollisionshandhabung und Iteration unkompliziert ist (und die in Suns java.util.HashMap ist)

Answer 2

Nein, dies ist nicht garantiert.

Erstens kann eine andere JVM den HashSet-Algorithmus anders implementieren (solange er der HashSet-Spezifikation entspricht), sodass Sie unterschiedliche Ergebnisse auf verschiedenen JVMs erhalten.

Zweitens kann der Algorithmus auf nicht-deterministischen Faktoren beruhen, wenn er die verschiedenen Buckets (Teil des Hash-Tabellen-Algorithmus) erstellt.

Answer 3

Gemäß der javadoc:

Diese Klasse implementiert die Set Schnittstelle, unterstützt durch eine Hash-Tabelle (eigentlich eine HashMap Instanz). Es macht keine Garantien bezüglich der Iterationsreihenfolge des Satzes; in insbesondere garantiert es nicht, dass die Reihenfolge über Zeit konstant bleibt. [...] Die Iteratoren von Klasse dieser Iteratormethode zurückgekehrt sind ausfall schnell: wenn der Satz jederzeit geändert wird, nachdem der Iterator

erstellt

Und die Methode iterator:

Gibt einen Iterator über die Elemente in diesem Set zurück. Die Elemente werden in keiner bestimmten Reihenfolge zurückgegeben.

Also ich glaube nicht, dass Sie eine solche Annahme machen können.

Answer 4

Es gibt keine "offizielle" Garantie für so etwas. Ich würde sagen, dass es wahrscheinlich für Instanzen der gleichen HashSet-Implementierung gilt, die auf die gleiche Weise initialisiert wurde. Aber ich habe Fälle gesehen, in denen die Iterationsreihenfolge beispielsweise zwischen Java 5 und 6 verschieden ist.

Es kann auch für Instanzen der gleichen HashSet-Implementierung anders sein, die mit unterschiedlicher Größe initialisiert wurden, weil sie erneut generiert wurden. I.e. Wenn Sie 100 Elemente und zwei Mengen haben, eine mit einer Größe größer als 100 initialisiert, die andere mit einer viel kleineren Größe, wird die zweite neu zugewiesen und ihre Elemente werden beim Auffüllen mehrmals aufgeräumt. Dies kann dazu führen, dass Elemente, die demselben Bucket zugeordnet sind, in anderer Reihenfolge hinzugefügt (und somit iteriert) werden.

In Java4 und höher haben Sie LinkedHashSet, die garantiert, dass die Iterationsreihenfolge die Reihenfolge ist, in der seine Elemente eingefügt wurden.

Answer 5

Ich bin mir sicher, dass die Java-Entwickler möchten, dass Sie die Antwort "Nein" annehmen. Insbesondere für Hashtabellen würden sie es für alle anderen langsamer machen, die diese Eigenschaft nicht benötigen, um zu garantieren, dass Objekte, deren Hashes kollidieren (identische HashCode% size), in derselben Reihenfolge beobachtet werden, unabhängig von ihrer Reihenfolge einstellen?

Answer 6

Eine solche Annahme kann nicht gemacht werden. Die javadoc sagt, dass:

Diese Klasse umfasst die Set -Schnittstelle implementiert, unterstützt durch eine Hash-Tabelle (eigentlich eine HashMap Instanz). Es macht keine Garantien bezüglich der Iterationsreihenfolge des Satzes; in insbesondere garantiert es nicht, dass die Reihenfolge über Zeit konstant bleibt.

Am nächsten kommt man mit einer LinkedHashSet, die den Anzeigenauftrag beibehält.

Answer 7

Niemals Annahmen über die Iterationsreihenfolge von irgendetwas, das Sie in ein HashSet setzen, machen, da sein Vertrag explizit besagt, dass Sie sich in keiner Weise darauf verlassen können. Verwenden Sie LinkedHashSet, wenn Sie den Anzeigenauftrag beibehalten möchten, oder TreeSet, wenn Sie eine natürliche Sortierreihenfolge beibehalten möchten.

Answer 8

Wollte frühere Kommentare bestätigen/upvote. Kurz gesagt, Verlassen Sie sich nicht auf die HashSet-Iteration in konsistenter Reihenfolge. Dies kann und wird Fehler in Ihrem System einführen.

Wir haben gerade und ein Bug behoben, der Iterationsreihenfolge in HashSet inkonsistent war sogar mit:

• Identische Auftrag.
• Objekte einer Klasse mit einer gültigen Methode equals() und hashCode().

Und es mit Hilfe von LinkedHashSet behoben.

Dank des früheren Poster :)

Answer 9

Die Reihenfolge Objekte auf der endgültigen Anzahl der Schaufeln des HashSet hängen erscheinen. Durch Ändern des Ladefaktors und/oder der Anfangskapazität können Sie die Reihenfolge der Elemente ändern.

Im folgenden Beispiel sehen Sie, dass diese Bestätigungen jeweils in einer anderen Reihenfolge angezeigt werden.

public static void main(String...args) throws IOException { 
    printOrdersFor(8, 2); 
    printOrdersFor(8, 1); 
    printOrdersFor(8, 0.5f); 
    printOrdersFor(32, 1f); 
    printOrdersFor(64, 1f); 
    printOrdersFor(128, 1f); 
} 

public static void printOrdersFor(int size, float loadFactor) { 
    Set<Integer> set = new HashSet<Integer>(size, loadFactor); 
    for(int i=0;i<=100;i+=10) set.add(i); 
    System.out.println("new HashSet<Integer>("+size+", "+loadFactor+") adding 0,10, ... 100 => "+set); 
} 

druckt

new HashSet<Integer>(8, 2.0) adding 0,10, ... 100 => [0, 50, 100, 70, 40, 10, 80, 20, 90, 60, 30] 
new HashSet<Integer>(8, 1.0) adding 0,10, ... 100 => [0, 50, 100, 70, 20, 80, 10, 40, 90, 30, 60] 
new HashSet<Integer>(8, 0.5) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 20, 80, 90, 30, 60] 
new HashSet<Integer>(32, 1.0) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 80, 20, 90, 60, 30] 
new HashSet<Integer>(64, 1.0) adding 0,10, ... 100 => [0, 70, 10, 80, 20, 90, 30, 100, 40, 50, 60] 
new HashSet<Integer>(128, 1.0) adding 0,10, ... 100 => [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]