Die Hashfunktion bildet die potentiell unendliche Anzahl von Schlüssel auf eine endliche Anzahl von Buckets ab. Welche Strategie dabei die C++-Laufzeit verfolgt und wie diese angepasst werden kann, zeigt dieser Artikel.

Der entscheidende Grund für die konstante Zugriffszeit der ungeordneten assoziativen Container sind deren Hashfunktionen. In bekannter Manier bietet C++ viele Stellschrauben für Hashfunktionen an. Einerseits bringt C++ einen reichen Satz an Hashfunktionen mit, andererseits lassen sich auch eigene Hashfunktionen verwenden. Selbst die Verteilung der Hashwerte auf die Buckets kann angepasst werden.

Bevor ich das Interface der Hashtabellen - offiziell ungeordnete assoziative Container genannt- genauer betrachte, will ich ihre Performanz mit der der geordneten assoziativen Container vergleichen. Die idealen Kandidaten dafür sind die std::unordered_map und ihr geordneter Pendant die std::map, da sie von allen assoziativen Containern am häufigsten zum Einsatz kommen.

Hashtabellen wurden in C++ lange vermisst. Versprechen sie doch konstante Zugriffszeit auf ihre Elemente. C++11 besitzt jetzt Hashtabellen in vier Variationen. Offiziell heißen sie ungeordnete assoziative Container, inoffiziell werden sie auch Dictionaries oder einfach nur assoziative Arrays genannt.

Type Traits offenbaren bei genauen Hinblick ein großes Optimierungspotential. Da die Type-Traits Bibliothek es erlaubt, im ersten Schritt den Code zu Compilezeit zu analysieren, kann dieser im zweiten Schritt optimiert werden. Wie ist das möglich? Abhängig vom Typ einer Variable wird eine besondere, schnelle Variante eines Algorithmus gewählt.

constexpr Funktionen sind Funktionen, die zur Compilezeit ausgeführt werden können. Hört sich erst mal nicht so spannend an. Ist es aber, denn durch constexpr Funktionen können Berechnungen auf die Compilezeit verschoben werden. Damit stehen deren Ergebnisse als Konstanten im ROM zur Laufzeit zur Verfügung. Darüber hinaus sind constexpr Funktionen implizit inline.

Wird eine Variable als constexpr definiert, kann sie zur Compilezeit evaluiert werden. Dies gilt nicht nur für Variablen von fundamentalen Datentypen, sondern auch für Instanzen von benutzerdefinierten Datentypen (Objekte). Insbesondere bei Objekten gibt es deutliche Einschränkungen, damit diese zur Compilezeit evaluiert werden können.