C++ unordered_map Kollision Behandlung, Größe ändern und rehash

Question

Ich habe nicht den C++ - Standard gelesen, aber das ist, wie ich finde, dass die unordered_map von C++ funktionieren soll.

• Weisen Sie einen Speicherblock im Heap zu.
• Mit jeder PUT-Anfrage, das Objekt Hash und es zu einem Raum Karte Adressierung in diesem Speicher
• Während dieses Prozess Griff Kollision Handhabung über Verkettungs oder öffnen ..

Ich bin ziemlich überrascht, dass ich kann nicht finde viel darüber heraus, wie der Speicher von unsordered_map gehandhabt wird. Gibt es eine bestimmte anfängliche Speichergröße, die unordered_map zuweist? Was passiert, wenn wir sagen, dass wir 50 Int-Speicher zugewiesen haben und wir schließlich 5000 Integer eingefügt haben?

Dies wird viele Kollisionen sein, so glaube ich, sollte es wie ein Re-Hashing und Größenanpassung Algorithmus sein, um die Anzahl der Kollisionen nach einem bestimmten Grad der Kollisionsschwelle zu verringern. Da sie der Klasse explizit als Memberfunktionen zur Verfügung gestellt werden, nehme ich an, dass sie auch intern verwendet werden. Gibt es einen solchen Mechanismus?

Answer 1

Mit jeder PUT-Anfrage, das Objekt Hash und es in einen Raum in diesem Speicher Karte

Leider ist dies nicht ganz richtig. Sie beziehen sich auf eine offene Adresse oder geschlossen Hashing Datenstruktur, die nicht wie unordered_map angegeben ist.

Jede unordered_map Implementierung speichert eine verknüpfte Liste mit externen Knoten im Array von Buckets. Das bedeutet, dass das Einfügen eines Elements immer mindestens einmal (der neue Knoten) zugewiesen wird, wenn nicht zweimal (Größe des Bucket-Arrays, dann des neuen Knotens).

Nein, das ist überhaupt nicht die effizienteste Möglichkeit, eine Hash-Map für die häufigsten Anwendungen zu implementieren. Leider erfordert ein kleines "Versehen" in der Spezifikation unordered_map dieses Verhalten nur. Das erforderliche Verhalten besteht darin, dass Iteratoren für Elemente beim Einfügen oder Löschen anderer Elemente gültig bleiben müssen. Da das Bucket-Array durch das Einfügen wachsen (neu zuweisen) kann, ist es im Allgemeinen nicht möglich, dass ein Iterator direkt in das Bucket-Array zeigt und die Stabilitätsgarantien erfüllt.

unordered_map ist eine bessere Datenstruktur, wenn Sie teure Kopien als Schlüssel oder Wert speichern. Das macht Sinn, wenn man bedenkt, dass das allgemeine Design von Boosts Pre-Move-Semantics Design abgelöst wurde.

Chandler Carruth (Google) erwähnt dieses Problem in seinem CppCon '14 Gespräch "Efficiency with Algorithms, Performance with Data Structures".

Answer 2

std :: unordered_map enthält einen Ladefaktor, mit dem die Größe der internen Buckets verwaltet wird. std :: unordered_map verwendet diesen ungeraden Faktor, um die Größe des Containers irgendwo zwischen 0,0 und 1,0 zu halten. Dies verringert die Wahrscheinlichkeit einer Kollision in einem Bucket. Danach bin ich mir nicht sicher, ob sie auf lineares Sondieren innerhalb eines Buckets zurückgreifen, in dem eine Kollision gefunden wurde, aber ich würde dies annehmen.