Hashtabellen

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.

Klassisches C++ bietet bereits vier verschiedene assoziative Container an. Mit C++11 kommen vier neue dazu. Hier gilt es erst mal Ordnung zu schaffen.

Assoziatives Container

Allen assoziativen Containers ist gemein, dass sie einen Schlüssel mit einem Wert assoziieren, so dass der Wert über seinen Schlüssel referenziert werden kann. Die klassischen assoziativen Container werden geordnete assoziative Container, die neuen assoziativen Container ungeordnete assoziative Container genannt.

Geordnete assoziative Container

Der feine Unterschied ist, dass die Schlüssel der klassischen assoziativen Container geordnet sind. Per Default kommt ein Kleiner-Relation (<) zum Einsatz, so dass die Container aufsteigend sortiert sind.

Diese Ordnung besitzt interessante Auswirkungen auf die geordneten assoziativen Container.

• Die Schlüssel müssen eine Ordnungsrelation unterstützen.
• Assoziative Container sind typischerweise in balancierten, binären Bäumen implementiert.
• Die Zugriffszeit auf die Schlüssel und damit auf deren assoziierten Werte ist logarithmisch.

Das am häufigsten verwendete geordnete assoziative Array ist die std::map:

std::map<int,std::string> int2String{ {3,"three"},{2,"two"},{1,"one"},{5,"five"},{6,"six"},{4,"four"},{7,"seven"} };

Der balancierte, binäre Suchbaum kann die folgende Struktur besitzen.

Ungeordnete assoziative Container

Die zentrale Idee der ungeodneten assoziativen Arrays ist es, dass ihre Schlüssel mit Hilfe der Haskfunktion auf einen Bucket abgebildet werden. In diesem Bucket befinden sich die Schlüssel/Wert Paare.

Noch ein paar Begriffe, bevor ich weiter auf die Charakteristiken der ungeordneten assoziativen Arrays eingehe.

• Hashwert: Der Wert, den die Anwendung der Hashfunktion auf den Schlüssel ergibt, wird gerne als Hashwert bezeichnet.
• Kollision: Werden verschiedene Schlüssel durch die Hashfunktion auf denselben Hashwert abgebildet, entsteht eine Kollision. Damit muss das ungeordnete assoziative Array umgehen können.

Die Hashfunktion besitzt sehr interessante Auswirkungen auf ungeordneten assoziativen Containern.

• Der Schlüssel muss auf Gleichheit vergleichbar sein, um mit Kollisionen umgehen zu können.
• Der Hashwert eines Schlüssels muss zur Verfügung stehen.
• Die Ausführungszeit der Hashfunktion ist konstant. Das heißt, dass der Zugriff auf die Schlüssel eines ungeordneten assoziativen Containers auch konstant ist. Der Einfachheit halber, ignoriere ich bei meiner Schlüssfolgerung Kollisionen.

 Entsprechend zu std::map, das der am häufigst verwendete geordnete assoziative Container ist, ist std::unordered_map das häufigst verwendete ungeordnete assoziative Container:

std::unordered_map<std::string,int> str2Int{ {"Grimm",491634333356},{"Grimm-Jaud",49160123335}, {"Schmidt",4913333318},{"Huber",490001326} };

Die Graphik soll Abbildung der Schlüssel mit Hilfe der Haskfunktion auf ihre Buckets dar.

Die Gemeinsamkeiten

Die Namensähnlichkeit von std::map und std::unordered_map ist kein Zufall. Beide bieten ein sehr ähnliches Interfaces an. Das zeigt das folgende Codebeispiel.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// mapHashCompare.cpp

#include <iostream>
#include <map>
#include <unordered_map>

int main(){

  std::cout << std::endl;

  std::cout << "C++ map: " << std::endl;
  std::map<std::string,int> m { {"Dijkstra",1972},{"Scott",1976} };
  m["Ritchie"] = 1983;
  std::cout << "    m[Ritchie]: " <<  m["Ritchie"] << "\n    ";
  for(auto p : m) std::cout << '{' << p.first << ',' << p.second << '}';
  m.erase("Scott");
  std::cout << "\n    ";
  for(auto p : m) std::cout << '{' << p.first << ',' << p.second << '}';
  m.clear();
  std::cout << std::endl;
  std::cout << "    m.size(): " << m.size() << std::endl;


  std::cout << std::endl;

  std::cout << "C++11 unordered_map: " << std::endl;
  std::unordered_map<std::string,int> um { {"Dijkstra",1972},{"Scott",1976} };
  um["Ritchie"] = 1983;
  std::cout << "    um[Ritchie]: " <<  um["Ritchie"] << "\n    ";
  for(auto p : um) std::cout << '{' << p.first << ',' << p.second << '}';
  um.erase("Scott");
  std::cout << "\n    ";
  for(auto p : um) std::cout << '{' << p.first << ',' << p.second << '}';
  um.clear();
  std::cout << std::endl;
  std::cout << "    um.size(): " << um.size() << std::endl;

  std::cout << std::endl;

}

Die Schlüssel des std::map sind geordnet und damit auch die Paare. Kein Wunder. Denn darin unterscheidet sich genau das sichtbare Verhalten der geordneten von den ungeordneten Container.

Die acht Variationen

Um Systematik in die acht Variationen von assoziativen Containern zu bringen, starte ich mit den klassischen, geordneten assoziativen Container. Diese Systematik lässt sich dann leicht auf die ungeordneten assoziativen Container erweitern.

Die Beantwortung zweier Fragen ist der Schlüssel zur Systematik der geordneten assoziativen Container:

• Ist dem Schlüssel ein Wert zugeordnet?
• Darf ein Schlüssel öfters als einmal vorkommen?

Aus der Beantwortung dieser zwei Fragen ergeben sich die vier verschiedene geordnete assoziative Container std::set, std::multiset, std::map und std::multimap.

Natürlich können die zwei Fragen auch auf die ungeordneten assoziativen Container angewandt werden. In diesem Fall resultieren die Container std::unordered_set, std::unordered_multiset, std::unordered_map und std::unordered_multimap.

Nun gilt es nur noch, die Systematik nieder zuschreiben. Enthält einer Container den Namensbestandteil

• map, so ist dem Schlüssel ein Wert zugeordnet.
• multi, so kann er mehrere gleiche Schlüssel besitzen.
• unordered, so sind seine Schlüssel nicht sortiert.

Der Analogieschluss geht noch weiter. Unterscheiden sich zwei Container nur durch den Namensbestandteil unordered, so bieten sie ein ähnliches Interface an. Für die std::map und std::unordered_map hat dies ja bereits das Listing mapHashCompare.cpp gezeigt.

Die Tabelle bringt nochmals die ganze Systematik auf den Punkt. Diese Systematik schließt auch ein, dass die Zugriffszeit für die geordneten Variationen logarithmisch, für die ungeordneten Variationen der assoziativen Container konstant ist.

Wie geht's weiter?

Eigentlich wollte ich in diesem Artikel die Performanzunterschiede beim Zugriff auf geordnete bzw. ungeordnete Container vergleichen. Ich habe aber deutlich unterschätzt, wie viel Schreibaufwand notwendig ist, diese Systematik für die Variationen der assoziativen Container zu entwickeln. Damit ist klar, über was ich im nächsten Artikel schreibe werde.

Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.