Grundlagen der Programmierung: Datenstrukturen

Hashtabellen

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Hashtabellen erweitern durch den Einsatz einer Hashfunktion (und eventuell etwas zusätzlicher Logik) den Funktionsumfang eines herkömmlichen Arrays.

Transkript

Die Idee das Hashens ist sehr fundamental für das Verständnis einer Datenstruktur namens Hash-Tabelle. Eine Hash-Tabelle ist eine typische Art, ein assoziatives Array zu erzeugen. In Ihrer Sprache mag das dictionary heißen oder map oder Hash oder tatsächlich HashTable. Der Riesenvorteil von Hash-Tabellen gegenüber Arrays und verlinkten Listen besteht darin, dass sie sehr schnell sind. Für beides. Für das Nachsehen, ob ein Eintrag existiert oder nicht und für das Auffinden eines speziellen Eintrags in einer Hash-Tabelle Und für das Hinzufügen und Entfernen von Einträgen. Lassen Sie uns einen Blick drauf werfen, warum das so ist. Wenn eine Hash-Tabelle erzeugt wurde, ist das eine intern sehr undramatische array-basierte Datenstruktur. Aber es fügt eine zusätzliche Funktionalität hinzu, um die Einschränkungen eines Arrays zu überwinden. Normalerweise können Hash-Tabellen mit geringem Aufwand erzeugt werden. Wenn Sie wissen, wie groß alles werden soll, so ist es besser für das Speicher-Management, mit Hash-Tabellen zu arbeiten. Sogar wenn es um eine flexible Anzahl an Elementen geht, die Idee dahinter ist dieselbe: dass nämlich eine Hash-Tabelle mit einer Menge an Platzhaltern beginnt einer Menge an Buckets, Körben, die alle nur auf Inhalte warten. Sogar, wenn's eine flexible Anzahl an Elementen werden soll, die Idee dahinter ist dieselbe. Und Buckets, also Körbe, so dumm die Bezeichnung klingen mag, die wir für diese Einträge in einer Hash-Tabelle verwenden. Wir fügen immer paarweise Inhalte hinzu. Manchmal verwenden wir dafür das Wort add manchmal put, manchmal insert, aber wir fügen einen Schlüssel und einen Wert hinzu. Wir übergeben also diese Information der Hash-Funktion. Und diese nimmt unseren Schlüssel. Das ist in unserem Fall eine Zeichenkette, kann aber genauso gut ein Objekt sein, und lässt es durch die Hash-Funktion jagen und wir bekommen dann einen Integer-Wert heraus. Abhängig von der Hash-Funktion könnte dieser Hash-Wert eine recht große Zahl sein, also ein recht großer Integer-Wert. Damit ist er nicht ein herkömmlicher Index eines Arrays. Nun folgt ein klein wenig Logik. Diese Logik findet innerhalb der Hash-Tabelle statt. Es läuft hinter dem Vorhang ab, aber wir reduzieren die Zahl entsprechend der derzeitigen Größe der Hash-Tabelle. Damit sie versuchen kann, die Elemente gleichmäßig auf die Buckets zu verteilen. Dieses Reduzieren der Zahl kann so einfach sein wie eine Modulo-Operation. Wir nehmen den Hash-Wert und dividieren ihn durch die Anzahl der Buckets der Hash-Tabelle. Wir verwenden, was auch immer als Rest überbleibt, in unserem Fall eben die Fünf, und bilden diese auf dem speziellen Index im Array wieder ab. Dann fügen wir eventuell ein weiteres Schlüssel-Wert-Paar hinzu. Der Schlüssel durchläuft die Hash-Funktion. Wir bekommen einen anderen Wert heraus und der Modulo-Wert, der sich dann daraus ergibt, ist die Zwei, und in diesen Bucket wird dann der entsprechende Wert abgelegt. Aber die Idee ist die: dass wir, wenn wir ein Objekt aus der Hash-Tabelle brauchen, der Hash-Tabelle sagen, dass wir den Wert für einen bestimmten Schlüssel wollen. Es wird den Schlüssel wieder nehmen, ihn die exakt selbe Hash-Funktion durchlaufen lassen und dann kann's direkt zum speziellen Bucket weitergereicht werden, der diesen speziellen Wert enthält, den wir suchen. Keine lineare Suche, keine binäre Suche, kein Durchlaufen einer Liste. Wir gehen direkt zu dem gesuchten Element. Sogar, wenn die Hash-Tabelle tausende, zehntausende Werte beinhaltet. Es ist eine sehr effiziente Art, sowohl für die Suche nach Einträgen als auch für das Hinzufügen von Einträgen. Aber in einer perfekten Welt wollen wir, dass jeder Bucket in der Hash-Tabelle nur exakt einen Wert enthält. Das ist aber nicht immer möglich. Wie wir gesehen haben, steht zu erwarten, dass wir manchmal auf eine Hash-Kollision treffen. Dass wir denselben Hash-Wert für unterschiedliche Objekte bekommen. Darüber hinaus, da wir typischerweise einen Hash-Wert zu einem kleinen index reduzieren, gibt's keine unendliche Anzahl an Buckets. Obwohl wir Hash-Tabellen mit hunderttausenden Einträgen haben. Kollisionen passieren. Wir fügen also einen neuen Schlüssel hinzu, wir jagen ihn durch die Hash-Funktion, es durchläuft die Modulo-Operation und das, was rauskommt, ist ebenfalls die Fünf. Damit landet ein zweiter Wert in diesem Bucket. Das ist kein Desaster. Es ist ein erwartetes Verhalten. Wir wollen nur nicht, dass es zu oft passiert. So wie es unterschiedliche Umsetzungen von Hash-Tabellen gibt, gibt's auch unterschiedliche Ansätze, wie Kollisionen gelöst werden können. Es reicht von eigentlich recht einfachen Lösungen dass etwa jeder Bucket in der Hash-Tabelle seinerseits eine einfache Sammlung enthält, wie ein Array oder eine verlinkte Liste, die dann zu unterschiedlichen Einträgen verweisen kann. So wären wir nach wie vor in der Lage, jeden Bucket schnell zu finden. Aber wenn wir ihn dann gefunden haben, enthält er verschiedene Einträge. Aber die Hash-Tabelle durchläuft die interne Liste um zu finden, was wir gesucht haben. Das wird die separate Verkettung in einer Hash-Tabelle genannt. Mit zwei oder drei Einträgen im Bucket hat es keine signifikante Auswirkung auf die Umsetzung. Es gibt auch andere Techniken, um mit Kollisionen in Hash-Tabellen umzugehen. Unter anderem mit einem Hashing mit offener Adressierung und dem wunderbaren Namen Kuckucks-Hashing, Hopscotch, oder Robin-Hood-Hashing. Aber wir sind pragmatische und praktische Programmierer, also verwenden wir, was auch immer uns unsere jeweilige Sprache bereithält. Sie werden feststellen, dass viele Sprachen mehrere spezielle Umsetzungen von Hash-Tabellen für spezielle Einsatzgebiete anbieten.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
vielen Dank
Anonym
für die gute Erläuterung.

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!