[NOISE].
Vor dem Tauchen in Hash-Tabellen, lassen
zunächst die Vor-und Nachteile von einigen bewerten
einfacher Datenstrukturen, die mit
Arrays.
Daran erinnern, dass Arrays ermöglichen es uns, zu speichern
Elemente eines einzigen Datentyp
im Speicher zusammenhängend.
Da jedes Element zugeordnet ist
ein Index oder Lage,
wir haben wahlfreien Zugriff auf alle der
Elemente in einem Array.
In anderen Worten, wir können jedes Element zugreifen
in einem einzigen Schritt durch Indexieren in der
Array.
Dies ist eine große Sache, weil Algorithmen
wie binäre Suche auf zufälligen hängen
Zugang.
Ein Nachteil von Anordnungen ist, dass ihre Größe
befestigt ist.
Da Arrays speichern Daten zusammenhängend in
Speicher, müssen Sie ein Array-Größe angeben
wenn Sie das Array deklarieren.
Sie sind im Wesentlichen dahin, das Betriebs
System, um den entsprechenden Betrag zu reservieren
Speicher für die Elemente des Arrays.
Es gibt keine Garantie, dass mehr Speicher,
neben Ihrem Array, erhältlich sein
für die spätere Verwendung.
So Arrays nicht leicht wachsen.
Daran erinnern, dass wir gelernt, auch zu verknüpften
Listen, die wachsen können, weil ihre
Elemente sind nicht zusammenhängend im Speicher.
Jeder Knoten in einer verknüpften Liste enthält die
Element, das wir speichern wollen, sowie
ein Zeiger auf das nachfolgende Element in
die Liste.
Leider ist der Preis, den wir bezahlt haben
dynamische Größe ist wahlfreien Zugriff auf
Elemente.
Um ein bestimmtes Element zuzugreifen,
es ist notwendig, den gesamten Verfahrweg
Liste, bis das gewünschte Element
erreicht.
Also, wenn ich mich für die Nummer 9, würde ich
folgen Sie den Zeiger von Knoten zu Knoten,
Prüfen, ob der Wert jedes Knotens
gleich 9 ist.
Als solcher, im schlimmsten Fall, nachschlagen ist
O (n), was wenig effizient ist.
Können wir besser als O (n), während noch
so dass unsere Datenstruktur zu über wachsen
Zeit?
Hash-Tabellen bieten eine Lösung.
Hash-Tabellen verwendet werden, wenn schnelle
Einfügen, Löschen und Suchen von
Elemente Priorität.
In der Theorie, Insertion, Deletion und Lookup
kann sogar in ständiger erreicht werden
Zeit.
Also, was ist eine Hash-Tabelle überhaupt?
Eine Hash-Tabelle ist nur ein Array verbunden
mit einer Funktion, die wir den Hash nennen
-Funktion.
Die Hash-Funktion nimmt ein Stück von Daten
als Eingang, wir nennen dies einen Schlüssel, und
gibt eine ganze Zahl ist, gemeinhin
als Hashwert.
Der Hash-Wert bildet unser Schlüssel zu einem
bestimmten Index in der Hash-Tabelle.
Sie würden zunächst die Hash-Funktion verwenden, um
festzustellen, wo in der Hash-Tabelle, um
speichern Sie eine bestimmte Taste.
Später können Sie den gleichen Hash-Funktion verwenden möchten
zu bestimmen, wo in der Hash-Tabelle, um
Suche nach einem bestimmten Schlüssel.
Aus diesem Grund ist es entscheidend, dass ein Hash
Funktion verhält sich konsequent und Ausgänge
die gleichen Hash-Wert für identische Schlüssel.
Wissen Sie, dass Hash-Tabellen können verwendet werden,
Speicherdaten aller Arten.
Aber die Dinge zu vereinfachen, werden wir uns auf
Saiten für jetzt.
Hier ist eine einfache Hash-Funktion für Strings.
Dieser Hash-Funktion berechnet einen Hash-
Funktion basierend auf dem ersten Buchstaben des
Taste.
"Apfel" mit dem Buchstaben "A", so dass es
mit Index 0 in der Hash-Tabelle zugeordnet.
Ebenso ist "Banane" zu Index 1 zugeordnet,
und "Katze" auf Index 2 abgebildet.
Wenn ein Freund fragt, ob das Wort "Hund" ist in
die Tabelle, wir Eingang "Hund" in die Hash-
Funktion, die folgende Ausgabe ein Hash-Wert
3.
Da "Hund" ist nicht am Index 3 gespeichert sind, wir
kann mit Zuversicht sagen, dass "Hund" ist nicht
in der Tabelle,
obwohl wir nur überprüft, eine der
Hash-Tabelle 26 Indizes.
Zeit, einen Schraubenschlüssel in die Dinge zu werfen.
Was, wenn wir zu "Ameise" in die gespeichert werden soll
Tabelle als gut?
"Ant"-Hashes zu Index 0, so wie "Apfel" hat.
Dies ist ein Beispiel einer Kollision, die
Ergebnis von zwei Hash-Schlüssel zu der gleichen
Index.
Selbst wenn Ihr Hash-Tabelle ist größer als
Ihre Daten gesetzt, und Sie haben eine gute gewählt haben
Hash-Funktion,
Sie müssen noch einen Plan für den Umgang mit
Kollisionen, ob und wann sie entstehen.
Sprechen wir über die Vor-und Nachteile von zwei
gemeinsame Methoden für die Lösung von Kollisionen:
lineare Sondieren und separate Verkettung.
Bei linearen Sondieren, wenn ein Schlüssel-Hashes zu
der gleiche Index wie der zuvor gespeicherten
Schlüssel, es den nächsten verfügbaren zugeordnet ist
Schlitz in dem Tisch.
Also, "ant" jetzt bei Index 3 gespeichert, da
Indizes 0, 1 und 2 wurden bereits im Einsatz.
Und wenn wir versuchen, ein Geschäft, das dritte Wort
mit dem Buchstaben "A", ist es zugewiesen
mit Index 4, da Indizes 0, 1, 2 und 3
sind voll.
Wie Sie auch aus diesem einfachen sehen können
Beispielsweise, wenn eine Kollision auftritt,
Chancen deutlich erhöhen, dass
weitere Kollision in demselben auftreten
Bereich.
Dies wird als Clustering, und es ist ein
gravierenden Nachteil an lineare Sondieren.
Außerdem Worst-Case-Insertion, Deletion,
und Lookup Zeiten haben sich zu O (n) übertragen,
wie der nächste verfügbare Slot haben könnte
möglicherweise bereits der letzte Schlitz in dem Tisch.
Vielleicht separaten Verkettung eine mehr bieten
überzeugende Lösung.
In der separaten Verkettung Modell, die Hash-
Tabelle tatsächlich ein Array von Zeigern auf
verkettete Listen.
Wenn eine Kollision auftritt, kann der Schlüssel
in konstanter Zeit an der Spitze der einge
die entsprechenden verlinkten Liste.
Was passiert nun, wenn wir die Suche nach "apple"
in der Hash-Tabelle?
Im schlimmsten Fall müssen wir durchqueren die
gesamten verketteten Liste, beginnend bei Index 0.
Das Worst-Case-Lookup-Zeit für einen Hash-
Tabelle, die getrennte Verkettung verwendet, ist
Daher O (n / k), wobei k die
Größe der Hash-Tabelle.
Warten Sie eine Sekunde, k ist eine Konstante.
Also O (n / k) ist wirklich nur O (n),
die das Worst-Case-Lookup war Zeit für
eine verkettete Liste.
Haben wir wirklich durch alle gegangen
Mühe des Lernens über Hash-Tabellen
nur um wieder dort landen, wo wir angefangen haben?
Dies kann der Fall sein, von einem theoretischen
Perspektive, aber in der realen Welt,
O (n / k) konnte eine große Verbesserung gegenüber sein
O (n).
Betrachten Sie es mal so: davon ausgehen, dass k
10 - würden Sie lieber warten 100 Sekunden
oder 100 / k?
10 Sekunden nach Microsoft Word zu beenden
Rechtschreibprüfung Ihres Dokuments.
Wie Sie gerade gesehen haben, lösen Kollisionen
bringt eine Art von linearen Suche oder
eine andere, die Dinge verlangsamt
erheblich.
Daher sollten Sie einen Hash wählen
Funktion, die die Chance minimiert
Kollisionen in den ersten Platz auftreten.
Hier sind einige Eigenschaften der gute Hash-
Funktionen im Auge zu behalten.
Eine gute Hash-Funktion nutzen sollten
Alle Informationen, die von einem bestimmten Schlüssel bereitgestellt
um die Anzahl von zu maximieren
Hash-Werte möglich.
Zum Beispiel, wenn wir zwei Strings, "cat"
und "Raupe", würden wir wollen, dass sie hash
zu verschiedenen Orten auf dem Tisch.
Wenn eine Hash-Funktion nur berücksichtigte
die ersten ein, zwei oder sogar drei Buchstaben
der Saiten, würde eine Kollision auftreten,
da beide Wörter beginnen mit dem gleichen
drei Buchstaben.
Hash-Werte sollten gleichmäßig verteilt werden
in der Hash-Tabelle.
Dadurch wird die Länge der verlinkten reduzieren
Listen sollten Kollisionen auftreten.
Es ist auch ein gutes Zeichen, wenn Ihr Hash-Wert
ist in der Lage sehr unterschiedlich
Hash-Werte für ähnliche Tasten,
wodurch Kollisionen viel weniger wahrscheinlich.
Unser Ziel ist es schnelle Einfügen, Löschen,
und Lookup.
Die Hash-Funktion spielt eine entscheidende Rolle bei der
jeder dieser Prozesse und werden
sehr häufig genannt.
Stellen Sie daher sicher, dass es nur sehr beschäftigt
einfache, schnelle Vorgänge zu minimieren Lauf
Zeit.
Ich hoffe, dass Sie diese kurze genossen haben
Einführung in Hash-Tabellen.
Mein Name ist Lauren, und das ist CS50.