CS 100.9.1: Hash-Tabellen und Hashing

Nach zehn Beiträgen haben wir den Punkt erreicht, an dem dieser Beitrag nach dem Muster „CS101.0“ heißen sollte! Da diese Serie jedoch nicht annähernd tiefgreifend genug ist und ich auch nur annähernd sachkundig genug bin, um einen CS 101-Kurs zu schreiben, nennen wir sie CS 100.9.1. Denken Sie nicht, dass dies bedeutet, dass der Inhalt hier in irgendeiner Weise eine Größenordnung weniger wichtig ist als das, was wir bisher behandelt haben. Tatsächlich sind Hash-Tabellen äußerst grundlegende Datenstrukturen und hätten wahrscheinlich früher in dieser Serie behandelt werden sollen. Siehst du, ich weiß NICHTS?! (Beachten Sie auch, dass ich mich für 100.9.1 anstelle von 100.91 entschieden habe, was die Art und Weise widerspiegelt, wie Softwareversionen veröffentlicht werden. Kann jemand META sagen?!)

Okay, weiter zu den Hash-Tabellen. Sie sind wahrscheinlich mit der Implementierung von Hash-Tabellen vertraut, die Ihre bevorzugte Sprache implementiert: Wörterbücher in Python, Hashes in Ruby, Objekte in JavaScript usw. Nehmen wir die Python-Namenskonvention als Beispiel, da sie am aussagekräftigsten ist. Eine Hash-Tabelle ist genau das: ein Wörterbuch. Wenn Sie darüber nachdenken, was ein Wörterbuch wirklich ist, ist es eine Liste von Schlüssel-Wert-Paaren, in der das Nachschlagen eines Schlüssels einem bestimmten Wert zugeordnet ist. Dies kann besonders nützlich bei der Lösung von Problemen sein, bei denen bei jedem Schritt mehrere Informationen bekannt sein müssen, vielleicht sogar bei einigen Problemen, für die Sie gedacht hätten, ein Array (oder mehrere Arrays) zu verwenden. Bei richtiger Verwendung können Hash-Tabellen die zeitliche Komplexität verschiedener Funktionen erheblich reduzieren und den Code leichter verständlich machen.

Zuerst ein Überblick über Hashing. Ich habe erwähnt, dass jeder Schlüssel einem Wert „zugeordnet“ ist. Dies geschieht natürlich nicht automatisch, sondern der Computer erledigt dies über eine Hash-Funktion. Zu verstehen, wie man eine gute Hash-Funktion schreibt, geht über das hinaus, was die meisten Interviewer von einem Junior-Entwickler erwarten würden, aber es ist nicht schlecht, sich damit vertraut zu machen, auch wenn Sie keinen perfekten Code dafür schreiben können.

Das Problem beim Hinzufügen von Schlüsseln zu einer Hash-Tabelle besteht darin, dass Schlüssel alles sein können. In Arrays ist es einfach, Elemente hinzuzufügen und zu prüfen, ob Elemente vorhanden sind; Sie werden in einem ganzzahligen Index gespeichert, und wir können an diesem Index nach einem Element suchen. Hash-Schlüssel sind nicht unbedingt ganze Zahlen, daher brauchen wir eine Möglichkeit, sie zu standardisieren und sie einem konsistenten Satz möglicher Indizes zuzuordnen. Hier kommt Hashing ins Spiel. Eine Hash-Funktion nimmt einen bestimmten Schlüssel und wandelt ihn in eine Darstellung um, die in der Tabelle gespeichert werden kann. Hash-Funktionen müssen immer denselben Schlüssel an derselben Stelle abbilden, und sie müssen sicherstellen, dass alle gleichen Schlüssel an derselben Stelle abgebildet werden (mit anderen Worten, 9.0, die Gleitkommazahl, und 9, die Ganzzahl, müssen an derselben Stelle im Speicher abgebildet werden). ). Das Problem dabei ist, dass wir beim Erstellen der Hash-Tabelle nicht immer wissen, welche Schlüssel und Arten von Schlüsseln wir speichern müssen. Darüber hinaus sind Hash-Tabellen keine speichereffizienten Datenstrukturen und können schnell unhandlich werden, wenn wir zu viel Platz für die Zuordnung von Schlüsseln zuweisen. Der Kampf mit Hash-Tabellen besteht darin, ein Gleichgewicht zwischen der Zuteilung von zu viel Platz und der Sicherstellung zu finden, dass eindeutige Schlüssel eindeutigen Orten zugeordnet werden. Wenn zwei verschiedene Schlüssel demselben Ort zugeordnet sind, wird dies als „Kollision“ bezeichnet und muss von der Hash-Funktion behandelt werden. Dies ist also der grundlegende Kampf von Hash-Funktionen: Ordnen Sie Schlüssel so vielen verschiedenen Orten wie möglich zu, ohne übermäßig viel Speicherplatz zu beanspruchen, minimieren Sie Kollisionen, und wenn sie auftreten, behandeln Sie sie so effizient wie möglich.

Um auf unser Python-Wörterbuch-Beispiel zurückzukommen, funktioniert die Wörterbuch-Hash-Funktion von Python, indem sie die 32-Bit-Binärdarstellung jedes Schlüssels nimmt, auf die letzten drei Bits in diesem Schlüssel abbildet und, wenn es an dieser Stelle eine Kollision gibt, frühere Bits bis ein einführt Ein leerer Steckplatz wurde gefunden. Wenn 2/3 der Slots in der Tabelle belegt sind, ändert sich die Größe der Tabelle (4x für eine Tabelle <50.000 Einträge lang, 2x für eine Tabelle >50.000). Dies ist jedoch nicht die gebräuchlichste Art, Kollisionen zu behandeln. Weitaus typischer ist die Verwendung von „Verkettung“, bei der ein Schlüssel einem Ort zugeordnet wird, und wenn dort eine Kollision auftritt, wird an diesem Ort eine verknüpfte Liste erstellt, wobei jedes Element in der Liste auf den nächsten zugeordneten Schlüssel zeigt dieser Ort. Unter dem Strich sind Hash-Tabellen auf jeden Fall effizient, weil wir Hash-Funktionen schreiben können, die die Platzeffizienz optimieren und gleichzeitig die Anzahl der Kollisionen minimieren, wodurch eine Situation entsteht, in der im Durchschnitt ein Eintrag in der Tabelle nicht mehr als ist 1–2 Kollisionen tief, und der dafür erforderliche Platz ist nicht wesentlich größer als die Anzahl der Elemente in der Liste. Tatsächlich kann eine Hash-Tabelle mit einer guten Hash-Funktion bei richtiger Verwendung einen gegebenen Schlüssel und seinen Wert finden, einen Schlüssel einfügen und einen Schlüssel löschen, alles im Durchschnitt in O(1)-Zeit.

Es ist wichtig zu erkennen, dass dies beim Hashing mit Verkettung im schlimmsten Fall und tatsächlich für alle Hashing-Schemata gilt: Die Such-, Einfüge- und Löschzeiten betragen O(n). Dies liegt daran, dass im schlimmsten Fall alle Elemente an denselben Ort gehasht werden und wir eine n lange Liste von Elementen zurücklassen. In der Praxis können wir dies unglaublich unwahrscheinlich machen, und der Weg dazu ist eine der häufigsten und bisher undiskutierten Algorithmusstrategien in CS: Randomisierung. Die Idee ist, dass bei n zu hashenden Schlüsseln jeder Schlüssel einem zufälligen Ort zugeordnet wird und somit jeder Schlüssel mit gleicher Wahrscheinlichkeit einem beliebigen Ort zugeordnet wird. In der Praxis hält diese Annahme aus verschiedenen Gründen nicht, aber machen Sie sich darüber keine Sorgen und nehmen Sie sie für wahr. Wenn dies zutrifft, dann ist die erwartete Länge jeder Kette unter der Annahme, dass wir n Schlüssel und eine Tabelle der Länge m haben, n/m, da für jeden Slot in der Tabelle jeder Schlüssel eine Chance von 1/m hat, zu ihm zu gehashen , und es gibt n Schlüssel. Die erwartete Kettenlänge wird als „Lastfaktor“ der Tabelle bezeichnet. Wenn doppelt so viele Schlüssel wie Steckplätze in der Tabelle vorhanden sind, beträgt der Ladefaktor zwei. Wenn n 10 mal m ist, ist der Lastfaktor 10 und so weiter. Das ist nicht wichtig. Wichtig ist, dass dies Konstanten sind, sodass die Kosten für die Durchführung einer Aktion auf dem Tisch immer O(1+n/m) betragen und somit konstant sind.

Der knifflige Teil besteht dann darin, eine Hash-Funktion zu schreiben, die so genau wie möglich die von uns getroffene Annahme simuliert, dass jeder Schlüssel mit gleicher Wahrscheinlichkeit einem bestimmten Ort zugeordnet wird, unabhängig davon, wo andere Schlüssel zugeordnet sind. Auch diese als einfaches einheitliches Hashing bekannte Annahme ist ein theoretisches Ideal, das wir in der Praxis nie erreichen können, aber wir können es so gut wie möglich annähern, und hier kommt die Randomisierung ins Spiel. Wir nennen diesen Algorithmus universelles Hashing und er sieht so aus:

h(k) = [(ak + b) mod p] mod m

Offensichtlich ist h(k) die Hash-Funktion für einen bestimmten Schlüssel. p ist eine Primzahl, die größer ist als das Universum möglicher Schlüssel, die Sie hashen. Wenn Sie also beispielsweise eine Tabelle mit Knochen im menschlichen Körper erstellen, ist p eine Primzahl > 206. a und b sind Zufallszahlen zwischen 0 und p. In der Praxis schafft diese Funktion eine Situation, in der die Wahrscheinlichkeit, dass zwei ungleiche Schlüssel an dieselbe Stelle gehasht werden, im schlimmsten Fall 1/m beträgt, was bedeutet, dass unser theoretisches Ideal im Wesentlichen erfüllt ist.

Auch hier geht das Verständnis von universellem Hashing weit über das hinaus, was die meisten Interviewer von Ihnen erwarten würden, aber ich dachte, zumindest ein wenig damit vertraut zu sein, könnte Ihnen bei Ihrer Suche nur helfen. Hoffentlich hilft ein gewisses Gefühl dafür, wie Hash-Tabellen unter der Haube funktionieren, zu verstehen, warum sie bei der Lösung von Problemen so nützlich sind. Tatsächlich gehören sie zu den häufigsten Datenstrukturen in CS-Anwendungen, und jetzt, da Sie wissen, wie sie funktionieren, fordere ich Sie auf, darüber nachzudenken, wann Sie sie verwenden können, um Probleme zu vereinfachen. Im Allgemeinen sind Hash-Tabellen in Situationen, in denen Sie Beziehungen zwischen mehreren Datenpunkten nutzen möchten, oft die beste Wahl.

Ich werde Sie heute mit einigen weisen Worten eines Moderators der PyCon 2010 namens Brandon Craig Rhodes verlassen

„Mögen Ihre Hashes einzigartig sein, Ihre Hash-Tabellen niemals voll sein und Ihre Schlüssel selten kollidieren“

Danke fürs Lesen! Bis zum nächsten Mal.

Similar Posts

Leave a Reply

Your email address will not be published.