Ist die unordered_map wirklich ungeordnet?

Question

Ich bin sehr verwirrt durch den Namen 'unordered_map'. Der Name deutet darauf hin, dass die Schlüssel überhaupt nicht bestellt sind. Aber ich dachte immer, dass sie nach ihrem Hash-Wert geordnet sind. Oder ist das falsch (weil der Name bedeutet, dass sie nicht bestellt sind)?

Oder anders ausgedrückt: Ist die

typedef map<K, V, HashComp<K> > HashMap; 

mit

template<typename T> 
struct HashComp { 
    bool operator<(const T& v1, const T& v2) const { 
     return hash<T>()(v1) < hash<T>()(v2); 
    } 
}; 

die gleichen wie

typedef unordered_map<K, V> HashMap; 

? (OK, nicht genau, wird STL hier beschweren, denn es kann Schlüssel k1, k2 und weder k1 < k2 noch k2 < k1 sind Sie müßten multimap verwenden und die gleiche Prüfung überschreiben..)

Oder auch anders: Kann ich bei der Iteration davon ausgehen, dass die Schlüsselliste nach ihrem Hashwert sortiert ist?

Answer 1

Als Antwort auf Ihre bearbeitete Frage sind keine dieser beiden Snippets überhaupt gleichwertig. std::map speichert Knoten in einer Baumstruktur, unordered_map speichert sie in einer Hashtabelle *.

Die Schlüssel werden nicht in der Reihenfolge ihres "Hash-Werts" gespeichert, da sie nicht in beliebiger Reihenfolge gespeichert sind. Sie werden stattdessen in "Buckets" gespeichert, wobei jeder Bucket einer Reihe von Hash-Werten entspricht. Grundsätzlich geht die Umsetzung wie folgt aus:

function add_value(object key, object value) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     buckets[bucket_index] = new linked_list(); 
    } 
    buckets[bucket_index].add(new key_value(key, value)); 
} 

function get_value(object key) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     return null; 
    } 

    foreach(key_value kv in buckets[bucket_index]) { 
     if (kv.key == key) { 
      return kv.value; 
     } 
    } 
} 

Offensichtlich das ist eine ernste Vereinfachung und reale Umsetzung wäre viel weiter fortgeschritten (zum Beispiel die Unterstützung der buckets Array Ändern der Größe, vielleicht eine Baumstruktur anstelle von verketteten Liste für den Eimern und so weiter), aber das sollte eine Vorstellung davon geben, wie man die Werte nicht in einer bestimmten Reihenfolge zurückbekommt. Weitere Informationen finden Sie unter wikipedia.

* Technisch gesehen ist die interne Implementierung von std::map und unordered_map ist die Implementierung definiert, aber der Standard erfordert bestimmte Big-O Komplexität für Operationen, den dieser internen Implementierungen

Answer 2

Wenn Sie eine Analogie wünschen, schauen Sie sich das RDBMS Ihrer Wahl an.

Wenn Sie beim Ausführen einer Abfrage keine ORDER BY-Klausel angeben, werden die Ergebnisse "ungeordnet" zurückgegeben - dh in welcher Reihenfolge sich die Datenbank anfühlt. Die Bestellung ist nicht spezifiziert, und das System ist frei, sie zu "bestellen", wie es will, um die beste Leistung zu erhalten.

Answer 3

Sie haben Recht, unordered_map ist eigentlich Hash-Reihenfolge. Beachten Sie, dass die meisten aktuellen Implementierungen (vor TR1) es hash_map nennen.

Das IBM C/C++ Kompilierer documentation bemerkt, dass Wenn Sie eine optimale Hash-Funktion haben, die Anzahl der Operationen während der Lookup, Insertion, und das Entfernen eines beliebigen Elements hängt nicht von der Anzahl der Elemente in der Sequenz durchgeführt, , so bedeutet dies, dass die Reihenfolge nicht so ungeordnet ist ...

Nun, was bedeutet es, dass es Hash ist bestellt? Da ein Hash nicht vorhersehbar sein sollte, können Sie per Definition keine Annahmen über die Reihenfolge der Elemente in der Map treffen. Aus diesem Grund wurde es in TR1 umbenannt: Der alte Name schlug einen Auftrag vor. Jetzt wissen wir, dass eine Bestellung tatsächlich verwendet wird, aber Sie können sie ignorieren, da sie unvorhersehbar ist.

Answer 4

"Ungeordnet" bedeutet nicht, dass es irgendwo in der Implementierung keine lineare Sequenz gibt. Es bedeutet "Sie können nichts über die Reihenfolge dieser Elemente annehmen".

Zum Beispiel nehmen Leute oft an, dass Einträge aus einer Hash-Map in derselben Reihenfolge kommen, in der sie eingefügt wurden. Aber das tun sie nicht, weil die Einträge ungeordnet sind.

Wie "nach ihrem Hash-Wert geordnet": Hash-Werte werden im Allgemeinen aus dem vollen Bereich von Ganzzahlen genommen, aber Hash-Karten haben nicht 2 ** 32 Steckplätze in ihnen. Der Bereich des Hash-Wertes wird auf die Anzahl der Slots reduziert, indem die Anzahl der Slots modulo genommen wird. Wenn Sie einer Hash-Map Einträge hinzufügen, ändert sich die Größe möglicherweise, um die neuen Werte zu berücksichtigen. Dies kann dazu führen, dass alle vorherigen Einträge neu platziert werden und ihre Reihenfolge geändert wird.

In einer ungeordneten Datenstruktur können Sie nicht von der Reihenfolge der Einträge ausgehen.

Answer 5

Wie der Name unordered_map andeutet, wird vom C++ 0x-Standard keine Reihenfolge angegeben. Die Reihenfolge einer ungeordneten Map hängt davon ab, was für die tatsächliche Implementierung geeignet ist.