[Musikwiedergabe]
>> DOUG LLOYD: Jetzt haben Sie wissen viel über Arrays,
und Sie wissen viel über verkettete Listen.
Und wir haben das zu diskutieren Vor-und Nachteile, wir haben
diskutiert, die Listen verbunden kann größer und kleiner werden,
aber sie nehmen mehr Größe.
Arrays sind viel einfacher zu verwenden, aber sie sind restriktiv, so viel
wie wir haben, um die Größe festgelegt das Array zu Beginn
und dann werden wir mit ihm stecken.
>> Aber das ist, wir haben ziemlich viel alle unsere Themen erschöpft
über verkettete Listen und Arrays.
Oder wir haben?
Vielleicht können wir etwas tun, noch kreativer.
Und diese Art von leiht der Gedanke einer Hashtabelle.
>> So in einer Hash-Tabelle, wir werden versuchen, kombinieren ein Array mit einer verketteten Liste.
Wir werden die Vorteile zu nehmen des Arrays, wie Direktzugriffs,
in der Lage zu gehen, nur um Array Element 4 bzw. Array-Element 8
ohne über laufen.
Das ist ziemlich schnell, nicht wahr?
>> Aber wir wollen auch, um unsere Daten Struktur in der Lage, zu wachsen und schrumpfen.
Wir brauchen nicht, wissen wir nicht möchte eingeschränkt werden.
Und wir in der Lage sein wollen, hinzufügen und alles zu entfernen
sehr leicht, die, wenn Sie sich erinnern, ist sehr komplex mit einer Reihe.
Und wir können diesen Aufruf neue Sache eine Hash-Tabelle.
>> Und wenn es richtig umgesetzt, wir Art der Einnahme
die Vorteile der beiden Daten Strukturen Sie bereits gesehen haben,
Arrays und verkettete Listen.
Einsetzen kann zu starten neigen Theta von 1.
Theta wir nicht wirklich diskutiert, aber Theta ist nur der Durchschnittsfall,
was tatsächlich passieren wird.
Sie sind nicht immer zu haben den schlimmsten Fall
und du bist nicht immer gehen zu müssen, Im besten Fall, so was ist
die durchschnittliche Szenario?
>> Gut eine durchschnittliche Insertion in eine Hashtabelle
können Sie beginnen, in der Nähe von konstanter Zeit zu bekommen.
Und Löschen erhalten können schließen, um konstante Zeit.
Und Lookup bekommen können schließen, um konstante Zeit.
That's-- wir eine Daten nicht Struktur noch, dass das tun können,
so dass diese bereits klingt wie eine ziemlich große Sache.
Wir haben wirklich entschärft die Nachteile jeder für sich allein.
>> Um diese Leistung zu erhalten Upgrade aber wir
müssen überdenken, wie wir hinzufügen Daten in der Struktur.
Insbesondere wollen wir die Daten selbst, uns zu sagen
wo es in der Struktur zu gehen.
Und wenn wir dann zu sehen, ob es in die Struktur, wenn wir brauchen, um es zu finden,
wollen wir die Daten anschauen immer in der Lage zu sein, wirksam,
unter Verwendung der Daten, zufällig darauf zugreifen.
Gerade indem Sie das Daten, die wir haben sollten
eine Vorstellung davon, wo wir genau sind werde es in der Hash-Tabelle zu finden.
>> Nun ist die Kehrseite einer Hash- Tabelle ist, dass sie wirklich
ziemlich schlecht bei der Bestellung oder Sortieren von Daten.
Und in der Tat, wenn Sie beginnen , sie zu benutzen, um zu bestellen oder sort
Daten, die Sie all das zu verlieren, Vorteile, die Sie zuvor
hatte in Bezug auf Einfügen und Löschen.
Die Zeit näher an Theta von n, und wir haben im Grunde
in einer verknüpften Liste zurückgebildet.
Und so haben wir den Hash verwenden möchten nur Tabellen, wenn wir nicht kümmern
ob Daten sortiert.
Für den Kontext, in dem Sie werden sie in CS50 verwenden
Sie wahrscheinlich nicht kümmern dass die Daten sortiert.
>> So eine Hash-Tabelle ist eine Kombination aus zwei verschiedenen Stücken
mit denen wir vertraut sind.
Die erste ist eine Funktion, die wir in der Regel rufen Sie eine Hash-Funktion.
Und das Hash-Funktion, um gehen Rück etwas nicht negative Ganzzahl, die
wir in der Regel einen Hash-Code aufrufen, OK?
Das zweite Stück ist ein Array, das ist die Speicherung von Daten des Typs wir
will in der Datenstruktur zu platzieren.
Wir werden uns auf das zu warten, verknüpften Liste Element für jetzt
und nur mit den Grundlagen eines Start Hash-Tabelle, um Ihren Kopf um es zu bekommen,
und dann werden wir vielleicht zu blasen Ihre Meinung ein wenig, wenn wir
kombinieren Arrays und Linklisten zusammen.
>> Die Grundidee obwohl ist, dass wir einige Daten zu nehmen.
Wir führen, dass die Daten durch die Hash-Funktion.
Und so die Daten verarbeitet und es spuckt eine Zahl, OK?
Und dann mit dieser Nummer wir einfach die Daten zu speichern
wir in die gespeichert werden sollen Anordnung an dieser Stelle.
So zum Beispiel, haben wir vielleicht Diese Hash-Tabelle von Strings.
Es hat 10 Elemente in ihr, so Wir können 10 Saiten in ihm passen.
>> Nehmen wir an, wir John hash möchten.
So John als die Daten, die wir einfügen wollen in diesen Hash-Tabelle irgendwo.
Wo stehen wir sagen?
Auch typischerweise mit einem Array so weit wir wahrscheinlich
wäre es in Feldposition 0 gebracht.
Aber jetzt haben wir diese neue Hash-Funktion.
>> Und lassen Sie uns sagen, dass wir laufen John durch diese Hash-Funktion
und es spuckt 4.
Nun, das ist, wo wir sind gehen, um John setzen wollen.
Wir möchten John in Feldposition setzen 4, denn wenn wir hash John again--
sagen wir mal später werden wir wollen zu suchen und anzusehen
wenn John in dieser Hash existiert table-- alles, was wir tun müssen,
wird es durch den gleichen Hash laufen Funktion, bekommen die Zahl 4,
und in der Lage, John sofort in unserem Datenstruktur.
Das ist ziemlich gut.
>> Nehmen wir an, wir tun dies, wieder, wir wollen Paul Hash.
Wir wollen Paul hinzufügen in diesen Hash-Tabelle.
Nehmen wir an, dass wir dieses Mal laufen Paul durch die Hash-Funktion,
die Hash-Code, der generiert wird, ist 6.
Nun können wir Paul setzen in dem Feld Speicherort 6.
Und wenn wir brauchen, um sich schauen, ob Paul ist in diesem Hash-Tabelle,
alles, was wir tun müssen, ist laufen Paul durch die Hash-Funktion wieder
und wir werden 6 wieder heraus.
>> Und dann haben wir nur schauen bei Matrixort 6.
Ist Paul da?
Wenn ja, ist er in der Hash-Tabelle.
Ist Paul nicht da ist?
Er ist nicht in der Hash-Tabelle.
Es ist ziemlich einfach.
>> Nun, wie Sie eine Hash-Funktion zu definieren?
Nun gibt es wirklich keine Begrenzung für die Anzahl der möglichen Hash-Funktionen.
In der Tat gibt es eine Reihe von wirklich, wirklich guten im Internet.
Es gibt eine Reihe von wirklich, wirklich schlecht, die auf dem Internet.
Es ist auch recht einfach um ein schlechtes schreiben.
>> Also, was macht einen guten Hash-Funktion, nicht wahr?
Nun eine gute Hash-Funktion sollte verwenden Sie nur die Daten, die gehasht,
und all die Daten gehasht.
So haben wir nicht verwenden möchten anything-- wir nichts übernehmen
anderes als die Daten.
Und wir wollen, um alle Daten zu verwenden.
Wir wollen nicht einfach nur ein Stück verwenden davon wollen wir alle es zu benutzen.
Eine Hash-Funktion sollte auch deterministisch sein.
Was bedeutet das?
Nun, es bedeutet, dass jedes Mal, wenn wir übergeben Sie die exakt gleiche Stück von Daten
in die Hash-Funktion haben wir immer Sie erhalten die gleiche Hash-Code aus.
Wenn ich übergeben John in die Hash-Funktion Ich steige aus 4.
Ich sollte in der Lage, das zu tun 10000 Zeiten, und ich werde immer 4.
Also keine Zufallszahlen effektiv finden Sie in unserer Hash einbezogen werden tables--
in unserer Hash-Funktionen.
>> Eine Hash-Funktion sollte auch gleichmäßig zu verteilen Daten.
Wenn jedes Mal, wenn Daten über die laufen Hash-Funktion Sie den Hash-Code 0 zu erhalten,
das ist wahrscheinlich nicht so toll, nicht wahr?
Sie wollen wahrscheinlich groß eine Reihe von Hash-Codes.
Auch Dinge können verteilt werden während der gesamten Tabelle.
Auch wäre es toll, wenn wirklich ähnliche Daten, wie John und Jonathan,
vielleicht wurden verteilt, um zu wiegen verschiedenen Orten in der Hash-Tabelle.
Das wäre ein schöner Vorteil.
>> Hier ist ein Beispiel einer Hash-Funktion.
Ich schrieb diesen einen früher.
Es ist nicht ein besonders gute Hash-Funktion
aus Gründen, die nicht wirklich zu tun tragen gehen in diesem Augenblick.
Aber wissen Sie, was ist denn hier los?
Es scheint, als würden wir eine Variable deklarieren genannte Summe, und wenn er gleich 0.
Und dann anscheinend bin ich etwas zu tun, so lange, wie strstr [j] ist ungleich
0 Backslash.
Was soll ich denn da?
>> Dies ist im Grunde nur eine andere Art der Implementierung [? strl?]
und Erfassen, wann haben Sie erreicht das Ende der Zeichenfolge.
So dass ich nicht wirklich haben, um Berechnung der Länge der Zeichenfolge,
Ich bin einfach nur mit, wenn ich auf die Backslash 0 Zeichen Ich weiß,
Ich habe das Ende des Strings erreicht.
Und dann werde ich halten Durchlaufen dieser Zeichenkette,
Hinzufügen strstr [j], um zu der Summe, und dann Ende des Tages werde Summe mod zurück
HASH_MAX.
>> Grundsätzlich sind alle diese Hash- Funktion macht, ist Zugabe von bis
alle ASCII-Werte meine Schnur, und dann ist es
Rückkehr einige hashcode von HASH_MAX modded.
Es ist wahrscheinlich die Größe meiner Array, nicht wahr?
Ich will nicht zu sein, immer Hash Codes, wenn meine Array der Größe 10,
Ich will nicht zu sein, immer aus Hash-Codes 11, 12,
13, kann ich nicht die Dinge in diejenigen Stellen des Arrays,
das wäre illegal.
Ich würde einen Segmentation Fault zu leiden.
>> Nun, hier ist eine weitere schnelle beiseite.
Im Allgemeinen sind Sie wahrscheinlich nicht gehen möchten Sie Ihre eigenen Hash-Funktionen zu schreiben.
Es ist eigentlich ein bisschen eine Kunst, keine Wissenschaft.
Und es gibt eine Menge, die in sie geht.
Das Internet, wie ich schon sagte, ist voll wirklich gute Hash-Funktionen,
und Sie sollten das Internet zu bedienen Hash-Funktionen zu finden, weil es wirklich
nur irgendwie eine unnötige Verschwendung von Zeit Ihre eigenen zu erstellen.
>> Sie können einfache diejenigen zu schreiben für Testzwecke.
Aber wenn Sie tatsächlich sind los starten Hashing von Daten und Speicherung
in eine Hash-Tabelle Sie wahrscheinlich gehen zu wollen,
um eine Funktion, die erzeugt wurde, verwenden für Sie besteht, dass über das Internet.
Wenn Sie nur sicher sein, Ihre Quellen zu zitieren.
Es gibt keinen Grund, plagiieren hier nichts.
>> Die Informatik-Community ist auf jeden Fall wachsen, und wirklich Werte
Open Source, und es ist wirklich wichtig, Ihre Quellen zu zitieren, damit die Menschen
kann Zuschreibung für erhalten die Arbeit, die sie
tut, um die Nutzen der Gemeinschaft.
Also immer sure-- sein und nicht nur für die Hash-
Funktionen, aber in der Regel, wenn Sie verwenden Code von einer externen Quelle,
immer anführen Ihre Quelle.
Namentlich an die Person, tat etwas von der Arbeit, so dass Sie nicht haben, um.
>> OK also lassen Sie uns dies überdenken Hash-Tabelle für eine Sekunde.
Dies ist, wo wir aufge ab, nachdem wir einge
Johannes und Paulus in diesen Hash-Tabelle.
Haben Sie sich hier ein Problem?
Sie konnten zwei zu sehen.
Aber vor allem, sind Sie sehen Sie dieses mögliche Problem?
>> Was, wenn ich hash Ringo, und es stellt sich heraus, daß nach der Verarbeitung
daß Daten durch die Hash-Funktion Ringo generiert auch die Hash-Code 6.
Ich habe schon bei bekamen Daten hashcode-- Matrixort 6.
So ist es wahrscheinlich zu sein, ein wenig ein Problem für mich jetzt, nicht wahr?
>> Wir nennen dies eine Kollision.
Und die Kollision auftritt, wenn zwei Stücke von Daten durch den gleichen Hash ausgeführt
Funktion ergeben den gleichen Hash-Code.
Vermutlich wollen wir noch beide bekommen Stücke von Daten in die Hash-Tabelle,
sonst wären wir nicht laufen Ringo werden beliebig durch die Hash-Funktion.
Wir wollen, vermutlich, um zu bekommen Ringo in diesem Array.
>> Wie können wir es zu tun aber, wenn er und Paul sowohl Ausbeute hashcode 6?
Wir wollen nicht, um Paul zu überschreiben, wir wollen, dass Paulus an dabei sein.
Also müssen wir einen Weg finden, um zu bekommen Elemente in die Hash-Tabelle,
noch unsere schnelle bewahrt Einsetzen und kurzen Blick auf.
Und eine Möglichkeit, damit umzugehen ist, tun etwas namens lineares Sondieren.
>> Mit dieser Methode, wenn wir eine Kollision, nun, was sollen wir tun?
Nun, wir nicht setzen ihn in Matrixort 6, oder was auch immer Hashcode generiert wurde,
lassen wir ihn in hashcode plus 1.
Und wenn das volle Lassen Sie uns setzte ihn in hashcode plus 2.
Der Vorteil dieses Wesen, wenn er nicht genau, wo wir denken, dass er,
und wir haben die Suche zu starten, vielleicht haben wir nicht zu weit zu gehen.
Vielleicht werden wir nicht haben, um zu suchen alle n Elemente der Hash-Tabelle.
Vielleicht haben wir, um zu suchen ein paar von ihnen.
>> Und so sind wir immer noch in Richtung tendiert dass die durchschnittlichen Fall die Nähe zu 1 vs
in der Nähe von n, so vielleicht das wird funktionieren.
Also mal sehen, wie diese vielleicht in Wirklichkeit heraus zu arbeiten.
Und mal sehen, ob wir vielleicht erkennen kann das Problem, das hier auftreten können.
>> Sagen wir, wir hash Bart.
So, jetzt werden wir einen neuen Satz laufen von Strings durch die Hash-Funktion,
und wir laufen Bart durch die Hash- Funktion, bekommen wir hashcode 6.
Wir werfen einen Blick sehen wir 6 leer, so können wir Bart dort setzen.
>> Jetzt hash wir Lisa, und dass erzeugt auch hashcode 6.
Nun gut, dass wir mit diesem Linearsondierungsverfahren beginnen wir bei der 6,
sehen wir, dass 6 voll ist.
Wir können nicht Lisa in 6.
Also, wo gehen wir hin?
Lassen Sie uns bis 7 gehen.
7 ist leer, so dass das funktioniert.
Also lassen wir es Lisa.
>> Jetzt hash wir Homer und wir bekommen 7.
OK gut wir wissen, dass 7 der Voll Jetzt, so dass wir nicht setzen Homer gibt.
Lassen Sie uns also bis 8 gehen.
8 zur Verfügung?
Ja, und 8 ist in der Nähe von 7, wenn ja, Wir haben die Suche sind wir zu starten
nicht gehen zu müssen, zu weit zu gehen.
Und so lassen wir Homer bei 8.
>> Jetzt hash wir Maggie und liefert 3, Gott sei Dank
wir sind in der Lage, setzen Sie einfach Maggie gibt.
Wir haben nicht zu einem zu tun Art Sondierungs dafür.
Jetzt hash wir Marge, und Marge gibt auch 6.
>> Gut 6 voll ist, 7 ist voll, 8 voll ist, 9, in Ordnung Gott sei Dank, 9 ist leer.
Ich kann Marge auf 9 gesetzt.
Schon sehen wir, dass wir beginnen um dieses Problem, in dem jetzt sind wir haben
beginnen, die Dinge Art strecken der weit weg von ihren Hash-Codes.
Und Theta von 1, dass die durchschnittlichen Bei konstant Zeit,
beginnt, ein wenig more-- erhalten beginnen, ein wenig mehr dazu neigen,
in Richtung Theta von n.
Wir fangen an, dass zu verlieren Vorteil der Hash-Tabellen.
>> Das Problem, das wir gerade gesehen haben so etwas wie Clustering.
Und was ist wirklich schlecht zu Clustering ist, dass, sobald Sie sich jetzt
zwei Elemente, die Seite sind durch Seite macht es noch wahrscheinlicher,
Sie haben die doppelte Chance, dass du gehst
um eine weitere Kollision haben mit diesem Cluster,
und der Cluster wird durch einen wachsen.
Und du wirst zu halten wächst und wächst Ihre Wahrscheinlichkeit, dass eine Kollision.
Und schließlich ist es genauso schlecht nicht Sortieren der Daten überhaupt.
>> Das andere Problem ist aber, wir noch, und so weit bis zu diesem Punkt,
Wir haben gerade eine Art gewesen zu verstehen, was eine Hash-Tabelle ist,
wir immer noch nur Platz für 10 Saiten.
Wenn wir wollen, auch weiterhin hash die Bürger von Springfield,
wir können nur in dorthin zu gelangen 10 von ihnen.
Und wenn wir es versuchen und füge eine 11. oder 12., wir haben nicht einen Platz, um sie gelegt.
Wir konnten einfach werden rund um die Spinnerei in Kreise versuchen, eine freie Stelle zu finden,
und wir vielleicht stecken in einer Endlosschleife.
>> Also diese Art der leiht dem Idee der so genannten Verkettung.
Und das ist, wohin wir gehen, um zu bringen verkettete Listen zurück in das Bild.
Was wäre, wenn statt der Speicherung von nur die Daten selbst in der Anordnung,
jedes Element der Anordnung könnte Halten Sie mehrere Stücke von Daten?
Nun, das ist nicht sinnvoll, nicht wahr?
Wir wissen, dass ein Array kann nur jedes Element eines Arrays hold--
kann nur ein Stück zu halten Daten dieses Datentyps.
>> Aber was, wenn dieser Datentyp ist eine verkettete Liste, nicht wahr?
So was, wenn jede Element der Anordnung war
ein Zeiger auf den Kopf einer verketteten Liste?
Und dann werden wir aufbauen konnten diese verkettete Listen
und wachsen sie willkürlich, da verkettete Listen ermöglichen
uns zu wachsen und schrumpfen viel mehr flexibler als ein Array tut.
So was, wenn wir heute verwenden, wir diese nutzen, oder?
Wir beginnen, diese Ketten wachsen aus diesen Positionen auf dem Array.
>> Jetzt können wir eine unendliche passen Datenmenge oder nicht unendlich,
eine willkürliche Menge an Daten in unser Hash-Tabelle
ohne jemals in Laufen das Problem der Kollision.
Wir haben ebenfalls eliminiert Clustering, indem Sie diese.
Und auch wir wissen, dass, wenn wir fügen in einer verknüpften Liste, wenn Sie sich erinnern,
aus unserem Video auf verkettete Listen, einzeln verkettete Listen und doppelt verkettete Listen,
es ist eine konstante Zeitbetrieb.
Wir sind einfach nur mit an die Front.
>> Und sehen Sie, auch wir wissen, dass Nachschlagen in einer verknüpften Liste
kann ein Problem sein, oder?
Wir haben, um durch zu suchen es von Anfang bis Ende.
Es gibt keine Zufalls Zugriff in einer verketteten Liste.
Aber wenn anstatt einer verknüpften Liste, wo eine Lookup würde O n sein,
wir haben jetzt 10 verkettete Listen, oder 1.000 verkettete Listen,
jetzt ist es O n geteilt durch 10, oder O n geteilt durch 1.000.
>> Und während wir uns unterhielten theoretisch über die Komplexität
wir Konstanten außer Acht lassen, in der realen Welt diese Dinge eigentlich egal,
Recht?
Wir werden tatsächlich feststellen, dass dies geschieht,
zu 10-mal schneller laufen, oder 1000 mal schneller
weil wir die Verteilung einer lang Kette über 1.000 kleinere Ketten.
Und so jedes Mal müssen wir suchen durch eine dieser Ketten können wir
ignorieren Sie die 999-Ketten ist uns egal zu, und suchen nur, dass man.
>> Das ist im Durchschnitt sein 1.000-mal kürzer.
Und so sind wir immer noch eine Art Stärker zur dieser Durchschnittsfall
der konstant ist Zeit, aber nur weil wir die Nutzung
Division mit einem riesigen konstanten Faktor.
Mal sehen, wie könnte dies tatsächlich aussehen though.
Das war also die Hash-Tabelle wir hatten bevor wir eine Hash-Tabelle erklärt, dass
war die Speicherung von 10 Saiten.
Wir gehen nicht, um mehr tun.
Wir wissen bereits, die Grenzen dieser Methode.
Jetzt geht unsere Hash-Tabelle zu sein ein Array von 10 Knoten, Zeiger
In den Köpfen der verknüpften Listen.
>> Und jetzt ist es null.
Jede dieser 10-Pointer ist null.
Es gibt nichts in unserem Hash-Tabelle im Augenblick.
>> Lassen Sie uns jetzt beginnen, einige setzen Dinge in dieser Hash-Tabelle.
Und lassen Sie uns sehen, wie diese Methode wird uns zugute kommen ein wenig.
Lassen Sie uns nun Hash Joey.
Wir werden die Zeichenfolge Joey durchlaufen eine Hash-Funktion und kehren wir zurück 6.
Nun, was machen wir jetzt?
>> Nun arbeitet nun mit verketteten Listen, wir sind nicht die Arbeit mit Arrays.
Und wenn wir arbeiten mit verknüpften Listen wir
wissen, wir brauchen, um dynamisch zu starten Zuweisen von Speicherplatz und Gebäudeketten.
Das ist eine Art how-- das sind die Kern Elemente des Aufbaus einer verketteten Liste.
Lassen Sie uns also dynamisch Speicherplatz zuweisen für Joey,
und dann lassen Sie ihn in den der Kette.
>> So, jetzt schauen, was wir getan haben.
Wenn wir hash Joey wir haben den Hashcode 6.
Jetzt wird der Zeiger auf Array Lage 6 weist auf die Spitze einer verknüpften Liste,
und jetzt ist es die einzige Element einer verketteten Liste.
Und der Knoten dadurch gekennzeichnet, dass verknüpfte Liste ist Joey.
>> Also, wenn wir müssen schauen Joey später, wir haben nur hash Joey wieder,
wir wieder zu bekommen, weil unsere 6 Hash-Funktion deterministisch ist.
Und dann fangen wir an der Spitze der verknüpften Liste hingewiesen
durch Feldposition 6, und wir durchlaufen kann
auf, die versuchen, Joey zu finden.
Und wenn wir unser effektiv Hash-Tabelle,
und unsere Hash-Funktion effektiv Daten gut zu verteilen,
im Durchschnitt jedes dieser verbunden Listen in jedem Array Ort
wird 1/10 der Größe, wenn wir sein musste es einfach als eine einzige riesige
verknüpfte Liste mit allem, was in ihm.
>> Wenn wir zu verteilen, dass riesige verbunden Liste über 10 verketteten Listen
Jede Liste wird 1/10 der Größe sein.
Und damit 10 Mal schneller zu durchsuchen.
Lassen Sie uns also wieder tun.
Lassen Sie uns nun Hash Ross.
>> Und lassen Sie uns sagen, Ross, wenn wir das tun, der Hash-Code wir zurück ist 2.
Nun haben wir eine dynamische Zuordnung neue Knoten legen wir Ross in diesem Knoten,
und wir sagen jetzt Matrixort 2, statt auf null,
weist auf den Kopf eines verknüpften Liste, deren einzige Knoten ist Ross.
Und wir können diesen noch einmal zu tun, die wir kann Rachel hash und erhalten hashcode 4.
malloc einen neuen Knoten, legte Rachel in der Knoten, und sagen, ein Array Ort
4 zeigt nun auf den Kopf einer verketteten Liste, deren
einzige Element passiert mit Rachel sein.
>> OK, aber was passiert, wenn wir haben eine Kollision?
Mal sehen, wie wir Kollisionen umgehen mit der separaten Verkettungsverfahren.
Lassen Sie uns hash Phoebe.
Wir bekommen die hashcode 6.
In unserem vorigen Beispiel nur waren wir Speichern der Zeichenfolgen in der Anordnung.
Dies war ein Problem.
>> Wir wollen nicht clobber Joey, und wir haben bereits
zu sehen, dass wir einige Clustering erhalten Probleme, wenn wir versuchen, Schritt
durch und Sonde.
Aber was, wenn wir nur irgendwie behandeln dies die gleiche Art und Weise, nicht wahr?
Es ist wie das Hinzufügen eines Elements auf den Kopf einer verketteten Liste.
Lassen Sie uns gerade malloc Platz für Phoebe.
>> Wir werden nächste Zeiger Phoebes Punkte sagen zur alten Leiter der verknüpften Liste,
und dann 6 Punkte, nur um die neuer Leiter der verknüpften Liste.
Und jetzt schauen, haben wir Phoebe in geändert.
Wir können nun speichern zwei Elemente mit Hash-Code 6,
und wir haben keine Probleme.
>> Das ist so ziemlich alles, gibt es, um die Verkettung.
Und Verkettung ist auf jeden Fall die Methode, die ist
gehen, um am effektivsten für Sie, wenn Sie Daten-Speicher werden in einer Hash-Tabelle.
Aber diese Kombination von Arrays und verkettete Listen
zusammen, um eine Hash-Tabelle wirklich bilden dramatisch verbessert Ihre Fähigkeit,
um große Mengen von Daten zu speichern, und sehr schnell und effizient suchen
durch diese Daten.
>> Es gibt noch eine weitere Datenstruktur gibt,
dass vielleicht sogar ein bisschen sein besser in Bezug auf Gewährleistung
dass unsere Insertion, Deletion und nachschlagen Zeiten sind noch schneller.
Und wir werden, dass in einem Video auf Versuche zu sehen.
Ich bin Doug Lloyd, ist dies CS50.