Hash-tabelle

Zurück ◈ Weiter

Höhepunkte dieser Übung:

Lab Übung:


Klicken Sie auf den kleinen Computer oben für eine detaillierte Beschreibung.
Für diese Übung werden Sie gebeten, ein Passwort Kontrollsystem zu implementieren, ein Benutzer-Passwort zu authentifizieren.

1. Definition eines Hash Table

Bevor wir in die Definition von Hash Tables bekommen, ist es gut vorstellen WARUM Hash-Tabellen zu verwenden.

Hash-Tabellen sind gut für eine schnelle Suche auf Dinge zu tun.

Zum Beispiel, wenn wir ein Array mit Daten gefüllt haben (sagen wir 100 Artikel). Wenn wir die Position, dass ein bestimmtes Element wussten in einem Array gespeichert ist, dann könnten wir es schnell zugreifen. So passieren wir nur zu wissen, dass das Element wir wollen an Position 3; Ich kann gelten:
MyItem = myarray [3];

Damit wir müssen nicht in der Anordnung durch jedes Element suchen, greifen wir nur Position 3.

Die Frage ist, wie können wir wissen, dass Position 3 speichert die Daten, die wir interessiert?

Dies ist, wo Hashing in praktisch. Gegeben einige Schlüssel, können wir eine Hash-Funktion, um es anzuwenden, einen Index oder die Position zu finden, die wir zugreifen wollen.

1.1 Was ist die Hash-Funktion?

Es gibt viele verschiedene Hash-Funktionen. Einige Hash-Funktionen werden einen Integer-Schlüssel nehmen und es in einen Index drehen. Ein allgemeines Verfahren ist die Teilung.

Lassen Sie uns ein Beispiel lernen:

1.2 Teilungsverfahren (ein Hash-Verfahren für ganze Zahlen)

Angenommen, Sie haben die folgenden Nummern oder Schlüssel hatte, die Sie in einer Reihe von 10 Elementen abbilden wollte:

123456
123467
123450

Um die Teilungsverfahren anzuwenden, könnte man die Anzahl von 10 (oder die maximale Anzahl der Elemente in dem Array) unterteilen und verwenden, den Rest (Modulo) als Index. Die folgende ergäbe:

123456% 10 = 6 (der Rest ist 6, wenn sie durch 10 dividiert)
123467 10% = 7 (der Rest ist, 7)
123450 10% = 0 (der Rest ist 0)

Diese Zahlen würden 6, 7 und 0 jeweils in die Anordnung an Positionen eingefügt werden. Es könnte wie folgt aussehen:

Die wichtige Sache mit dem Teilungsverfahren ist, dass die Schlüssel ganze Zahlen sind.

1.3 Was passiert, wenn die Tasten sind nicht ganze Zahlen?

Sie haben eine andere Hash-Funktion anzuwenden, um sie in ganzen Zahlen zu drehen. Effektiv, erhalten Sie zwei Hash-Funktionen in einem:
  1. Funktion erhält eine ganze Zahl
  2. Funktion ein Hash-Verfahren von oben aufzubringen, einen Index zu einem Array zu erhalten

Was meinen wir, dass die Tasten sind nicht ganze Zahlen? Nun, lassen Sie uns sagen, dass die Schlüssel Die Namen sind. Sowie:

Sarah Jones
Tony Balognie
Tom Katz

Das Ziel ist, in einen dieser Namen zu geben und einen Index auf ein Array, um diese Informationen zugreifen zu bekommen. Wie machen wir das?
Die Hash-Funktion hat zwei Dinge zu tun:
  1. Konvertieren Sie die Namen in ganzen Zahlen
      Zum Beispiel haben wir eine Funktion, die eine Zeichenfolge in eine ganze Zahl dreht. Die Ergebnisse werden wie folgt aussehen:
      Sarah Jones -> 1038
      Tony Balognie -> 1259
      Tom Katz -> 746
  2. Tragen Sie eine Hash-Methode einen Index zu erhalten
      Wir können nun die Teilungsmethode anwenden, einen Index für eine Reihe von 10 Elementen zu erhalten
      Sarah Jones -> 1038% 10 -> 8
      Tony Balognie -> 1259% 10 -> 9
      Tom Katz -> 746% 10 -> 6

1.4 Was würde das aussehen wie in der Matrix?

Das Array wird als Hash-Tabelle bekannt. Es speichert den Schlüssel (verwendet, um den Index zu finden) zusammen mit den zugehörigen Werten. In dem obigen Beispiel könnten wir eine Hash-Tabelle, die in etwa so aussah:

Auch hier ist die Idee, dass wir Einzelteile in die Hash-Tabelle einfügen den Schlüssel und Anwenden der Hash-Funktion (en), den Index zu erhalten verwenden.

Ein Problem tritt auf, wenn zwei Tasten, um den gleichen Index ergeben. Zum Beispiel, sagen wir schließen wollten:
John Smith -> 948% 10 -> 8

Wir haben eine Kollision, weil Sarah Jones bereits bei Array-Index 8 gespeichert ist.

Wir brauchen eine Methode, um diese zu lösen. Die Auflösung kommt, wie Sie Ihre Hash-Tabelle erstellen. Es zwei wichtige Ansätze in dem Buch:
  1. linear Probing
  2. Verkettung
Der Ansatz in diesem Labor verwendet wird als Verkettung bezeichnet.

Die Details sind als Klasse Material verlassen, aber erkennen, dass in Verkettungs Sie eine Reihe von verknüpften Listen haben. Alle Daten in der „gleichen Link“ haben kollidiert Indexwerte.

Betrachten wir ein Diagramm des obigen Beispiels. Denken Sie daran, es zu einer Kollision mit Sarah Jones und John Smith war. Beachten Sie, dass John Smith „gekettet“ oder „verknüpft“ nach Sarah Jones.

1.5 Anwendungen von einer Hash-Tabelle

Hash-Tabellen sind gut in Situationen, in denen Sie enorme Datenmengen, aus denen Sie schnell mögen Suchen und Abrufen von Informationen. Einige typische Hash-Tabelle Implementierungen würden in den folgenden Situationen:
  • Für den Führerschein Rekord. Mit einer Hash-Tabelle, könnten Sie schnell erhalten Informationen über den Fahrer (dh. Namen, Anschrift, Alter) angesichts der Lizenznummer.

  • Für Compiler Symboltabellen. Der Compiler verwendet eine Symboltabelle Spur der benutzerdefinierten Symbole in einem C ++ Programm zu halten. Dies ermöglicht es dem Compiler schnell Attribute nachschlagen mit Symbolen zugeordnet (zB Variablennamen)

  • Für Internet-Suchmaschinen. hier Für weitere Informationen, klicken Sie auf

  • Für Telefonbuch-Datenbanken. Sie könnten die Verwendung einer Hash-Tabelle implementatation machen, um schnell John Smith Telefonnummer nachzuschlagen.

  • Für elektronische Bibliothekskataloge. Hash Table-Implementierungen ermöglichen eine schnelle Entdeckung unter den Millionen von Materialien, die in der Bibliothek gespeichert.

  • Für Passwörter für Systeme mit mehreren Benutzern zu implementieren. Hash-Tabellen ermöglichen einen schnellen Abruf des Passworts, das zu einem bestimmten Benutzernamen entspricht.

    • 1.6 Typische Operationen eines Hash Table

    Die Funktionen im Zusammenhang mit unserer Implementierung der Hash-Tabelle sind die folgenden:
  • bool isEmpty ()
    Gibt true zurück, wenn die Hash-Tabelle ist leer. Ansonsten gibt false zurück

  • bool isFull ()
    Gibt true zurück, wenn die Hash-Tabelle ist voll. Ansonsten gibt false zurück

  • Leerer Einsatz (konst DT newDataItem)
    NewDataItem Inserts in die entsprechende Liste in der Hash-Tabelle. Die Lage (Index), in der Hash-Tabelle wird von dem Schlüssel und der Hash-Funktion bestimmt.

  • bool remove (KF Suchbegriff)
    Durchsucht die Hash-Tabelle für das Datenelement mit dem Schlüssel SearchKey. Wenn das Datenelement gefunden wird, entfernt dann das Datenelement und gibt true zurück. Andernfalls wird false zurückgegeben.

  • bool abrufen (KF Suchbegriff, DT dataItem)
    Durchsucht die Hash-Tabelle für das Datenelement mit dem Schlüssel SearchKey. Wenn das Datenelement gefunden wird, dann kopiert das Datenelement dataItem und gibt true zurück. Andernfalls wird false zurückgegeben.

  • nichtig clear ()
    Entfernt alle Datenelemente in der Hash-Tabelle.

  • Leerer showStructure ()
    Gibt die Datenelemente in einer Hash-Tabelle. Wenn die Hash-Tabelle leer ist, Ausgänge, "Empty-Hash-Tabelle". Dies wird für den Test / Debug-Zwecke gedacht.

    2. Anwendung: Nachschlagen Passwörter

    Im folgenden Abschnitt wird ein Algorithmus für das Kennwort eines Benutzers zu authentifizieren. Später im Labor Übung werden Sie das Skelett Code gegeben und baten Linien hinzuzufügen, damit es funktioniert.

    Eine mögliche Verwendung für eine Hash-Tabelle ist Computer-Benutzer Login Benutzernamen und Passwörter zu speichern.

    Es gibt zwei wichtige Schritte zu diesem Programm:
    1. Das Programm wird Benutzername / Passwort-Sets aus der Datei password.dat laden und sie in die Hash-Tabelle einfügen, bis das Ende der Datei auf password.dat erreicht ist. Die password.dat Datei wird mit einem Benutzernamen / Passwort pro Zeile festgelegt wie folgt aussehen:
  • Das Programm wird dann eine Anmeldeaufforderung präsentieren, lesen Sie einen Benutzernamen, ein Passwort vorhanden Aufforderung, und nach den Benutzernamen des Passworts in der Hash-Tabelle nachschlagen, wird entweder „Authentifizierung erfolgreich“ oder „Authentifizierungsfehler“ drucken. Die Ausgabe könnte wie folgt aussehen:
    • Schritt 2 wird wiederholt, bis das Ende der Eingangsdaten (EOF) auf dem Konsoleneingangsstrom erreicht ist (CIN). Die EOF-Zeichen auf dem PC sind die CTRL Z Charakter.

    Lassen Sie sich in einigen Details füllen:

    3. Laborübung

    • Holen Sie sich die Dateien:
    • Extrahieren Sie alle Dateien auf dem WORK. Öffnen Sie den WORK und doppelklicken Sie auf exercise.sln. Dadurch wird das Projekt öffnen. Es gibt sechs Dateien in diesem Programm verwendet:
      • hashtbl.cpp und hashtble.h - enthalten, die Umsetzung der Hashtable-Klasse
      • listlnk.cpp und listlnk.h - enthalten die Umsetzung der verkettete Listen Klasse
      • login.cpp - das Hauptprogramm. Diese enthält die Passwort-Struktur, die in der Hash-Tabelle eingefügt wird.
      • password.dat - enthält alle Benutzer und die entsprechenden Passwörter.
    Die Schritte umfassen:
  • Versuchen Sie, dieses Programm auszuführen. Sie sollten feststellen, dass es Sie veranlassen wird „Login“ und „Password:“ (Typ in zufälligen Worten an diesen Aufforderungen). Sie werden feststellen, dass es continuely Zyklen für diese Informationen fragen Sie sich um.
    So beenden Sie das Programm von ausgeführt wird, bei der „Anmeldung:“ Eingabeaufforderung geben Sie CTRL und z (gleichzeitig) und dann die Enter-Taste.

  • Fügen Sie in einer Zeile Kennwörter in die Tabelle einzufügen. Hinweis: Beachten Sie, dass der Name der Hash-Tabelle Passwörter sind und dass Sie ein Passwort Struktur namens tempPass in die Hash-Tabelle eingefügt werden sollen.

  • Fügen Sie in einer Zeile die Hash-Tabelle auszudrucken. Hinweis: die Hash-Tabelle ist Passwörter und es gibt eine Memberfunktion namens showStructure.

  • Fügen Sie Zeilen, das wahre Kennwort des eingegebenen Passwort und print „Authentifizierungsfehler“ oder „Authentifizierung erfolgreich“ zu vergleichen. Hinweis: Vergleichen Sie das eingegebene Passwort (pass), um das Passwort innerhalb des tempPass Objekt (das abgerufen wurde).

  • Erstellen und Ausführen Ihres Programms. Sie sollten die Ergebnisse wie folgt erhalten:
  • Sie wollen jetzt vielleicht mit ein paar Dinge zu spielen, um zu sehen, was passiert:
    • Ändern Sie die folgende Zeile ein, so dass Sie 8 Elemente in der Hash-Tabelle (statt 10): Was ist mit dem Hash-Tabelle geschieht? Warum?
    • Bearbeiten Sie die Datei password.dat. Diese Datei wurde in das Projekt (im Solution Explorer unter „Resource Files“) hinzugefügt. Klicken Sie doppelt auf ihn zu öffnen.

    Testplan für „Login“ Simulationsprogramm

    In Verbindung stehende Artikel

    • Zurück ◈ Weiter