Ich bin heute über den "ominösen" float loadFactor Parameter im Hashtable Constructor beim Fremdcode debuggen gestoßen. Wer sich nicht mit theoretischen Verständnis belasten will, nicht das "letzte" bischen Performance braucht und auch noch nie eine "System.InvalidOperationException: Hashtable insert failed. Load factor too high" Exception gesehen hat, dem sei gesagt, laß den loadFactor in Ruhe. Der ist Standardmäßig auf 0.72 eingestellt und völlig ausreichend normalerweise.
Wer jetzt noch dabei ist, der muss sich nun darauf gefasst machen das ich recht weit ausholen muß. Nach etwas Recherche in Wesner Moise's legendärem .NET undocumented blog, ging mir ein Licht auf, was dass denn nun genau ist.
Theorie
Die Grundidee der Hashtable ist, simpel gesagt, mittels des Keys den man besitzt direkt zum Eintrag in einer Liste springen zu können. Kein suchen und langes vergleichen, man hat den Key, berechnet daraus eine Art "Offset" und hat damit den Speicherplatz lokalisiert wo der zugehörige Value abgelegt ist. Die Berechnung dieses "Offsets" übernimmt die Hashfunktion in unserer Hashtable.
Z.b. wir haben eine Mitarbeiternummer für 50 Mitarbeiter, um jeden Eindeutig zu identifizieren würde es reichen aus den letzten 2 Nummern der Mitarbeiternummer einen eindeutigen Hashcode zu berechnen, ergo reicht uns ein vorinitialisiertes leeres Array von 100 Einträgen (nennen wir dieses Array Buckets) und je nach Hashcode kann man dann zum berechneten Index springen (egal ob 0 oder 99). Nun kommt aber Mitarbeiter 51, und dessen letzten 2 Ziffern aus der Mitarbeiternummer stimmen ganz zufällig mit der eines anderen überein. Ein insert schlägt fehl (Hashtable insert failed), unsere Hashfunktion ist nicht ausreichend und es gibt das, was man eine Collision in der Hashtable nennt.
Um diese Collision zu vermeiden kann man nun z.B. die Hashfunktion neu implementieren, nur haben wir dann das dilema, um so komplizierter und einzigartiger dieser Hashcode berechnet wird, um so langsamer wird jeder Zugriff auf unsere Hashtable. Ein anderer Ansatz geht vom Load Factor der Hashtable aus. haben wir unsere Buckets aus dem obigen Beispiel mit der Größe 100 und 50 Einträge drin, dann beträgt der Load Factor 50/100 = 0.5. Das heißt unsere Buckets sind zu 50% gefüllt, die Wahrscheinlichkeit das eine Collision stattfindet ist 0.5. Um so niedriger wir diesen Faktor drücken können, um so unwahrscheinlicher ist eine Collision, aber auch um so mehr freien Speicherplatz verpulvern wir sprichwörtlich.
Aber selbst wenn wir die Wahrscheinlichkeit drücken, sie bleibt bestehen, daher benötigt man eine Technik die im Falle der Collision eine Gegenstrategie fährt. Buckets machen aus unserem 1-dimensionalen Array ein 2-dimensionales Array. Ist der Index belegt, wird einfach in der 2. Dimension am nächsten freien Index unser Kollidierter Hash abgelegt. Praktisch auffüllen wie bei einem Eimer (Bucket). Die Nachteile sind offentsichtlich, das eingangs erwähnte "Vergleichen", dass man vermeiden wollte ist plötzlich wieder da, auch noch eine Collisiondetektions und Handlingsroutine.
Ergo man kann es also auf den Punkt bringen, mehr Speicherplatz für mehr Performance in der Hashtable. Vermeidet man Kollisionen, vermeidet man unnötige Operationszeiten. Sowohl beim schreiben und vor allem auch beim auslesen.
.NET Praxis
Nach dem theoretischen Ausflug zurück zu .NET. Ganz so simpel wie das theoretische Modell ist es nicht ganz in der Praxis.
Buckets sind in der .NET Hashtable ein Array von Arrays, um genau zu sein ein Bucket[], wobei jedes Bucket drei Werte hält: hash_coll (int), key (object) und val (object):
Füge ich in die obige Hashtable den key "a" ein, berechnet die Hashfunktion einen Wert dazu und ordnet diesem Wert einen Index in DIESEM(!) Bucket Array zu (andere Bucket Array Größe, andere Zuordnungsweise). Daher wird in dieser Hashtable (100, 1.0f), der key "a" immer an Position 49 im Bucket Array landen (.NET 3.5). Hätte ich nun einen key zur Hand, dessen Hashcode zufällig identisch wäre, würde eine Collision eintreten und das Collision Handling tritt ein. Dazu wird der Hashkey neu berechnet und als "Offset" zu der Kollision Index Position aufgerechnet. Es wird also nicht wie im klassischen Bucket in die 2. Dimension gegangen, sondern, flapsig gesagt, flach "weitergesprungen" (was uns den Compare aus der Theorie von oben erspart!).
Das wiederrum erklärt warum das Bucket Array hier deutlich größer ist als der vorgegebene Initialwert von 100. Und jetzt kommen wir damit auch endlich zum loadFactor und dessen Auswirkung. Ich habe den Wert von 1.0f übergeben als loadFactor. Dies wird mit dem Initialwert 0.72 multipliziert. D.h. würde ich 0.5f übergeben, wäre der interne loadFactor 0.36:
Die Berechnung der Bucket Anzahl ist jetzt eher nebensächlich, grob gesagt die Initialgröße dividiert durch den loadFactor und dann die nächste Primzahl (aus statistischen Gründen für maximale Effektivität). Wesner Moise läßt sich in seinem Blog detailierter darüber aus, wen es genauer interessiert (siehe Verlinkung oben).
Fazit
D.h. zusammenfassend:
um so kleiner der loadFactor...
-> um so größer das Bucket Array
-> um so mehr Speicherverbrauch
-> um so weniger Collisionen
-> um so weniger Operationen
-> um so höhere Performance in Abhängigkeit von der steigenden Anzahl der keys (was wirklich durchaus in einem signifikanten Rahmen liegt, ...probierts aus)
Keine Kommentare:
Kommentar veröffentlichen