Buckets, Kapazität und Ladefaktor

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.

Um das große Bild nicht zu verlieren, will ich es gerne explizit betonen. Auch wenn ich in diesem Artikel std::unordered_set als Repräsentant für einen ungeordneten assoziativen Container verwende, gelten die Aussagen dieses Artikels für alle ungeordneten assoziaitiven Container. Mit deren Systematik habe ich mich ausführlich bereits im Artikel Hashtabellen auseinandergesetzt. 

Rehashing

In welchen Bucket ein Schlüssel landet, darüber entscheidet die Hashfunktion. Da die Hashfunktion den potentiell unendlich großen Schlüsselraum auf eine endliche Anzahl von Buckets reduziert, kommt es natürlich vor, dass verschiedene Schlüssel im gleichen Bucket landen. Dieser Vorgang wird als Kollision bezeichnet. Im Bucket selber werden die Schlüssel typischerweise als verlinkte Liste gespeichert. Daraus lässt es sich schön ableiten, wie schnell der Zugriff auf einen Schlüssel in einem ungeordneten assoziativen Container ist. Zum einen ist die Anwendung der Hashfunktion eine konstante Operation, zum anderen ist das Suchen in der verlinkten Liste eine lineare Operation. Das Ziel der Hashfunktion muss es daher sein, möglichst wenig Kollisionen zu erzeugen.

Die Anzahl der Buckets wird als Kapazität, die durchschnittliche Anzahl der Elemente je Bucket als Ladefaktor bezeichnet. Die C++-Laufzeit erzeugt in der Regel neue Buckets dann, wenn der Ladefaktor 1 übersteigt. Dieser Vorgang wird Rehashing genannt und kann auch explizit angefordert werden, indem die Kapazität eines ungeodneten assoziativen Containers durch seine Methode rehash(val) auf einen höheren Wert gesetzt wird.Um die Begrifflichkeit besser auseinander zu halten, fasse ich sie nochmals zusammen.

• Kapazität: Anzahl de Buckets
• Ladefaktor: Durchschnittliche Anzahl der Elemente (Schlüssel) je Bucket
• Rehashing: Erzeugen neuer Buckets 

Diese Kenngrößen lassen sich in C++ sowohl bestimmen als auch verändern.

 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

// rehash.cpp

#include <iostream>
#include <random>
#include <unordered_set>

void getInfo(const std::unordered_set<int>& hash){
  std::cout << "hash.bucket_count(): " << hash.bucket_count() << std::endl;
  std::cout << "hash.load_factor(): " << hash.load_factor() << std::endl;
}

void fillHash(std::unordered_set<int>& h,int n){
  std::random_device seed;
  // default generator
  std::mt19937 engine(seed());
  // get random numbers 0 - 1000
  std::uniform_int_distribution<> uniformDist(0,1000);

  for ( int i=1; i<= n; ++i){
    h.insert(uniformDist(engine));
  }
}

int main(){

  std::cout << std::endl;

  std::unordered_set<int> hash;
  std::cout << "hash.max_load_factor(): " << hash.max_load_factor() << std::endl;

  std::cout << std::endl;

  getInfo(hash);

  std::cout << std::endl;

  // only to be sure
  hash.insert(500);
  // get the bucket of 500
  std::cout << "hash.bucket(500): " << hash.bucket(500) << std::endl;

  std::cout << std::endl;

  // add 100 elements
  fillHash(hash,100);
  getInfo(hash);

  std::cout << std::endl;

  // at least 500 buckets
  std::cout << "hash.rehash(500): " << std::endl;
  hash.rehash(500);

  std::cout << std::endl;

  getInfo(hash);

  std::cout << std::endl;

  // get the bucket of 500
  std::cout << "hash.bucket(500): " << hash.bucket(500) << std::endl;

  std::cout << std::endl;

}

Zuerst zu den beiden Hilfsfunktionen getInfo (Zeile 7 - 10) und fillHash (Zeile 12 - 22). Die Funktion getInfo gibt für eine std::unordered_set die Anzahl seiner Buckets und den Ladefaktor aus. Die Funktion fillHash füllt seinen ungeordneten assoziativen Container mit n zufällig erzeugen Ganzzahlen.

Interessant ist es, die Ausgabe des Programms unter Linux mit der unter Windows zu vergleichen. Unter Linux kam in bekannter Manier der GCC-, unter Windows der cl.exe-Compiler zum Einsatz. Beide Programme habe ich ohne Optimierungsflag übersetzt.

Zuerst interessiert mich der maximale Ladefaktor (Zeile 29) des leeren Containers. Wird der maximale Ladefaktor überschritten, findet ein Rehashing des ungeordneten assoziativen Containers statt. Der maximale Ladefaktor ist sowohl unter Linux wie auch unter Windows1. Interessanterweise legt der GCC auf Verdacht 11 Buckets, der cl.exe nur 8 Buckets an. Der Ladefaktor ist natürlich auf beiden Plattformen 0. Wird der Schlüssel 500 (Zeile 38) in die Hashtabelle geschoben, landet er auf Linux im Bucket 5, auf Windows im Bucket 6. In Zeile 45 füge ich 100 Elemente zur Hashtabelle hinzu. Während Linux danach 97 Buckets besitzt, besitzt Windows 512 Buckets. Das Linux nur 97 Buckets besitzt, ist dadurch zu erklären, dass unter Linux durch Zufall einige gleiche Schlüssel erzeugt wurden. Während Linux mit seinem Ladefaktor dadurch schon nahe an 1 ist, kann unter Windows die Hashtabelle noch sehr viele Elemente aufnehmen, bevor es mit einem Ladefaktor von 1 automatisch zum Rehashen kommt. Das Rehashen stoße ich explizit für Linux in Zeile 51 an, in dem ich fordere, dass die Hashtabelle mindestens 500 Buckets besitzen soll. Damit bestätigt sich meine Aussage. Während Linux die neuen Buckets erzeugt und auch die Schlüssel neu verteilt, ist das Rehashing unter Windows nicht notwendig, da die Hashtabelle bereits 512 Buckets besitzt. Sowohl unter Linux als auch unter Windows ist der Schlüssel 500 (Zeile 61) letztendlich in einem anderen Bucket wie zu Beginn des Progamms (Zeile 40).

Aus einer einzelnen Beobachtung ist es fragwürdig eine Schlussfolgerung zu ziehen. Es scheint aber, dass die Linux-Laufzeit die minimalen Speicherforderungen der Hashtabelle höher gewichtet als die Windows-Laufzeit. Windows legt bereits mit 101 Schlüsseln 512 Buckets (Zeile 45) an. Damit spart sich Windows das teure Rehashen und erkauft sich dies mit einer deutlichen überdimensionierten Hashtabelle. Beim Rehashen werden gegebenenfalls nicht nur neue Buckets angelegt, sondern auch die bestehenden Schlüssel neu verteilt.

Daumenregel

Falls du weißt, wie groß dein ungeordneter assoziativer Container wird, solltest du mit einer vernünftigen Anzahl an Buckets starten. Damit kannst du das oftmalige teure Rehashing vermeiden. Rehashing bedeutet immer Speicherallokation und die Neuverteilung der Schlüssel. Dies Frage ist natürlich, was heißt vernünftig. Meine Daumenregel ist es, mit einer Anzahl an Buckets zu starten, die der Anzahl an Schlüsseln entspricht. Damit ist der Ladefaktor nahe an 1.

Gerade zu dieser Daumenregel bin ich auf Anmerkungen gespannt, die ich gegebenenfalls wieder in diesen Artikel einfliesen lasse.

Wie geht's weiter?

POD's steht für Plain Old Data. Dies sind Datentypen, die ein C-Standardlayout besitzen. Damit können sie direkt mit den effizienten C-Funktionen wie memcpy, memmove, memcmp oder memset manipuliert werden. C++11 ermöglicht es, das selbst Klassen PODs sind. Welche Bedingungen dazu ein Klasse erfüllen muss, davor erzählt der nächste Artikel.

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.