Vor sechs Jahren verbrannte ich mehrere Tage damit, herauszufinden, wo mein perfekt deterministischer Rahmen regellos reagierte. Nachdem ich das gesamte Framework akribisch verfolgt habe, um sicherzustellen, dass alle die gleiche Instanz von Random verwenden, jagte ich dann weiter mit Einzelschrittcode. Es war ein sich sehr wiederholender iterativer Selbst-Aufruf-Code. Schlimmer noch, der verdammte Effekt würde erst nach einer großen Anzahl von Iterationen auftauchen. Und nach +6 Stunden war ich endlich am Ende, als ich eine Zeile im Javadoc für HashSet.iterator () entdeckte, die darauf hinweist, dass es nicht die Reihenfolge garantiert, in der Elemente zurückgegeben werden. Ich ging dann durch meine gesamte Codebasis und ersetzte alle Instanzen von HashSet durch LinkedHashSet. Und niedrig-und-siehe, mein Rahmen entsprang dem deterministischen Leben! ARGH!
Ich habe gerade diesen FREAKIN-Effekt noch einmal erlebt (zumindest waren es diesmal nur 3 Stunden). Aus welchem Grund auch immer, ich habe das kleine Detail übersehen, dass HashMap den gleichen Weg für sein SchlüsselSet () hat.
Hier ist ein SO-Thread zu diesem Thema, obwohl die Diskussion meine Frage nie ganz beantwortet: Iterationsreihenfolge von HashSet
Ich bin also neugierig, warum das passieren könnte. Zu beiden Zeiten hatte ich eine riesige single - threaded Java - Anwendung, die genau denselben Instanziierungs - / Einfügeraum mit genau den gleichen JVM - Parametern (mehrere Läufe von derselben Batch - Datei) auf demselben Computer durchforstete, wobei fast nichts anderes lief JVM, so dass sich HashSet und HashMap nach einer enormen Anzahl von Iterationen unvorhersehbar verhalten würden (nicht inkonsistent, da das Javadoc sagt, dass es nicht von der Reihenfolge abhängt)?
Irgendwelche Ideen dazu entweder aus dem Quellcode (Implementierung dieser Klassen in java.util) oder aus Ihrem Wissen über die JVM (vielleicht beeinflussen einige GC, wo interne Java-Klassen bei der Zuweisung interner Speicherräume Speicher ungleich Null bekommen)?
Ich habe das schon vorher getroffen, wo die Reihenfolge nicht wichtig war, aber die Ergebnisse beeinflusst hat.
Die Multi-Thread-Natur von Java bedeutet, dass wiederholte Läufe mit genau den gleichen Eingaben durch geringfügige Zeitunterschiede beeinflusst werden können, zum Beispiel, wie lange es dauert, einen neuen Speicherblock zuzuordnen, für den manchmal ein Paging benötigt wird Festplatte den vorherigen Inhalt, und zu anderen Zeiten wird das nicht benötigt. Ein anderer Thread, der diese Seite nicht verwendet, kann fortfahren, und Sie könnten mit einer anderen Reihenfolge der Objekterstellung enden, wenn Systemobjekte berücksichtigt werden.
Dies kann das Object.hashCode() -Ergebnis für das äquivalente Objekt in verschiedenen Läufen der JVM beeinflussen.
Für mich habe ich beschlossen, den kleinen Overhead der Verwendung von LinkedHashMap hinzuzufügen, um die Ergebnisse der Tests, die ich ausgeführt habe, reproduzieren zu können.
Es gibt einen Kompromiss. Wenn Sie den Zugriff auf Elemente mit konstanter Zeit O (1) amortisieren möchten, stützen sich die bisherigen Techniken auf ein zufälliges Schema wie Hashing. Wenn Sie einen geordneten Zugriff auf Elemente wünschen, bietet der beste technische Kompromiss nur die Leistung O (ln (n)) . Für Ihren Fall ist das vielleicht egal, aber der Unterschied zwischen der konstanten Zeit und der logarithmischen Zeit macht einen sehr großen Unterschied, der bereits mit relativ kleinen Strukturen beginnt.
Also, ja, Sie können sich den Code ansehen und ihn sorgfältig untersuchen, aber es läuft auf eine ziemlich praktische theoretische Tatsache hinaus. Jetzt ist eine gute Zeit, um den Staub von dieser Kopie von Cormen (oder Map oder Set , um geordnete Listen von Schlüsseln / Mitgliedern zurückzugeben. Dafür sind sie nicht da. Maps und Sets-Strukturen sind nicht genau wie die zugrundeliegenden mathematischen Konzepte angeordnet und bieten unterschiedliche Performance. Das Ziel dieser Datenstrukturen (wie @thejh hervorhebt) ist eine effiziente amortisierte insert , contains und get time, ohne die Reihenfolge zu verwalten. Sie können prüfen, wie eine Hash-Datenstruktur verwaltet wird, um zu erfahren, welche Kompromisse bestehen. Werfen Sie einen Blick auf die Wikipedia-Einträge auf Hash-Funktionen und Hash Tables (ironisch, beachten Sie, dass der Wiki-Eintrag für" ungeordnete Karte "zu letzterem umleitet) oder ein Informatik / Datenstruktur-Text.
Denken Sie daran: Verlassen Sie sich nicht auf Eigenschaften von ADTs (und speziell Sammlungen) wie Bestellung, Unveränderbarkeit, Thread-Sicherheit oder irgendetwas anderes, es sei denn, Sie betrachten genau, was der Vertrag ist. Beachten Sie, dass der Javadoc für Map deutlich sagt:
Die Reihenfolge einer Karte ist definiert als Reihenfolge, in der die Iteratoren auf der Die Ansichten der Kartensammlung geben ihre zurück Elemente. Einige Kartenimplementierungen, Wie die TreeMap-Klasse, mache spezifisch Garantien hinsichtlich ihrer Bestellung; Andere, wie die Klasse HashMap, nicht.
Und Set.iterator() hat Ähnliches:
Gibt einen Iterator über die Elemente zurück in diesem Satz. Die Elemente werden zurückgegeben in keiner bestimmten Reihenfolge (außer dies set ist eine Instanz einer Klasse, die bietet eine Garantie).
Wenn Sie eine geordnete Ansicht von diesen wünschen, verwenden Sie einen der folgenden Ansätze:
Set ist, möchten Sie vielleicht wirklich ein SortedSet wie ein TreeSet
TreeMap , die entweder eine natürliche Sortierung erlaubt von Schlüsseln oder eine bestimmte Reihenfolge über Comparator
SortedSet von Schlüsseln sowie ein Map , die in der amortisierten Zeit besser abschneiden. Map.keySet() (oder nur das Set , an dem Sie interessiert sind) und fügen Sie es in ein SortedSet wie TreeSet , entweder mit der natürlichen Reihenfolge oder einem bestimmten Comparator . Map.Entry<K,V> mit Map.entrySet().iterator() , nachdem es sortiert wurde. Z.B. for (final Map.Entry<K,V> entry : new TreeSet(map.entrySet())) { } , um effizient auf Schlüssel und Werte zuzugreifen. Arrays.sort() , das ein anderes Leistungsprofil (Raum und Zeit) hat. Wenn Sie sich die Quelle für juHashSet und juHashMap , sie sind auf GrepCode verfügbar. Beachten Sie, dass ein HashSet nur Zucker für eine HashMap ist. Warum nicht immer Verwenden Sie die sortierten Versionen? Nun, wie ich oben andeutete, unterscheidet sich die Leistung und das ist in einigen Anwendungen wichtig. Siehe verwandte SO Frage hier Sie können auch einige konkrete Leistungszahlen hier unten sehen ( Ich habe nicht genau hingeschaut, um zu überprüfen, ob diese korrekt sind, aber sie bestätigen meinen Standpunkt, also werde ich den Link munter weiterleiten: -)
Ссылка () sagt:
So viel wie vernünftigerweise praktisch ist, die von der Klasse definierte Methode hashCode Objekt gibt eindeutige ganze Zahlen zurück für verschiedene Objekte. (Das ist typischerweise durch Konvertierung implementiert die interne Adresse des Objekts in eine ganze Zahl, aber das Implementierungstechnik ist nicht wird von der JavaTM-Programmierung benötigt Sprache.)
Vielleicht ändert sich die interne Adresse?
Dies bedeutet auch, dass Sie es wahrscheinlich beheben können, ohne Geschwindigkeit aufzugeben, indem Sie Ihre eigene hashCode() -Methode für alles schreiben, was als Schlüssel dienen soll.
Sie sollten NIEMALS von der Reihenfolge einer Hash-Map abhängig sein.
Wenn Sie eine Karte mit einer deterministischen Reihenfolge wünschen, empfehle ich Ihnen eine SortedMap / SortedSet wie TreeMap / TreeSet oder LinkedHashMap / LinkedHashSet. Ich benutze die später oft, nicht weil das Programm die Reihenfolge benötigt, sondern weil es einfacher zu lesen / debuggt den Zustand der Karte zu lesen. Wenn Sie also einen Schlüssel hinzufügen, geht er jedes Mal bis zum Ende.
Sie können zwei HashMap / HashSet mit denselben Elementen erstellen, erhalten aber je nach Kapazität der Sammlung unterschiedliche Befehle. Es ist möglich, feine Unterschiede in der Art und Weise, wie Ihr Code ausgeführt wird, auszulösen, um eine andere endgültige Bucket-Größe und damit eine andere Reihenfolge auszulösen.
z.B.
%Vor%druckt
%Vor%Hier haben Sie HashSet (s) mit denselben Werten, die in der gleichen Reihenfolge hinzugefügt wurden, was zu verschiedenen Iterator-Aufträgen führt. Sie spielen möglicherweise nicht mit dem Konstruktor, aber Ihre Anwendung könnte indirekt eine andere Bucket-Größe verursachen.