Kategorien
Hashmaps – Akademischer Tag 5
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.
Schöner Beitrag, mehr davon! Sehr informativ, aber da auch sehr wissenschaftlich formuliert ist er etwas schwer zu verstehen – aber keine Sorge, besser formuliert als mein altes Buch aus dem Mathe LK war es alle mal 😀
„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.“
Sie sind nur beim Direktzugriff am Schnellsten, zB bei Iterationen sind sie recht langsam, was der direkte Laufzeitvergleich von SplFixedArray auch sehr eindrucksvoll demonstriert.
Ist auch etwas ungünstig formuliert, weil sich „Laufzeit“ immer auf einen Algorithmus bezieht, hier allerdings so einige vorstellt wurden.
Best-Case von O(1) ist nicht ganz richtig,
man darf ja auch die komplexitaet der Hash-Fkt nicht vernachlaessigen,
was natuerlich unter der Annahme das alle Schluessel eine maximale laenge haben wiederrum in O(1) liegt.
@Schaelle: Man muss immer ein Gleichgewicht zwischen Korrektheit und Verständlichkeit finden. Bei solchen Themen finde ich Korrektheit wichtiger, da man durch Nachdenken ein eigenes Verständnis entwickeln kann. Aber solange es noch verständlich ist, ist es okay. Übrigens bin ich für weitere Themenvorschläge offen. 🙂
@KingCrunch: Stimmt, ich hätte zusätzlich schreiben sollen, dass Hashnmaps nur für das Einfügen und Entnehmen zu den schnellsten Datenstrukturen zählen, es aber noch weitere hilfreiche Operationen gibt. Der erste angegebene Algorithmus funktioniert nur unter der Annahme, dass die Hashfunktion kollisionsfrei ist, weshalb ich ihn aus der Komplexitätsbetrachtung weggelassen habe. Die beiden anderen Algorithmen haben dieselbe Best-Case-Laufzeit aber unterschiedliche Worst-Case-Laufzeiten. O(log n) für das Hashing mit Verkettung und O(n) für das Hashing mit offener Adressierung.
@sargon: Bei der Komplexität O(f(n)) mit f(n) = 1 hätte ich angeben sollen, was dieses n ist. Es ist nämlich die Anzahl der Elemente, die sich in der Hashmap befinden. Natürlich kostet auch das Berechnen der Hashfunktion Zeit, aber ich denke, dass das für das Wachstum vernachlässigbar ist. Korrekt müsste die Komplexität O(g(Schlüssellänge)+f(n)) mit obiger Funktion f lauten. Im Grunde genommen hast du jedoch Recht.
Ich finde es genial, dass es hier solche Artikel gibt. Da ich selbst noch nicht zum Studium gefunden habe, ist es für mich sehr interessant mal etwas genauer zu sehen, was sonst nur als „gegeben“ angesehen wird.
Danke ;o)
@Moelle:
Die Kollisionsfreiheit muss nicht zwangsläufig gegeben sein, denn selbst wenn der Eintrag einer HashMap selbst wieder eine (echte) Map ist, ist der Zugriff direkt wieder konstant. Bei Zugriff würde „er“ statt eines einzelnen Elementes eine weitere Liste finden und dort nach dem konkreten Eintrag suchen. In dem Fall hätte man eine Laufzeit von O(n)
@sargon:
Das ist Falsch. Ein Hash-Algorithmus arbeitet immer in O(1) und (zusammen mit der HashMap selber) O(1+1) = O(1). Ein HashMap analysiert nicht, sie berechnet bloss, sie ist also nicht von der Eingangsgrößte abhängig.
Korrektur vom letzten @Moelle:
Die Laufzeit wäre nicht O(n) sondern wesentlich geringer, weswegen sollte klar sein (alle anderen Beiträge liegen irgendwo in anderen Hash-Einträgen).
Das Ausführen der Hashfunktion und der Zugriff auf ein Array-Element hat eine Komplexität von O(1), wie du bereits sagtest. Ist die Hashfunktion kollisionsfrei, bleibt die Komplexität in O(1), da wir sofort wissen, an welcher Position sich das gesuchte Element befindet. Um kollisionsfrei zu sein, müsste die Funktion f injektiv sein. Dafür müsste jedoch die Schlüsselmenge sehr stark begrenzt sein. Deshalb sind die Hashfunktionen im Allgemeinen nicht kollisionsfrei, weshalb wir Strategien benötigen, um trotz der Kollisionen eine eindeutige Zuordnung zu finden. Dies wird über die beiden genannten Strategien realisiert.
Betrachtet man das Hashing mit Verkettung, stellt man fest, dass die Hashfunktion nur eine ungefähre Position des gesuchten Elements angibt. D.h. es wird das einzige Array-Element zurückgegeben, welches das gesuchte Element möglicherweise enthält. Im Worst-Case enthält dieses Array-Element alle in der Hashmap enthaltenen Elemente. Das Durchsuchen dieser Liste hat dann eine Komplexität von O(n). Verwendet man statt einer Liste eine bessere Datenstruktur (z.B. balancierte Suchbäume), verbessert sich die Komplexität natürlich.
Bei der offenen Adressierung erhält man durch die Hashfunktion eine Folge von Indizes, die möglicherweise das gesuchte Element enthalten.
Im schlimmsten Fall hat diese Folge eine Länge von n. Zwar kostet jeder Zugriff O(1), aber da „fast n“ Zugriffe benötigt werden, ist n eine geeignete obere Abschätzung, weshalb die Komplexität in O(n) liegt.
Wenn wir hier von Komplexitätsmaßen reden, sollten wir nicht vergessen, dass mit der O-Notation nur eine obere Abschätzung abgeben wird. Wenn ein Algorithmus in O(n) liegt, heißt nicht, dass er im Normalfall ca. n Schritte benötigt, sondern nur, dass er nicht schneller als linear wächst.
„Dabei ordnet eine Funktion jedem Element des Definitionsbereichs genau ein Element aus dem Wertebereich zu.“
ist soweit ich weiß, nicht ganz korrekt.
Für eine Funktion
f(x)=y=wurzel(x)
kann y genau 2 Werte annehmen. (Vorrausgesetzt x ist positiv.)
y1=-wurzel(x)
y2=wurzel(x)
So ich hoffe ich hab mich nicht verhuddelt. 🙂
Ansonsten:
Weiter so! Besonders die Artikel die um Algorithmen gehen (wie map/reduce) finde ich spitze!
Unter der Voraussetzung, dass x positiv ist, ist sqrt(x) auch positiv. Das ist eine „Vereinbarung“, damit sqrt eindeutig und somit eine Funktion (im Sinne der Definition) ist. Witzigerweise hast du die Vereinbarung beachtet, als du die y-Werte bestimmt hast. 🙂
Die von dir beschriebene Abbildung ist hingegen eine Korrespondenz [1] von den positiven reellen Zahlen in die positiven reellen Zahlen. Eine bessere Definition würde dann lauten: f(x) = { y | x = y^2 }. D.h. f(x) gibt eine Menge von Zahlen y zurück, für die gilt, dass x = y^2 ist.
Falls du Vorschläge für weitere Themen hast: Einfach einen Kommentar verfassen!
[1] http://de.wikipedia.org/wiki/Korrespondenz_%28Mathematik%29
Die „Vereinbarung“ war für mich selbstverständlich, deshalb habe ich sie auch beachtet. Schließlich wurde mir das (auf diese einfache Art und Weise) in der Schule erklärt.
Wenn ich jetzt Alles richtig verstanden habe ist die Korrespondenz in der Mathematik also eine Ausnahme um die Definition von ‚Funktion‘ zu erhalten?
// Eine ganz andere Idee hätte ich noch:
// Was haltet ihr davon auf eine Kommentarplatform wie
// immensedebate oder DISQUS umzusteigen?
// Ich denke das würde die Diskussionen ankurbeln
// und vorallem würde ich dann keine Antwort mehr verpassen. 🙂
Eine Korrespondenz aus A in B ist eine (spezielle) Abbildung, die jedem Element A genau ein Element der Potenzmenge von B zuordnet. Die Potenzmenge von B enthält jede Teilmenge von B. Beispiel: Sei B = {1,2,3}, dann ist die Potenzmenge P(B) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. Damit bleibt die Abbildung eindeutig, aber es werden mehrere Werte (in einer Menge) zurückgegeben.
Um deine Frage zu beantworten: Es ist keine Ausnahme, sondern nur eine besondere Funktion/Abbildung, mit der man das Problem technisch lösen kann.
Ich werde deinen Wunsch weitergeben. 🙂 Du kannst allerdings auch das Kästchen „Bitte benachrichtige mich bei neuen Kommentaren“ ankreuzen.