Verarbeitet HashSet den Sortierjob intern?

Question

Meine Set ist manchmal sortiert, und manchmal nicht. Hier

ist das Beispiel:

public class SetOfInteger { 
    public static void main(String[] args) { 
     Random rand = new Random(47); 
     Set<Integer> intset = new HashSet<>(); 
     for (int i = 0; i < 10; i++) { 
      int j = rand.nextInt(30); 
      System.out.print(j + " "); 
      intset.add(j); 
     } 
     System.out.println(); 
     System.out.println(intset); 
    } 
} 

Das Ergebnis zeigt, dass die set nicht sortiert ist.

8 5 13 11 1 29 28 20 12 7 
[1, 20, 5, 7, 8, 11, 12, 29, 28, 13] 

Wenn ich die Kündigung Ausdruck i < 20 in der for-Anweisung zu ändern, zeigt das Ergebnis, dass die set sortiert werden.

8 5 13 11 1 29 28 20 12 7 18 18 21 19 29 28 28 1 20 28 
[1, 5, 7, 8, 11, 12, 13, 19, 18, 21, 20, 29, 28] 

Es ist so seltsam, oder? Ich weiß einfach nicht, wie ich es erklären soll, und ich brauche Hilfe, vielen Dank.

Answer 1

Sie müssen es manuell sortieren, da es keine Garantie gibt, dass das hashset sortiert wird. Wenn Sie möchten, können Sie auch TreeSet verwenden, die die Funktionalität, die Sie wollen liefern, aber wenn Sie HashSet trotzdem versuchen, dies verwenden möchten:

Set intset = new HashSet(); 
List sortedIntList = new ArrayList(intset); 
Collections.sort(sortedIntList); 

Answer 2

Ein HashSet nicht sortierter Iteration nicht garantiert, aber unter ganz bestimmten Umständen seine internen Daten Struktur kann wie ein bucket sort handeln.

Speziell für Ganzzahlschlüssel im Bereich [0,65535] und eine Tabellengröße, die größer als der größte Schlüssel ist, ist der Index des Buckets, in dem ein Schlüssel gespeichert ist, gleich dem Schlüssel selbst und seit dem Iterator Iteriert in der Eimerreihenfolge, es gibt die Elemente in sortierter Reihenfolge aus.

Answer 3

Interessante Frage. Set verwendet array of linked list, um seine Elemente zu speichern. hashCode() wird verwendet, um die Position (indirekt) des Objekts zu finden, das im Set gespeichert werden soll.

Falls zwei Objekte an derselben Position gespeichert werden müssen, wird das Objekt im nächsten Slot der verknüpften Liste an dieser Position gespeichert.

Die Größe des Arrays ist dynamisch und berechnet die Laufzeit entsprechend der Anzahl der darin enthaltenen Objekte. Es ist nicht sicher, aber ich nehme an, Sie sehen Ihre Zahlen sortiert, weil das Set die Größe erhöht haben könnte. Der hashCode() ist abhängig von dem Zahlenwert und wäre somit sequentiell berechnet worden. Da die Größe des zugrunde liegenden Arrays mit der Größe der Schleife zugenommen hätte. Es hätte keine Kollisionen gegeben und die Ausgabe ist sortiert.

Aber noch möchte ich betonen, dass meine Antwort zu keinem Missverständnis führt. HashSet keine Sortierung der Elemente garantiert

Answer 4

Die Iterationsreihenfolge eines HashSet nicht definiert ist, die einzige Garantie ist, dass es konsistent ist: die gleichen Sequenzen erzeugen Iterieren über eine HashSet, die nicht verändert wurde.

Intern, wie ein Kommentator sagte, verwendet die Klasse die HashCode-Methode jedes Elements, um sie in einer bestimmten Anzahl von Bins zu speichern. Wenn zum Beispiel 20 Bins verwendet werden, könnte es als Bin-Index sein. Jeder Bin kann mehrere Elemente in einer Liste haben, die dann durch die equals-Methode unterschieden werden. Selbst wenn der Hashwert einer Ganzzahl sein int-Wert ist, muss die Reihenfolge daher nicht die natürliche Ganzzahlreihenfolge sein.

Darüber hinaus überwacht das Gerät seinen Lastfaktor beim Einfügen und Entfernen von Elementen; Berücksichtigen Sie den Anteil der freien Bins, die maximale Größe der Bunkerliste, die durchschnittliche Anzahl der Elemente pro Bunker, was auch immer. Wenn es für angemessen erachtet wird, führt es eine Wiederaufbereitung durch, was bedeutet, dass die Anzahl der Behälter geändert wird, die zum Speichern der Elemente verwendet werden, so dass sich ihr Behälterindex ändert, weil sich das n in o.hashCode() % n ändert. Jedes Element wird an seinem neuen Ort "neu gemischt" (dies ist eine kostspielige Operation), was die unterschiedliche Reihenfolge erklärt, die Sie nach dem Hinzufügen weiterer Elemente sehen.

Answer 5

Ihre Frage weist darauf hin, dass die Artikelreihenfolge ändert, wenn das Set größer wird. Sie können jedoch nicht darauf zählen, dass die Reihenfolge beibehalten wird. Eine Set hat eine Garantie: es gibt nur eine von jeder Art von Element. Es gibt andere Set Objekte, die weitere Garantien bieten, aber eine einfache HashSet bietet keine Garantie für die Bestellung.

Die Nachbestellung, die Sie sehen, ist einfach eine interne Umgruppierung, da das HashSet intern gespeichert wird. In einer sehr vereinfachten Weise hat das HashSet eine bestimmte Anzahl von "Slots", um Werte zu speichern, die normalerweise eine ungerade Zahl, wenn nicht auch eine Primzahl sind. Die Hashcodes von getHashCode() werden verwendet, um das Objekt einem Slot zuzuordnen. Wenn Sie eine Hash-Code-Kollision haben, verwendet das HashSet den Gleichheitsoperator equals(), um festzustellen, ob die Objekte tatsächlich eindeutig sind.

Wenn Sie Elemente zu einem HashSet mehrere Dinge hinzufügen passieren:

• Objekte in ihre internen Steckplatz
  • Der Hash-Code wird dann weiter finden gehasht zugewiesen, welche Steckplatz es in
  • gehört Wenn es gibt eine Slot-Kollision, dann testen wir auf Gleichheit. Wenn es das gleiche Objekt ist, die wir es verwerfen, wenn wir es nicht zu einer Liste in diesem Slot hinzufügen
• Wenn die Anzahl der Objekte, die Anzahl der Schlitze überschreiten, die HashSet Bedürfnisse, um die Größe selbst
  • Es schafft ein größerer Satz von Schlitzen, die in der Regel noch ein ungeradeer oder Primzahl ist
  • die vorhandenen Elemente in die neue Kollektion von Slots neu zugeordnet werden - das ist, wo Ordnung

ändern

Die Quintessenz ist, dass wenn die Objekte sich magisch sortiert haben, dies keine Implementierung ist, auf die Sie sich verlassen können, wenn Sie nicht eine TreeSet verwenden, die den eingestellten Elementen eine Sortierreihenfolge auferlegt.

Answer 6

Es gibt einige gute Antworten, aber keine versucht zu erklären, was genau in dieser speziellen Situation passiert, also werde ich meine Antwort darauf beschränken, anstatt eine weitere Erklärung hinzuzufügen, wie das HashSet funktioniert. Ich nehme dieses Verständnis als selbstverständlich an.

Die default constructor of HashSet erstellt einen Satz mit einer Kapazität von 16 und einem Auslastungsfaktor von 0,75. Das bedeutet, dass es 16 Fächer gibt, und diese Kapazität wird erhöht, wenn Sie 16 * 0,75 = 12 einzigartige Elemente einfügen.

Deshalb werden im ersten Fall die Zahlen nach ihrem Rest sortiert, wenn sie durch 16 geteilt werden: Der Satz begann mit einer Tabellengröße von 16 und "hashte" jedes Element zu einem Fach, indem x % 16 genommen wurde. Dann, als es 12 Elemente gab, wuchs der Tisch und führte eine Neuaufbereitung durch (siehe Javier Martins Antwort, wenn das nicht klar ist), wahrscheinlich wuchs die Tabelle auf 32. (Ich konnte nur Informationen darüber finden, wie sie in the java 6 doc wächst Anzahl der Buckets wird "ungefähr" verdoppelt, was auch immer das bedeutet.) Das gab jeder Integer-Zahl unter 30 eine eigene Bin. Wenn also die Menge über jede Bin in der Reihenfolge iterierte, iterierte sie die Zahlen der Reihe nach. Wenn Sie Zahlen unter 64 eingeben, werden Sie wahrscheinlich feststellen, dass Sie 32 * 0,75 = 24 Elemente einfügen müssen, bevor die Iteration sortiert erscheint.

Beachten Sie auch, dass diese Art der Zuweisung von Bins nicht garantiert Verhalten ist. HashSets in anderen Java-Versionen/Implementierungen könnten etwas komplizierterer mit den hashCode() Werten der Objekte sein, als einfach einen Rest zu nehmen. (Wie von ruakh und flauschig in den Kommentaren - danke!)