Ich frage mich, wie Java Aufträge Elemente in den Map (HashMap oder Hashtable), wenn sie hinzugefügt werden. Sind die Schlüssel durch den Hashcode, die Speicherreferenz oder durch Zuordnungsvorrang geordnet?Wie bestellt Java Elemente in einer HashMap oder HashTable?
Es ist, weil ich gleiche Paare in der Map sind nicht immer in der gleichen Reihenfolge
java.util.HashMap ungeordnet ist; Sie können und sollten darüber hinaus nichts annehmen.
Diese Klasse gibt keine Garantie für die Reihenfolge der Karten; insbesondere garantiert es nicht, dass der Auftrag über die Zeit konstant bleibt.
java.util.LinkedHashMap verwendet Einfügereihenfolge.
Diese Implementierung unterscheidet sich von
HashMapdarin, dass sie eine doppelt verknüpfte Liste verwaltet, die alle Einträge durchläuft. Diese verkettete Liste definiert die Iterationsreihenfolge, bei der es sich normalerweise um die Reihenfolge handelt, in der Schlüssel in die Karte eingefügt wurden (Einfügereihenfolge).
java.util.TreeMap, ein SortedMap, verwendet entweder natürliche oder benutzerdefinierte Reihenfolge der Schlüssel.
Die Karte wird entsprechend der natürlichen Ordnung der Schlüssel sortiert werden, oder durch eine
Comparatorbei Map Erstellungszeit vorgesehen ist, je nachdem, welche Konstruktor verwendet wird.
HashMap sortiert nicht überhaupt bemerkt haben. Für eine Karte, die nach Schlüsselwerten sortiert, sollten Sie stattdessen verwenden.
Aus der JavaDocs für TreeMap:
Rot-Schwarz-Baum-basierte Implementierung von die SortedMap Schnittstelle. Diese Klasse garantiert, dass die Karte in aufsteigend Schlüssel, um sein, sortierte nach die natürlichen Ordnung für die Klasse Schlüssel (siehe Vergleich) oder durch den Komparator zum Zeitpunkt der Erstellung zur Verfügung gestellt, je nachdem, welchen Konstruktor verwendet .
Aus der Dokumentation von HashMap:
Diese Klasse keine Garantie für die Reihenfolge der Karte macht; Insbesondere garantiert nicht, dass der Auftrag im Laufe der Zeit konstant bleibt.
Ich habe nie gesagt, dass ich sie sortiert haben wollte. Ich frage mich, ob Java tut –
A Map ist nicht eine geordnete Datenstruktur - Sie können nicht auf Einträge in einem HashMap verlassen sollten in einer bestimmten Reihenfolge zu sein. Einige Map Implementierungen wie LinkedHashMap und TreeMap tun, um eine gewisse Ordnung garantieren, aber HashMap nicht.
Wenn Sie wirklich wissen wollen, was intern passiert, Nachschlagen, den Quellcode HashMap - Sie kann es in src.zip finden können, die in Ihrem JDK-Installationsverzeichnis sein sollte.
A HashMap hat eine Anzahl von "Buckets", in dem es seine Einträge speichert. Welcher Bucket ein Eintrag ist, wird durch den Hash-Code 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. Aber schreiben Sie keine Programme, die darauf angewiesen sind, dass Einträge in einer bestimmten Reihenfolge in einer HashMap sind - die Implementierung könnte sich in einer zukünftigen Version von Java ändern und Ihr Programm würde dann nicht mehr funktionieren.
Es gibt keine definierte Reihenfolge in einer Hash-Tabelle. Die Schlüssel werden basierend auf dem Hash-Code in einem Slot platziert, aber selbst das ist kein trivialer Hash-Reihenfolge-Code.
hashmap hat einen nicht definierten Reihenfolge der Elemente
Zu allererst: HashMap speziell bietet keine stabile und/oder die Bestellung definiert. Also alles, was Sie beobachten, ist einfach ein Implementierungsdetail und Sie müssen davon in keiner Weise abhängen.
Da es manchmal nützlich ist der Grund für die scheinbar zufällige Reihenfolge zu kennen, hier ist die Grundidee:
A HashMap hat Anzahl der Schaufeln (als Array implementiert), in der Einträge zu speichern.
Wenn ein Element zur Map hinzugefügt wird, wird es einem Bucket basierend auf einem Wert zugeordnet, der von seinem und der Bucket-Größe des HashMap abgeleitet wird. (Beachten Sie, dass der Bucket möglicherweise bereits besetzt 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 empfundene Ordnung des entires (wie durch Iterieren über die Map zurückgegeben werden), hängt von der Reihenfolge der Einträge in den Eimern.
Immer wenn die Größe aktualisiert wird (weil die Karte ihren Schwellenwert überschritten hat), ändert sich die Anzahl der Buckets, was bedeutet, dass sich die Position jedes Elements ändern kann, da die Bucket-Position ebenfalls aus der Anzahl der Buckets abgeleitet wird .
HashMap speichert die Werte mit dem eindeutigen Hash-Wert, der mit einem Teil des Schlüssels erzeugt wurde. Dieser Hash-Wert wird der Adresse zugeordnet, an der er gespeichert werden soll. So stellt es einen Zugang O (1) sicher.
LinkedHashmap hingegen behält die Reihenfolge bei, in der Sie der Karte hinzugefügt haben.
HashMap kann O (1) nicht garantieren. Es versucht, es am besten zu machen, aber im schlimmsten Fall ist es O (n) mit n = Anzahl der Einträge (auch wenn das unwahrscheinlich ist (oder Ihre hashCode-Methode ist wirklich schlecht implementiert)) – Hardcoded
Einverstanden, dass es nicht immer zur Verfügung stellt eine konstante Zeit Leistung, aber mehr als oft nicht versucht es. http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html –
noch eine Hashmap folgt die gleiche vorhersagbare Reihenfolge jedes Mal ... warum? –
@pop stack HashMap garantiert nicht die Bestellung. In Stephen Cs Antwort unter http://stackoverflow.com/questions/2144776/order-of-values-retrieved-from-a-hashmap finden Sie Details darüber, wie und warum sich das ändern könnte. –
Diese Art von Antwort ist großartig! Ein Spickzettel wäre toll, um die Unterschiede zwischen Map, List, Set in Java aufzulisten! –