wake-up-neo.com

Wie bestellt Java Artikel in einer HashMap oder einer HashTable?

Ich habe mich gefragt, wie Java Elemente in der Map (HashMap oder Hashtable) bestellt, wenn sie hinzugefügt werden. Sind die Schlüssel nach Hashcode, Speicherreferenz oder nach Prioritätszuordnung sortiert ...?

Ich habe bemerkt, dass gleiche Paare in der Map nicht immer in derselben Reihenfolge sind

59
Eyad Salah

Java.util.HashMap ist ungeordnet; Sie können und sollten nichts anderes als das annehmen.

Diese Klasse übernimmt keine Garantie für die Reihenfolge der Karte. Insbesondere kann nicht garantiert werden, dass die Bestellung im Zeitablauf konstant bleibt. 

Java.util.LinkedHashMap verwendet die Reihenfolge der Einfügung.

Diese Implementierung unterscheidet sich von HashMap dadurch, dass sie eine doppelt verknüpfte Liste führt, die alle ihre Einträge durchläuft. Diese verknüpfte Liste definiert die Iterationsreihenfolge. Dies ist normalerweise die Reihenfolge, in der Schlüssel in die Map eingefügt wurden (Einfügungsreihenfolge). 

Java.util.TreeMap , a SortedMap verwendet entweder die natürliche oder die benutzerdefinierte Reihenfolge der Schlüssel.

Die Karte wird nach der natürlichen Reihenfolge ihrer Schlüssel oder nach einer Comparator sortiert, die zum Zeitpunkt der Kartenerstellung bereitgestellt wird, abhängig davon, welcher Konstruktor verwendet wird. 

118

Erstens: HashMap spezifisch nicht eine stabile und/oder definierte Reihenfolge bereitstellen. Alles, was Sie beobachten, ist einfach ein Implementierungsdetail und Sie dürfen nicht sind in irgendeiner Weise davon abhängig.

Da es manchmal nützlich ist, den Grund für die scheinbar zufällige Reihenfolge zu kennen, ist hier die Grundidee:

Ein HashMap hat eine Anzahl von Buckets (als Array implementiert), in denen Einträge gespeichert werden können.

Wenn ein Element zur Karte hinzugefügt wird, wird es einem Bucket basierend auf einem Wert zugewiesen, der aus seinem hashCode und der Bucket-Größe des HashMap abgeleitet wird. (Beachten Sie, dass es möglich ist, dass der Bucket bereits belegt ist, was als Kollision bezeichnet wird. Dies wird ordnungsgemäß und korrekt gehandhabt, aber ich werde diese Behandlung für die Beschreibung ignorieren, da sie das Konzept nicht ändert.).

Die wahrgenommene Reihenfolge der Entires (z. B. durch Iteration über Map zurückgegeben) hängt von der Reihenfolge der Einträge in diesen Buckets ab.

Bei jeder erneuten Aufbereitung der Größe (weil die Karte den Schwellenwert für den Füllgrad überschritten hat) ändert sich die Anzahl der Schaufeln. Dies bedeutet, dass sich die Position jedes Elements ändern kann, da die Schaufelposition auch von der Anzahl der Schaufeln abgeleitet wird.

17
Joachim Sauer

HashMap sortiert überhaupt nicht. Für eine Karte, die nach Schlüsselwerten sortiert wird, sollten Sie stattdessen TreeMap verwenden.

Aus den JavaDocs für TreeMap:

Rot-Schwarz-Baum-basierte Implementierung von die SortedMap-Schnittstelle. Diese Klasse garantiert, dass sich die Karte in .__ befindet. aufsteigende Reihenfolge der Schlüssel, sortiert nach zur natürlichen Reihenfolge des Schlüssels Klasse (siehe Vergleichbar) oder durch die Komparator zum Zeitpunkt der Erstellung, abhängig davon, welcher Konstruktor .__ ist. gebraucht.

Aus der Dokumentation von HashMap:

Diese Klasse übernimmt keine Garantie für die Reihenfolge der Karte; im Speziellen, es garantiert nicht, dass die Bestellung wird im Laufe der Zeit konstant bleiben.

5
Behrang

Eine Map ist keine geordnete Datenstruktur. Sie sollten sich nicht darauf verlassen, dass Einträge in einer HashMap in einer bestimmten Reihenfolge sind. Einige Map-Implementierungen wie LinkedHashMap und TreeMap garantieren eine bestimmte Reihenfolge, HashMap jedoch nicht.

Wenn Sie wirklich wissen möchten, was intern geschieht, suchen Sie nach dem Quellcode von HashMap - Sie finden ihn in src.Zip , der sich in Ihrem JDK-Installationsverzeichnis befinden sollte.

Ein HashMap hat eine Reihe von "Buckets", in denen er seine Einträge speichert. In welchem ​​Bucket ein Eintrag gespeichert ist, wird durch den Hashcode des Schlüssels des Eintrags bestimmt. Die Reihenfolge, in der Sie die Einträge in HashMap sehen, hängt von den Hash-Codes der Schlüssel ab. Schreiben Sie jedoch keine Programme, die sich darauf verlassen, dass Einträge in einer bestimmten Reihenfolge in HashMap vorhanden sind. Die Implementierung kann sich in einer zukünftigen Version von Java ändern und Ihr Programm würde dann nicht mehr funktionieren.

1
Jesper

hashmap hat eine nicht definierte Reihenfolge der Elemente

1
Robar

Es gibt keine definierte Reihenfolge in einer Hashtabelle. Schlüssel werden basierend auf dem Hashcode in einem Slot platziert, aber selbst das ist kein trivialer Order-by-Hash-Code.

0
Marcelo Cantos

HashMap speichert die Werte mit dem eindeutigen Hashwert, der mit einem Teil des Schlüssels generiert wurde. Dieser Hashwert entspricht der Adresse, an der er gespeichert werden soll. So sorgt es für einen Zugriff O (1).

LinkedHashmap hingegen behält die Reihenfolge bei, die Sie der Karte hinzugefügt haben.

0
Vaishak Suresh