Übersicht über einfache Hash-Tabellen
Als Auffrischung ist eine Hash-Tabelle eine Möglichkeit, einen Wert unter einem bestimmten Schlüssel in einer Datenstruktur zu speichern. Zum Beispiel könnte ich den Wert "a"unter dem Schlüssel speichern 1und ihn später abrufen, indem ich den Schlüssel 1in der Hash-Tabelle nachschaue.
Das einfachste Beispiel für eine Hash-Tabelle, das ich mir auf Anhieb vorstellen kann, ist eine Hash-Tabelle, in der nur Ganzzahlen gespeichert werden können, wobei der Schlüssel für den Hash-Tabelleneintrag auch der gespeicherte Wert ist. Angenommen, Ihre Tabelle hat die Größe 8 und ist im Prinzip ein Array im Speicher:
---------------------------------
| | | | | | | | |
---------------------------------
0 1 2 3 4 5 6 7
Hash-Funktion
Hash-Funktionen geben Ihnen einen Index, wo Sie Ihren Wert speichern können. Eine recht einfache Hash - Funktion für diese Tabelle wäre 1 zu dem Wert hinzufügen , die Sie speichern möchten, und dann mod es um 8 (Tabellengröße). Mit anderen Worten, Ihre Hash-Funktion ist (n+1)%8, wo nist die ganze Zahl, die Sie speichern möchten.
Einsätze
Wenn Sie einen Wert in diese Hash-Tabelle einfügen möchten, rufen Sie (in diesem Fall (n+1)%8) Ihre Hash-Funktion für den Wert auf, den Sie einfügen möchten, um einen Index zu erhalten. Wenn wir beispielsweise 14 einfügen möchten, würden wir (14 + 1) % 8index aufrufen und abrufen 7, sodass wir den Wert in index einfügen würden 7.
---------------------------------
| | | | | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Ebenso können wir 33, 82 und 191 wie folgt einfügen:
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Kollisionen
Aber was passiert, wenn wir versuchen, etwas einzufügen, das mit einem Eintrag kollidieren würde? 2 in Index gehen sollte 3, aber es wird aufgenommen von 82. Es mehrere Möglichkeiten, dieses Problem zu lösen, ist die einfachste unsere Hash - Funktion erneut aufrufen und wieder wiederholt , bis wir einen leeren Raum finden.
Die Logik ist also wie folgt:
- (2 + 1)% 8 = 3
- Index 3 ist voll
- Stecken Sie 3 wieder in unsere Hash-Funktion. ( 3 + 1)% 8 = 4 , was leer ist.
- Platzieren Sie unseren Wert in Index 4 .
Nun sieht die Hash-Tabelle so aus, wobei der Wert 2 im Index gespeichert ist 4.
---------------------------------
|191| |33 |82 |2 | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Der Nachteil dieser Lösung ist, dass unser Tisch bald voll sein wird! Wenn Sie wissen, dass Ihre Datenmenge begrenzt ist, sollte dies kein Problem sein, solange Ihre Tabelle groß genug ist, um alle möglichen Werte aufzunehmen. Wenn Sie in der Lage sein möchten, mehr zu halten, können Sie Kollisionen unterschiedlich behandeln. Gehen wir zurück zu dem Punkt, an dem wir vor dem Einfügen von 2 waren.
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Wenn Sie sich erinnern, (2+1)%8gibt uns Index 3, der genommen wird. Wenn Sie nicht möchten, dass sich Ihre Hash-Tabelle füllt, können Sie jeden Tabellenindex als verknüpfte Liste verwenden und an die Liste an diesem Index anhängen. Anstatt die Hash-Funktion erneut aufzurufen, hängen wir sie einfach an die Liste im Index an 3:
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Diese Liste kann so groß werden, wie es der Speicher zulässt. Ich kann 18 einfügen und es wird nur an 2 angehängt:
-----
|18 |
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Lookups
Die Suche nach Werten in Ihrer Hash-Tabelle ist schnell, da Ihre Hash-Tabelle ziemlich groß ist. Sie rufen einfach Ihre Hash-Funktion auf und erhalten den Index. Angenommen, Sie möchten sehen, ob 82 in Ihrer Tabelle enthalten ist. Die Suchfunktion würde (82+1)%8= aufrufen 3und das Element im Index betrachten 3und es für Sie zurückgeben. Wenn Sie 16 nachschlagen, wird die Suchfunktion im Index nachgeschlagen 1und es wird festgestellt, dass sie nicht vorhanden ist.
Lookups müssen auch mit Kollisionen umgehen!
Wenn Sie versuchen, den Wert 2 nachzuschlagen, müsste Ihre Hash-Tabelle dieselbe Kollisionslogik verwenden, die zum Speichern der Daten verwendet wurde, wie zum Abrufen der Daten. Abhängig von der Funktionsweise Ihrer Hash-Tabelle werden Sie entweder den Schlüssel immer wieder hashen, bis Sie den gesuchten Eintrag finden (oder eine leere Stelle finden), oder Ihre verknüpfte Liste durchlaufen, bis Sie das Element gefunden haben (oder an das Ende der Liste)
Zusammenfassung
Hash-Tabellen sind daher eine gute Möglichkeit, Schlüssel-Wert-Paare schnell zu speichern und darauf zuzugreifen. In diesem Beispiel wurde derselbe Schlüssel wie der Wert verwendet, aber in Hash-Tabellen der realen Welt sind die Schlüssel nicht so eingeschränkt. Hash-Funktionen arbeiten mit den Schlüsseln, um einen Index zu generieren, und dann kann der Schlüssel / Wert an diesem Index gespeichert werden. Hash-Tabellen sind eigentlich nicht dazu gedacht, durchlaufen zu werden, obwohl dies möglich ist. Wie Sie sehen, können Hash-Tabellen viele Leerzeichen enthalten, und es wäre Zeitverschwendung, sie zu durchlaufen. Auch wenn die Hash-Tabelle über eine Logik zum Überspringen von Leerraumsuchen im Iterator verfügt, ist es besser, eine für Iteratoren konzipierte Datenstruktur wie verknüpfte Listen zu verwenden.
Stellen Sie sich eine Bibliothek mit Tausenden von Büchern vor. Sie müssen die Bücher so organisieren, dass Sie sie nach Titel so schnell wie möglich finden können.
Eine (gebräuchliche) Möglichkeit besteht darin, die Bücher alphabetisch zu sortieren. Wenn Ihr Titel mit "G" beginnt, finden Sie den Bereich "G". Suchen Sie nach dem zweiten Buchstaben, sagen Sie "ö", dann "d", "e", "l", und grenzen Sie Ihre Suche ein , bis du das Buch findest. Dies kann jedoch lange dauern, und außerdem müssen Sie bei der Ankunft neuer Bücher manchmal Ihr Layout neu organisieren, um Platz für die Neuankömmlinge zu schaffen.
Das ist eine binäre Suche. Das ist gut.
Es gibt jedoch einen schnelleren Weg, dies zu tun. Angenommen, Sie zählen alle Bücherschränke und Regale auf und berechnen dann für jedes Buch eine spezielle, hoffentlich eindeutige Nummer, die einem Bücherregal zugeordnet ist, in dem sich das Buch befinden soll. Die Art und Weise, wie Sie den "Schlüssel" berechnen, spielt keine Rolle, solange es sich um eine zufällig aussehende Zahl handelt. Sie können beispielsweise Zeichencodes aller Buchstaben im Titel hinzufügen und diese durch eine Primzahl teilen (möglicherweise nicht die beste Methode, funktioniert aber trotzdem).
Das ist Haschisch. Es geht viel schneller, weil Sie nicht durch ganze Bücherregale und Regale gehen müssen, um den nächsten Buchstaben im Titel nachzuschlagen. Das Hashing ist normalerweise eine einmalige Operation, es sei denn, Sie haben eine "Kollision", wenn zwei oder mehr Bücher auf den gleichen Schlüssel aufgelöst werden. Aber das ist in Ordnung, Sie wissen, dass sie nebeneinander liegen, und abhängig von der Qualität der Hash-Funktion sollten nicht zu viele unter demselben Schlüssel sein.
Hash-Tabellen haben einige Einschränkungen und Launen (Aufbereiten / Ändern der Größe), die die binäre Suche als überlebensfähiger Konkurrent aufrechterhalten. Es ist nicht alles schwarz-weiß, welche Methode besser ist. Aber das ist eine andere Geschichte.
PS Entschuldigung, dass Sie Ihre Frage nicht direkt beantwortet haben (schreiben Sie eine Hash-Tabelle in PHP), aber das sind Details und es heißt "Programmierung";)
quelle
Die Hash-Tabelle in PHP wird meines Wissens einfach über Folgendes implementiert:
Sie greifen dann auf die Daten über Anrufe zu, wie zum Beispiel:
Mit der Funktion foreach () können Sie den Inhalt des Arrays durchlaufen.
Der beste Weg, Hash-Tabellen zu verstehen, besteht darin, so etwas wie http://en.wikipedia.org/wiki/Hash_table zu lesen , aber es läuft grob so ab: Die linke Seite jeder Zeile in diesem array () -Aufruf sind die Schlüssel . Diese Schlüssel werden einer Hash-Berechnung unterzogen und das Ergebnis ist ein Hash. Sie haben wahrscheinlich schon einmal MD5- oder SHA-Hashes gesehen, es sieht ziemlich ähnlich aus. Ein bestimmter Teil dieses Hashs, in der Regel die ersten X-Zeichen, manchmal jedoch der vollständige Hash, wird verwendet, um die sogenannten "Buckets" zu identifizieren, die die Speicherbereiche für die Werte darstellen (rechts).
Wenn Sie dann auf Ihre Hash-Tabelle zugreifen, verwenden Sie den Schlüssel, um zum Wert zu gelangen. Der Schlüssel wird erneut zu einem Hash berechnet und der Hash wird verwendet, um den zugehörigen Wert schnell nachzuschlagen. Hash-Tabellen ermöglichen also ein schnelleres Nachschlagen als nur eine lineare Suche, wenn nur alles gespeichert wurde. Der einzige Nachteil ist, dass einige Hash-Implementierungen unter Kollisionen leiden. Dies ist der gleiche berechnete Hash für zwei verschiedene Schlüssel. Im Allgemeinen müssen Sie sich keine großen Sorgen machen.
Ich hoffe, dies liefert Hintergrundinformationen, aber bitte versuchen Sie, mehr über das Thema zu erfahren, wenn Sie daran interessiert sind. Meine Erklärung ist sehr rudimentär und ich bin sicher, dass es genug Löcher gibt, aber es sollte für eine schnelle Erklärung ausreichen.
quelle