W
std::unordered_map funktioniert mit Hashtables. Dabei wird ein Algorithmus benutzt, um z.B. aus einem std::string eine Hash-Zahl zu generieren. Diese Hash-Zahl ist für diesen String immer gleich. Es kann auch vorkommen, dass mehrere Strings die gleiche Hash-Zahl besitzen. Optimalerweise sollten aber ähnliche Strings wie "1", "2", "3" oder "abcd", "dcba" nicht die gleiche Hash-Zahl besitzen. Je nach Anzahl der Elemente wird dann ein Array erstellt, das die Paare am Index ihrer Hash-Zahl speichert. Falls mehrere Keys den gleichen Hash-Wert besitzen, so werden sie in einer Liste aneinandergehängt und müssen dann noch abgesucht werden. Wird die Anzahl der Elemente vergrößert, so wird ggf. auch die Hash-Tabelle vergrößert, damit die Elementlisten nicht zu lange werden.
Da diese map einen Algorithmus für den Key-Typ benötigt, funktioniert sie logischerweise nicht mit jedem Typ. Am üblichsten ist aber die Benutzung mit Strings.
So bietet sich bei einigermaßen effektiver Nutzung eine Komplexität von O(1), d.h. die std::unordered_map braucht immer gleich lange zur Suche eines Elements, egal, wie viele Elemente darin enthalten sind.
