Hashtabellen

Inhaltsverzeichnis[Anzeigen]

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, das 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.

geordneteAssoziativeArrays

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 Container.

  • 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.

UngeordnetesAssoziativesArray

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;

}
 
Ein typischer Fall von copy and paste. Die Zeilen 11- 21 bzw. 26 - 36 unterscheiden sich nur dadurch, dass im ersten Fall ein std::map, im zweiten Fall ein std::unordered_map zum Einsatz kommt. Daher beschreibe ich nur den zweiten Codeblock. In Zeile 27 wird die std::unordered_map mit Hilfe der Initialisiererliste initialisiert. Anschließend setze ich den Wert für den Schlüssel "Ritchie" neu und geben dessen assoziierten Wert in der nächsten Zeile wieder aus. In der Range-basierten For-Schleife (Zeile 30 und 33) gebe ich die Schlüssel/Werte Paare aus, wobei p.first den ersten, p.second den zweiten Wert des Paares adressiert. Mit um.clear() lässt sich der ungeordnete assoziative Container in Zeile 34 leeren und mit um.size() seine Größe ermitteln.
Ein scharfer Blick auf die Ausgabe des Programms offenbart doch einen kleinen Unterschied der beiden Container.
mapHashCompare

 

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

Die acht Variationen

Um Systematik in die acht Variationen von assoziativen Container zu bringen, starte ich mit den klassischen, geordneten assoziativen Containers. 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.

geordnetVersusUngeordnetAssoziativesArray

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.

 


 

 

 

 

 

 

 

title page smalltitle page small 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.

 

Kommentare   

0 #1 best hosting 2016-11-03 20:33
As the admin of this web page is working, no doubt very
shortly it will be well-known, due to its quality contents.
Zitieren

Kommentar schreiben


Modernes C++

Abonniere den Newsletter

Inklusive zwei Artikel meines Buchs
Introduction und Multithreading

Beiträge-Archiv

Sourcecode

Neuste Kommentare