am 23. Oktober 2009
Beim heutigen akademischen Tag geht es um eine Datenstruktur, die jeder PHP-Entwickler bereits verwendet hat – wahrscheinlich ohne es zu wissen: Hashmaps. Wem dieser Begriff nichts sagt: Assoziative Arrays werden i.d.R. als Hashmaps implementiert, so auch in PHP. Deshalb werden heute die Hintergründe ein wenig näher beleuchtet.
Der Begriff setzt sich aus den beiden englischen Begriffen hash, der eine Hashfunktion bezeichnet, und map (dt. Abbildung) zusammen. Geläufiger dürfte die Bezeichnung Funktion für eine (mathematische) Abbildung sein. Was versteht man unter Funktion? Eine Beziehung zwischen zwei Mengen, dem Definitions- und dem Wertebereich. Dabei ordnet eine Funktion jedem Element des Definitionsbereichs genau ein Element aus dem Wertebereich zu. In der Schule werden zur Beschreibung von Funktionen häufig Tabellen benutzt, um diese Relationen zu beschreiben. Dadurch erschließt sich auch der deutsche Begriff Hashtabelle.
Nicht nur der Begriff Hashmap, sondern auch die Datenstruktur Hashmap setzt sich aus einer Abbildung und einer Hashfunktion zusammen. In diesem Kontext bezeichnen wir den Definitionsbereich als Schlüsselmenge und den Wertebereich als Objektmenge. D.h. die Funktion bildet einen Schlüssel auf ein Objekt ab. Der Begriff Objekt ist hierbei nicht zu verwechseln mit dem gleichnamigen objektorientierten Konzept. Deshalb kann die Objektmenge natürlich auch skalare Objekte, z.B. Strings, enthalten. Da wir nun wissen, welchen Zweck man mit einer Hashmap verfolgt, nämlich das Speichern und Auslesen von Objekten anhand von Schlüsseln, können wir dazu übergehen, wie eine Hashmap implementiert wird. Hierfür ist die bereits erwähnte Hashfunktion der Namensgeber. Um Missverständnisse zu vermeiden, muss noch geklärt werden, was eine Hashfunktion ist: Eine Funktion, die einem Objekt einen numerischen Wert zuordnet. Das prominente Beispiel hierfür ist die Funktion md5, die einem String einen hexadezimalen Wert zuordnet. In PHP könnte man eine Hashfunktion schreiben, die eine Variable $obj auf hexdec(md5(serialize($obj))) abbildet. Durch die Serialisierung wird sichergestellt, dass md5 den MD5-Hash des Objekts berechnen kann. Da der Rückgabewert von md5 hexadezimal ist, ist die Funktion hexdec notwendig, um dem hexadezimalen Wert den gleichen dezimalen Wert zuzuordnen.
Nachdem wir die begrifflichen Voraussetzungen geschaffen haben, wird es Zeit, die Verwendung der Hashfunktion zu erläutern. Wir benutzen die Hashfunktion, die nachfolgend mit hash bezeichnet wird, um den Speicherort eines Objekts anhand seines Schlüssels zu bestimmen. Hierfür werden Arrays mit numerischen Indizes, wie z.B. SplFixedArray, verwendet. Damit diese Zuordnung funktioniert, ist es notwendig, dass das Array stets dieselbe Länge hat. Angenommen, die Länge sei mit n begrenzt, dann suchen wir eine Funktion f, die jedem Element der Schlüsselmenge ein Element aus {0, …, n-1} zuordnet. f ließe sich dann folgendermaßen definieren: f(key) = hash(key) modulo n. D.h. erst wird der Hash eines Schlüssels generiert und anschließend wird modulo n, d.h. der Rest bei einer ganzzahligen Division durch n, berechnet. Durch die modulo-Operation ergibt sich auch die Einschränkung der konstanten Länge des Arrays. Mit f haben wir nun eine Funktion gefunden, die jedem Schlüssel einen Speicherort im Array zuweist. Da diese Funktion O(1)-Schritte zum Berechnen der Position benötigt, lassen sich auch die beiden Operationen zum Einfügen und Auslesen von Objekten in O(1) realisieren. Die Schritte beim Einfügen und Auslesen können folgendermaßen zusammengefasst werden:
- insert(key, obj):
- Position p anhand von f(key) berechnen.
- obj an Position p schreiben.
- read(key):
- Position p anhand von f(key) berechnen.
- Lesen an Position p und ggf. Objekt zurückgeben.
Dieser Algorithmus und die obere Schranke gelten allerdings nur für den besten Fall, in dem keine sog. Kollisionen auftreten. Bei einer Kollision erhalten zwei Schlüssel dieselbe Position innerhalb des Arrays. Um dieses Problem zu lösen, gibt es zwei gängige Verfahren: Hashing mit Verkettung und Hashing mit offener Adressierung.
Beim Hashing mit Verkettung enthält jedes Array-Element sog. Buckets (dt. Behälter), in denen die kollidierten Objekte mitsamt Schlüssel enthalten sind. Im trivialen Fall handelt es bei den Buckets um Arrays, aber natürlich sind auch komplexere Datenstrukturen wie Suchbäume möglich. Die Prozeduren zum Einfügen und Auslesen müssen dann folgendermaßen modifiziert werden:
- insert(key, obj):
- Position p anhand von f(key) berechnen.
- Wenn key im Bucket der Position p existiert, wird das Paar (key, obj) aktualisiert, ansonsten wird es eingefügt.
- read(key):
- Position p anhand von f(key) berechnen.
- Wenn key im Bucket der Position p existiert, wird das zugehörige Objekt zurückgegeben.
Im schlimmsten Fall sind alle Elemente der Hashmap in einem Bucket, womit sich die Komplexität verschlechtert, z.B. auf O(log n) bei guten Suchbäumen.
Eine Alternative stellt das Hashing mit offener Adressierung dar. Hierbei wird eine weitere Funktion g eingeführt, die zum Generieren einer Folge von Positionen verwendet wird. Die einfachste Funktion dieser Bauart ist die sog. Nachfolgerfunktion, die einer Zahl seinen Nachfolger zuordnet. Bei diesem Verfahren enthält jedes Array-Element nur das Objekt mitsamt Schlüssel. Natürlich müssen die Prozeduren zum Einfügen und Auslesen auch für diese Strategie angepasst werden.
- insert(key, obj):
- Position p anhand von f(key) berechnen.
- Ist das Array an Position p leer, so wird (key, obj) an Position p eingefügt und die Prozedur beendet.
- Passt der Schlüssel an Position p zu key, so wird das vorhandene Objekt durch obj ersetzt und die Prozedur beendet.
- Setze p = g(p) modulo n.
- Fahre bei 2. fort.
- read(key):
- Position p anhand von f(key) berechnen.
- Ist das Array an Position p leer, so wird null zurückgegeben.
- Passt der Schlüssel an Position p zu key, so wird das Objekt an Position p zurückgegeben.
- Setze p = g(p) modulo n.
- Fahre bei Schritt 2 fort.
Wie man sieht, ist hier eine Endlosschleife möglich. Dieser Fall kann auftreten, wenn eine ungünstige Funktion g, wie z.B. die identische Funktion id mit id(x) = x, gewählt wurde, oder alle Positionen des Arrays bereits besetzt sind. Zum Verhindern der zuletzt genannten Situation, kann man das Array vergrößern und die enthaltenen Elemente umordnen. Auch beim Hashing mit Verkettung ist das Vergrößern des Arrays sinnvoll, da man damit die Anzahl der Kollisionen reduziert und somit im Mittel eine geringere Zugriffszeit erhält.
Resümierend lässt sich sagen, dass Hashmaps aufgrund der bestmöglichen Best-Case-Laufzeit von O(1) und einer Worst-Case-Laufzeit von O(log n) bzw. O(n) zu den schnellsten Datenstrukturen zählen. Dieser Vorteil wird durch die Nutzung einer geeigneten Hashfunktion realisiert, mit der das Suchen im günstigsten Fall nicht notwendig ist, da sich die Position im Array in einem konstanten Schritt berechnen lässt. Eben diese Funktion fehlt noch für eine effiziente Implementierung in nativem PHP, wohingegen die restlichen Strategien ausreichend beschrieben wurden, um sie implementieren zu können.
