Ist der unordered_map wirklich ungeordnete?

StackOverflow https://stackoverflow.com/questions/3176621

  •  02-10-2019
  •  | 
  •  

Frage

Ich bin mit dem Namen ‚unordered_map‘ sehr verwirrt. Der Name lässt vermuten, dass die Schlüssel überhaupt nicht bestellt. Aber ich habe immer gedacht, sie von ihrem Hash-Wert geordnet. Oder ist das falsch (weil der Name schon sagt, dass sie nicht bestellt werden)?

oder es anders zu sagen: Ist das 

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);
    }
};

das gleiche wie 

typedef unordered_map<K, V> HashMap;

? (OK, nicht genau, wird STL hier beschweren, weil es Schlüssel sein kann, k1, k2 und weder k1 multimap brauchen würde, und überschreiben die gleich-Check).

Oder auch anders: Wenn ich durchlaufen sie, kann ich davon ausgehen, dass der Schlüssel-Liste über ihre Hash-Wert ist bestellt

War es hilfreich?

Lösung

In Antwort auf Ihre Frage bearbeitete, nicht diese beiden Schnipsel sind überhaupt nicht gleichwertig. std::map speichern Knoten in einer Baumstruktur, unordered_map speichert sie in einer Hash-Tabelle *.

Die Schlüssel werden in der Reihenfolge ihres „Hash-Wertes“ nicht gespeichert, weil sie nicht gespeichert sind beliebige Reihenfolge bei allen . Sie werden stattdessen in „Kübel“ gespeichert, wobei jeder Eimer mit 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;
       }
   }
}

Natürlich, das ist eine ernsthafte Vereinfachung und reale Umsetzung wäre viel weiter fortgeschritten (zum Beispiel der Unterstützung des buckets Array Ändern der Größe, vielleicht eine Baumstruktur anstelle von verketteten Liste für den Eimer, und so weiter), aber das sollte eine Idee geben, wie Sie die Werte in einer bestimmten Reihenfolge nicht zurückerhalten können. Siehe wikipedia für weitere Informationen.


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

Andere Tipps

„Ungeordnete“ bedeutet nicht, dass es keine lineare Abfolge irgendwo in der Umsetzung ist. Es bedeutet „Sie nichts über die Reihenfolge dieser Elemente übernehmen kann.“

Zum Beispiel sei angenommen Leute oft, dass Einträge kommen aus einer Hash-Karte in der gleichen Reihenfolge, wie sie in gestellt wurden. Aber sie tun es nicht, weil die Einträge ungeordnet sind.

Wie bei „durch ihren Hash-Wert bestellt“: Hash-Werte werden in der Regel aus dem vollen Bereich von ganzen Zahlen genommen, aber Hash-Karten haben keine 2 ** 32 Slots in ihnen. Die Reichweite des Hash-Wert wird auf die Anzahl der Slots reduziert werden, indem es die Anzahl der Slots Modulo. Ferner ist, wie Sie Einträge in eine Hash-Karte hinzufügen, könnte es Größe ändern, um die neuen Werte zu berücksichtigen. Dies kann alle vorherigen Einträge verursachen Wieder platziert sein, ihre Reihenfolge ändern.

In einer ungeordneten Datenstruktur, Sie können nichts über die Reihenfolge der Einträge übernehmen.

Wie der Name schon sagt unordered_map, wird keine Bestellung durch den C ++ 0x-Standard spezifiziert. Eine scheinbare Ordnung der unordered_map wird davon abhängig sein, was auch immer ist bequem für die tatsächliche Umsetzung.

Wenn Sie eine Analogie wollen, Blick auf die RDBMS Ihrer Wahl.

Wenn Sie keine ORDER BY-Klausel angeben, wenn eine Abfrage durchgeführt wird, werden die Ergebnisse „ungeordnete“ zurückgegeben - das heißt, in welcher Reihenfolge die Datenbank sich anfühlt. Die Reihenfolge ist nicht festgelegt, und das System ist frei „um“ sie jedoch mag es, um die beste Leistung zu erhalten.

Sie haben Recht, ist unordered_map tatsächlich Hash bestellt. Beachten Sie, dass die meisten aktuellen Implementierungen (pre TR1) nennen es hash_map.

Die IBM C / C ++ Compiler

Nicht verbunden mit StackOverflow
scroll top