Hashfunktionen

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 aber konkret auf die Hashfunktionen eingehe, muss ich erst die Deklaration der ungeordneten assoziativen Container genauer betrachten, um nicht das große Bild zu verlieren. Exemplarisch betrachte ich den Repräsentanten der ungeordneten assoziativen Container, den Container std::unordered_map.

std::unordered_map

Die Deklaration der Hashtabelle std::unordered_map bringt sehr viele interessante Details an Licht.

template<
    class Key,
    class Val,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, Val> >
> class unordered_map;

Nun zu den einzelnen Template-Parametern. Das std::unordered_map assoziiert einen Schlüssel (Key) mit einem Wert (Val). Die übrigen drei Template-Parameter werden per Default von dem Typ des Schlüssels und dem des Wertes abgeleitet. Dies gilt für die Hashfunktion (Hash), die Gleichheitsfunktion (KeyEqual) und den Speicherbeschaffer (Allocator). Damit lässt sich einfach ein std::unordered_map char2int instanziieren.

std::unordered_map<char,int> char2int;

Nun wird es aber interessanter. Per Default kommt die Hashfunktion std::hash<Key> und die Gleichheitsfunktion std::equal_to<Key> zum Einsatz. Somit lässt sich ein std::unordered_map instanziieren, das eine spezielle Hash- bzw. Gleichheitsfunktion besitzt. Doch wozu ist die Gleichheitsfunktion notwendig? Die Hashfunktion bildet den Schlüssel auf den Hashwert ab. Der Hashwert landet im Bucket. Dabei kann es zu Kollisionen kommen. Das heißt, verschiedene Schlüssel können im gleichen Bucket landen. Mit dieser Kollision, bei der Schlüssel auf einfachere Hashwerte abgebildet werden, muss das std::unordered_map umgehen können. Genau hierzu benötigt der assoziative Container die Gleichheitsfunktion. Nur noch der Vollständigkeit halber. Mit dem Speicherbeschaffer (Allocator) lässt sich die Speicherstrategie des Containers anpassen.

Welche Bedingungen müssen der Schlüssel und der Wert eines ungeordneten assoziativen Containers erfüllen?

Der Schlüssel muss

• mit dem Gleichheitskriterium vergleichbar sein,
• als Hashwert zur Verfügung stehen,
• kopier- und verschiebbar sein.

Der Wert muss

• default-konstruierbar sein,
• kopier- und verschiebbar sein.

Die Hashfunktion

Eine Hashfunktion ist dann gut, wenn sie bei ihrer Abbildung von den Schlüsseln auf deren Hashwerte möglichst wenig Kollisionen erzeugt und ihre Hashwerte gleichmäßig auf die Buckets verteilt. Da die Ausführungszeit der Hashfunktion konstant ist, ist dies im optimalen Fall auch der Zugriff auf die Elemente des Containers.

Die Hashfunktion

• ist für fundamentale Datentypen wie Wahrheitswerte, Ganzzahlen und Fließkommazahlen vordefiniert,
• gibt es für die Datentypen std::string und std::wstring,
• erzeugt für einen C-String const char* einen Hashwert der Zeigeradresse,
• kann für eigene Datentypen definiert werden.

Wende ich nun die Theorie des bisherigen Artikels für einen eigenen Datentyp an, den ich als Schlüssel eines ungeordneten Containers verwenden will, gelten für diesen Datentyp zwei Bedingungen. Er benötigt eine Hashfunktion und muss auf Gleichheit vergleichbar sein.

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

// hashFunction.cpp

#include <iostream>
#include <ostream>
#include <unordered_map>

struct MyInt{
  MyInt(int v):val(v){}
  bool operator== (const MyInt& other) const {
    return val == other.val;
  }
  int val;
};

struct MyHash{
  std::size_t operator()(MyInt m) const {
    std::hash<int> hashVal;
    return hashVal(m.val);
  }
};

struct MyAbsHash{
  std::size_t operator()(MyInt m) const {
    std::hash<int> hashVal;
    return hashVal(abs(m.val));
  }
};

struct MyEq{
  bool operator() (const MyInt& l, const MyInt& r) const {
    return abs(l.val) ==  abs(r.val);
  }
};

std::ostream& operator << (std::ostream& strm, const MyInt& myIn){
  strm << "MyInt(" << myIn.val << ")";
  return strm;
}

int main(){

  std::cout << std::endl;

  std::hash<int> hashVal;

  // a few hash values
  for ( int i= -2; i <= 1 ; ++i){
    std::cout << "hashVal(" << i << "): " << hashVal(i) << std::endl;
  }

  std::cout << std::endl;

  typedef std::unordered_map<MyInt,int,MyHash> MyIntMap;

  std::cout << "MyIntMap: ";
  MyIntMap myMap{{MyInt(-2),-2},{MyInt(-1),-1},{MyInt(0),0},{MyInt(1),1}};

  for(auto m : myMap) std::cout << '{' << m.first << ',' << m.second << '}';

  std::cout << std::endl << std::endl;

  typedef std::unordered_map<MyInt,int,MyAbsHash,MyEq> MyAbsMap;
  std::cout << "MyAbsMap: ";
  MyAbsMap myAbsMap{{MyInt(-2),-2},{MyInt(-1),-1},{MyInt(0),0},{MyInt(1),1}};

  for(auto m : myAbsMap) std::cout << '{' << m.first << ',' << m.second << '}';

  std::cout << std::endl << std::endl;

  std::cout << "myAbsMap[MyInt(-2)]: " << myAbsMap[MyInt(-2)] << std::endl;
  std::cout << "myAbsMap[MyInt(2)]: " << myAbsMap[MyInt(2)] << std::endl;
  std::cout << "myAbsMap[MyInt(3)]: " << myAbsMap[MyInt(3)] << std::endl;

  std::cout << std::endl;

}

Meine Analyse des Programms beginnt in der main-Funktion. Am einfachsten ist es natürlich, die Ausgabe des Programms in Augenwinkel zu behalten. In Zeile 44 erzeugt ich die Hashfunktion hasVal und verwende diese anschließend, um die Hashwerte in Zeile 48 auszugeben. hasVal gibt Hashwerte vom Typ std::size_t zurück. std::size_t repräsentiert eine ausreichend große vorzeichenlose Ganzzahl. MyIntMap in Zeile 53 erklärt einen neuen Namen für einen Typ. Dieser verwendet MyInt (Zeile 7 - 13) als Schlüssel. Nun benötigt mein Datentyp noch eine Hashfunktion und eine Gleichheitsfunktion. Als Hashfunktion verwendet MyInt die Klasse MyHash (Zeile 15 - 20). Sie greift auf die Implementierung der Hashfunktion für den Datentyp int zurück. Die Gleichheitsfunktion habe ich bereits für den Datentyp überladen. 

Eine andere Strategie verfolgt der Datentyp MyAbsMap. Seinem Namen folgend, bildet MyAbsMap den Hashwert basierend auf dem absoluten Wert der ganzen Zahl (Zeile 25). Als Gleichheitsfunktion kommt die Klasse MyEq mit dem überladenen Klammeroperator zum Einsatz. MyEq interessiert sich konsequenterweise nur für den absoluten Wert der Ganzzahl. Die Ausgabe zeigt schön, das die Hashfunktion von MyAbsMap für verschiedene Schlüssel den gleichen Hashwert zurückgibt. Das Ergebnis ist, das der Wert für die Schlüssel MyInt(-2) (Zeile 70) als auch MyInt(2) (Zeile 71) identisch -2 ist. Dies gilt, obwohl ich MyAbsMap nicht mit einem Paar (MyInt(2),2) in Zeile 64 initialisiert habe.

Wie geht's weiter?

Eine Kleinigkeit fehlt noch um Hashfunktionen besser zu verstehen. Die Hashfunktion bildet den Schlüssel auf den Hashwert ab. Dabei ordnet sie einem Schlüssel vom Typ int oder auch std::string seinen Bucket zu. Wie ist das sinnvoll möglich? Stehen doch der potentiell unendlichen Anzahl von Schüsseln eines Datentyps eine endliche Anzahl von Buckets gegenüber. Das ist aber nicht die einzige Frage. Wieviel Elemente landen in dem Bucket? Oder anders augedrückt. Wie häufig kommen Kollisionen vor? Fragen, auf die der nächste Artikel Antworten gibt. 

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.