1 00:00:06,979 --> 00:00:07,479 [NOISE]. 2 00:00:07,479 --> 00:00:09,367 Vor dem Tauchen in Hash-Tabellen, lassen 3 00:00:09,367 --> 00:00:11,196 zunächst die Vor-und Nachteile von einigen bewerten 4 00:00:11,196 --> 00:00:13,202 einfacher Datenstrukturen, die mit 5 00:00:13,202 --> 00:00:14,739 Arrays. 6 00:00:14,739 --> 00:00:16,869 Daran erinnern, dass Arrays ermöglichen es uns, zu speichern 7 00:00:16,869 --> 00:00:18,644 Elemente eines einzigen Datentyp 8 00:00:18,644 --> 00:00:21,259 im Speicher zusammenhängend. 9 00:00:21,259 --> 00:00:24,115 Da jedes Element zugeordnet ist 10 00:00:24,115 --> 00:00:26,513 ein Index oder Lage, 11 00:00:26,513 --> 00:00:27,661 wir haben wahlfreien Zugriff auf alle der 12 00:00:27,661 --> 00:00:28,860 Elemente in einem Array. 13 00:00:28,860 --> 00:00:31,308 In anderen Worten, wir können jedes Element zugreifen 14 00:00:31,308 --> 00:00:33,468 in einem einzigen Schritt durch Indexieren in der 15 00:00:33,468 --> 00:00:35,112 Array. 16 00:00:35,112 --> 00:00:37,224 Dies ist eine große Sache, weil Algorithmen 17 00:00:37,224 --> 00:00:39,204 wie binäre Suche auf zufälligen hängen 18 00:00:39,204 --> 00:00:40,570 Zugang. 19 00:00:40,570 --> 00:00:43,130 Ein Nachteil von Anordnungen ist, dass ihre Größe 20 00:00:43,130 --> 00:00:44,380 befestigt ist. 21 00:00:44,380 --> 00:00:46,630 Da Arrays speichern Daten zusammenhängend in 22 00:00:46,630 --> 00:00:49,490 Speicher, müssen Sie ein Array-Größe angeben 23 00:00:49,490 --> 00:00:50,600 wenn Sie das Array deklarieren. 24 00:00:50,600 --> 00:00:53,510 Sie sind im Wesentlichen dahin, das Betriebs 25 00:00:53,510 --> 00:00:55,600 System, um den entsprechenden Betrag zu reservieren 26 00:00:55,600 --> 00:00:58,080 Speicher für die Elemente des Arrays. 27 00:00:58,080 --> 00:01:00,240 Es gibt keine Garantie, dass mehr Speicher, 28 00:01:00,240 --> 00:01:02,370 neben Ihrem Array, erhältlich sein 29 00:01:02,370 --> 00:01:03,480 für die spätere Verwendung. 30 00:01:03,480 --> 00:01:05,550 So Arrays nicht leicht wachsen. 31 00:01:05,550 --> 00:01:07,715 Daran erinnern, dass wir gelernt, auch zu verknüpften 32 00:01:07,715 --> 00:01:09,630 Listen, die wachsen können, weil ihre 33 00:01:09,630 --> 00:01:12,430 Elemente sind nicht zusammenhängend im Speicher. 34 00:01:12,430 --> 00:01:14,680 Jeder Knoten in einer verknüpften Liste enthält die 35 00:01:14,680 --> 00:01:16,620 Element, das wir speichern wollen, sowie 36 00:01:16,620 --> 00:01:18,976 ein Zeiger auf das nachfolgende Element in 37 00:01:18,976 --> 00:01:19,756 die Liste. 38 00:01:19,756 --> 00:01:22,560 Leider ist der Preis, den wir bezahlt haben 39 00:01:22,560 --> 00:01:24,945 dynamische Größe ist wahlfreien Zugriff auf 40 00:01:24,945 --> 00:01:26,460 Elemente. 41 00:01:26,460 --> 00:01:28,760 Um ein bestimmtes Element zuzugreifen, 42 00:01:28,760 --> 00:01:30,810 es ist notwendig, den gesamten Verfahrweg 43 00:01:30,810 --> 00:01:32,910 Liste, bis das gewünschte Element 44 00:01:32,910 --> 00:01:33,950 erreicht. 45 00:01:33,950 --> 00:01:36,450 Also, wenn ich mich für die Nummer 9, würde ich 46 00:01:36,450 --> 00:01:39,340 folgen Sie den Zeiger von Knoten zu Knoten, 47 00:01:39,340 --> 00:01:41,350 Prüfen, ob der Wert jedes Knotens 48 00:01:41,350 --> 00:01:42,584 gleich 9 ist. 49 00:01:42,584 --> 00:01:46,303 Als solcher, im schlimmsten Fall, nachschlagen ist 50 00:01:46,303 --> 00:01:48,400 O (n), was wenig effizient ist. 51 00:01:49,690 --> 00:01:51,630 Können wir besser als O (n), während noch 52 00:01:51,630 --> 00:01:53,470 so dass unsere Datenstruktur zu über wachsen 53 00:01:53,470 --> 00:01:54,560 Zeit? 54 00:01:54,560 --> 00:01:56,810 Hash-Tabellen bieten eine Lösung. 55 00:01:56,810 --> 00:01:58,730 Hash-Tabellen verwendet werden, wenn schnelle 56 00:01:58,730 --> 00:02:00,820 Einfügen, Löschen und Suchen von 57 00:02:00,820 --> 00:02:01,910 Elemente Priorität. 58 00:02:01,910 --> 00:02:05,500 In der Theorie, Insertion, Deletion und Lookup 59 00:02:05,500 --> 00:02:07,275 kann sogar in ständiger erreicht werden 60 00:02:07,275 --> 00:02:08,890 Zeit. 61 00:02:08,890 --> 00:02:11,120 Also, was ist eine Hash-Tabelle überhaupt? 62 00:02:11,120 --> 00:02:13,170 Eine Hash-Tabelle ist nur ein Array verbunden 63 00:02:13,170 --> 00:02:14,940 mit einer Funktion, die wir den Hash nennen 64 00:02:14,940 --> 00:02:15,440 -Funktion. 65 00:02:16,440 --> 00:02:18,610 Die Hash-Funktion nimmt ein Stück von Daten 66 00:02:18,610 --> 00:02:20,778 als Eingang, wir nennen dies einen Schlüssel, und 67 00:02:20,778 --> 00:02:23,700 gibt eine ganze Zahl ist, gemeinhin 68 00:02:23,700 --> 00:02:24,895 als Hashwert. 69 00:02:24,895 --> 00:02:28,810 Der Hash-Wert bildet unser Schlüssel zu einem 70 00:02:28,810 --> 00:02:30,840 bestimmten Index in der Hash-Tabelle. 71 00:02:32,080 --> 00:02:34,330 Sie würden zunächst die Hash-Funktion verwenden, um 72 00:02:34,330 --> 00:02:36,410 festzustellen, wo in der Hash-Tabelle, um 73 00:02:36,410 --> 00:02:38,430 speichern Sie eine bestimmte Taste. 74 00:02:38,430 --> 00:02:41,030 Später können Sie den gleichen Hash-Funktion verwenden möchten 75 00:02:41,030 --> 00:02:42,950 zu bestimmen, wo in der Hash-Tabelle, um 76 00:02:42,950 --> 00:02:45,010 Suche nach einem bestimmten Schlüssel. 77 00:02:45,010 --> 00:02:47,190 Aus diesem Grund ist es entscheidend, dass ein Hash 78 00:02:47,190 --> 00:02:49,840 Funktion verhält sich konsequent und Ausgänge 79 00:02:49,840 --> 00:02:53,130 die gleichen Hash-Wert für identische Schlüssel. 80 00:02:53,130 --> 00:02:54,970 Wissen Sie, dass Hash-Tabellen können verwendet werden, 81 00:02:54,970 --> 00:02:56,310 Speicherdaten aller Arten. 82 00:02:56,310 --> 00:02:58,330 Aber die Dinge zu vereinfachen, werden wir uns auf 83 00:02:58,330 --> 00:02:59,830 Saiten für jetzt. 84 00:02:59,830 --> 00:03:01,630 Hier ist eine einfache Hash-Funktion für Strings. 85 00:03:03,570 --> 00:03:05,590 Dieser Hash-Funktion berechnet einen Hash- 86 00:03:05,590 --> 00:03:07,410 Funktion basierend auf dem ersten Buchstaben des 87 00:03:07,410 --> 00:03:07,910 Taste. 88 00:03:09,090 --> 00:03:11,300 "Apfel" mit dem Buchstaben "A", so dass es 89 00:03:11,300 --> 00:03:13,200 mit Index 0 in der Hash-Tabelle zugeordnet. 90 00:03:14,270 --> 00:03:17,402 Ebenso ist "Banane" zu Index 1 zugeordnet, 91 00:03:17,402 --> 00:03:19,829 und "Katze" auf Index 2 abgebildet. 92 00:03:21,750 --> 00:03:23,790 Wenn ein Freund fragt, ob das Wort "Hund" ist in 93 00:03:23,790 --> 00:03:26,150 die Tabelle, wir Eingang "Hund" in die Hash- 94 00:03:26,150 --> 00:03:28,390 Funktion, die folgende Ausgabe ein Hash-Wert 95 00:03:28,390 --> 00:03:29,790 3. 96 00:03:29,790 --> 00:03:33,150 Da "Hund" ist nicht am Index 3 gespeichert sind, wir 97 00:03:33,150 --> 00:03:35,330 kann mit Zuversicht sagen, dass "Hund" ist nicht 98 00:03:35,330 --> 00:03:36,340 in der Tabelle, 99 00:03:36,340 --> 00:03:38,260 obwohl wir nur überprüft, eine der 100 00:03:38,260 --> 00:03:40,120 Hash-Tabelle 26 Indizes. 101 00:03:42,170 --> 00:03:44,280 Zeit, einen Schraubenschlüssel in die Dinge zu werfen. 102 00:03:44,280 --> 00:03:46,130 Was, wenn wir zu "Ameise" in die gespeichert werden soll 103 00:03:46,130 --> 00:03:47,820 Tabelle als gut? 104 00:03:47,820 --> 00:03:51,730 "Ant"-Hashes zu Index 0, so wie "Apfel" hat. 105 00:03:51,730 --> 00:03:53,890 Dies ist ein Beispiel einer Kollision, die 106 00:03:53,890 --> 00:03:56,419 Ergebnis von zwei Hash-Schlüssel zu der gleichen 107 00:03:56,419 --> 00:03:57,080 Index. 108 00:03:58,140 --> 00:04:00,040 Selbst wenn Ihr Hash-Tabelle ist größer als 109 00:04:00,040 --> 00:04:01,980 Ihre Daten gesetzt, und Sie haben eine gute gewählt haben 110 00:04:01,980 --> 00:04:03,060 Hash-Funktion, 111 00:04:03,060 --> 00:04:04,560 Sie müssen noch einen Plan für den Umgang mit 112 00:04:04,560 --> 00:04:06,420 Kollisionen, ob und wann sie entstehen. 113 00:04:07,440 --> 00:04:09,810 Sprechen wir über die Vor-und Nachteile von zwei 114 00:04:09,810 --> 00:04:12,360 gemeinsame Methoden für die Lösung von Kollisionen: 115 00:04:12,360 --> 00:04:15,230 lineare Sondieren und separate Verkettung. 116 00:04:15,230 --> 00:04:17,430 Bei linearen Sondieren, wenn ein Schlüssel-Hashes zu 117 00:04:17,430 --> 00:04:19,340 der gleiche Index wie der zuvor gespeicherten 118 00:04:19,340 --> 00:04:21,840 Schlüssel, es den nächsten verfügbaren zugeordnet ist 119 00:04:21,840 --> 00:04:22,862 Schlitz in dem Tisch. 120 00:04:22,862 --> 00:04:27,353 Also, "ant" jetzt bei Index 3 gespeichert, da 121 00:04:27,353 --> 00:04:30,850 Indizes 0, 1 und 2 wurden bereits im Einsatz. 122 00:04:32,780 --> 00:04:34,610 Und wenn wir versuchen, ein Geschäft, das dritte Wort 123 00:04:34,610 --> 00:04:36,410 mit dem Buchstaben "A", ist es zugewiesen 124 00:04:36,410 --> 00:04:41,263 mit Index 4, da Indizes 0, 1, 2 und 3 125 00:04:41,263 --> 00:04:42,530 sind voll. 126 00:04:42,530 --> 00:04:44,300 Wie Sie auch aus diesem einfachen sehen können 127 00:04:44,300 --> 00:04:46,580 Beispielsweise, wenn eine Kollision auftritt, 128 00:04:46,580 --> 00:04:48,400 Chancen deutlich erhöhen, dass 129 00:04:48,400 --> 00:04:50,370 weitere Kollision in demselben auftreten 130 00:04:50,370 --> 00:04:51,630 Bereich. 131 00:04:51,630 --> 00:04:53,530 Dies wird als Clustering, und es ist ein 132 00:04:53,530 --> 00:04:56,200 gravierenden Nachteil an lineare Sondieren. 133 00:04:56,200 --> 00:04:59,240 Außerdem Worst-Case-Insertion, Deletion, 134 00:04:59,240 --> 00:05:02,008 und Lookup Zeiten haben sich zu O (n) übertragen, 135 00:05:02,008 --> 00:05:04,200 wie der nächste verfügbare Slot haben könnte 136 00:05:04,200 --> 00:05:06,225 möglicherweise bereits der letzte Schlitz in dem Tisch. 137 00:05:06,225 --> 00:05:09,210 Vielleicht separaten Verkettung eine mehr bieten 138 00:05:09,210 --> 00:05:10,220 überzeugende Lösung. 139 00:05:10,220 --> 00:05:13,060 In der separaten Verkettung Modell, die Hash- 140 00:05:13,060 --> 00:05:14,930 Tabelle tatsächlich ein Array von Zeigern auf 141 00:05:14,930 --> 00:05:16,220 verkettete Listen. 142 00:05:16,220 --> 00:05:18,350 Wenn eine Kollision auftritt, kann der Schlüssel 143 00:05:18,350 --> 00:05:20,760 in konstanter Zeit an der Spitze der einge 144 00:05:20,760 --> 00:05:22,270 die entsprechenden verlinkten Liste. 145 00:05:23,420 --> 00:05:25,310 Was passiert nun, wenn wir die Suche nach "apple" 146 00:05:25,310 --> 00:05:26,900 in der Hash-Tabelle? 147 00:05:26,900 --> 00:05:28,940 Im schlimmsten Fall müssen wir durchqueren die 148 00:05:28,940 --> 00:05:32,530 gesamten verketteten Liste, beginnend bei Index 0. 149 00:05:32,530 --> 00:05:34,210 Das Worst-Case-Lookup-Zeit für einen Hash- 150 00:05:34,210 --> 00:05:35,890 Tabelle, die getrennte Verkettung verwendet, ist 151 00:05:35,890 --> 00:05:38,580 Daher O (n / k), wobei k die 152 00:05:38,580 --> 00:05:39,687 Größe der Hash-Tabelle. 153 00:05:39,687 --> 00:05:42,940 Warten Sie eine Sekunde, k ist eine Konstante. 154 00:05:42,940 --> 00:05:46,280 Also O (n / k) ist wirklich nur O (n), 155 00:05:46,280 --> 00:05:47,940 die das Worst-Case-Lookup war Zeit für 156 00:05:47,940 --> 00:05:49,320 eine verkettete Liste. 157 00:05:49,320 --> 00:05:50,770 Haben wir wirklich durch alle gegangen 158 00:05:50,770 --> 00:05:52,370 Mühe des Lernens über Hash-Tabellen 159 00:05:52,370 --> 00:05:54,927 nur um wieder dort landen, wo wir angefangen haben? 160 00:05:54,927 --> 00:05:56,975 Dies kann der Fall sein, von einem theoretischen 161 00:05:56,975 --> 00:05:59,087 Perspektive, aber in der realen Welt, 162 00:05:59,087 --> 00:06:01,199 O (n / k) konnte eine große Verbesserung gegenüber sein 163 00:06:01,199 --> 00:06:03,257 O (n). 164 00:06:03,257 --> 00:06:05,687 Betrachten Sie es mal so: davon ausgehen, dass k 165 00:06:05,687 --> 00:06:08,360 10 - würden Sie lieber warten 100 Sekunden 166 00:06:08,360 --> 00:06:11,076 oder 100 / k? 167 00:06:11,076 --> 00:06:13,252 10 Sekunden nach Microsoft Word zu beenden 168 00:06:13,252 --> 00:06:15,608 Rechtschreibprüfung Ihres Dokuments. 169 00:06:15,608 --> 00:06:17,368 Wie Sie gerade gesehen haben, lösen Kollisionen 170 00:06:17,368 --> 00:06:19,018 bringt eine Art von linearen Suche oder 171 00:06:19,018 --> 00:06:20,558 eine andere, die Dinge verlangsamt 172 00:06:20,558 --> 00:06:23,280 erheblich. 173 00:06:23,280 --> 00:06:25,470 Daher sollten Sie einen Hash wählen 174 00:06:25,470 --> 00:06:27,470 Funktion, die die Chance minimiert 175 00:06:27,470 --> 00:06:29,170 Kollisionen in den ersten Platz auftreten. 176 00:06:30,540 --> 00:06:32,120 Hier sind einige Eigenschaften der gute Hash- 177 00:06:32,120 --> 00:06:33,400 Funktionen im Auge zu behalten. 178 00:06:34,610 --> 00:06:36,590 Eine gute Hash-Funktion nutzen sollten 179 00:06:36,590 --> 00:06:38,830 Alle Informationen, die von einem bestimmten Schlüssel bereitgestellt 180 00:06:38,830 --> 00:06:40,890 um die Anzahl von zu maximieren 181 00:06:40,890 --> 00:06:42,960 Hash-Werte möglich. 182 00:06:42,960 --> 00:06:45,540 Zum Beispiel, wenn wir zwei Strings, "cat" 183 00:06:45,540 --> 00:06:47,980 und "Raupe", würden wir wollen, dass sie hash 184 00:06:47,980 --> 00:06:50,190 zu verschiedenen Orten auf dem Tisch. 185 00:06:50,190 --> 00:06:52,410 Wenn eine Hash-Funktion nur berücksichtigte 186 00:06:52,410 --> 00:06:54,860 die ersten ein, zwei oder sogar drei Buchstaben 187 00:06:54,860 --> 00:06:57,290 der Saiten, würde eine Kollision auftreten, 188 00:06:57,290 --> 00:06:58,970 da beide Wörter beginnen mit dem gleichen 189 00:06:58,970 --> 00:06:59,560 drei Buchstaben. 190 00:07:01,110 --> 00:07:03,100 Hash-Werte sollten gleichmäßig verteilt werden 191 00:07:03,100 --> 00:07:04,790 in der Hash-Tabelle. 192 00:07:04,790 --> 00:07:06,300 Dadurch wird die Länge der verlinkten reduzieren 193 00:07:06,300 --> 00:07:08,050 Listen sollten Kollisionen auftreten. 194 00:07:09,390 --> 00:07:11,490 Es ist auch ein gutes Zeichen, wenn Ihr Hash-Wert 195 00:07:11,490 --> 00:07:13,600 ist in der Lage sehr unterschiedlich 196 00:07:13,600 --> 00:07:15,660 Hash-Werte für ähnliche Tasten, 197 00:07:15,660 --> 00:07:17,250 wodurch Kollisionen viel weniger wahrscheinlich. 198 00:07:18,420 --> 00:07:21,110 Unser Ziel ist es schnelle Einfügen, Löschen, 199 00:07:21,110 --> 00:07:22,100 und Lookup. 200 00:07:22,100 --> 00:07:24,060 Die Hash-Funktion spielt eine entscheidende Rolle bei der 201 00:07:24,060 --> 00:07:25,520 jeder dieser Prozesse und werden 202 00:07:25,520 --> 00:07:26,735 sehr häufig genannt. 203 00:07:26,735 --> 00:07:29,620 Stellen Sie daher sicher, dass es nur sehr beschäftigt 204 00:07:29,620 --> 00:07:32,160 einfache, schnelle Vorgänge zu minimieren Lauf 205 00:07:32,160 --> 00:07:33,360 Zeit. 206 00:07:33,360 --> 00:07:34,560 Ich hoffe, dass Sie diese kurze genossen haben 207 00:07:34,560 --> 00:07:36,540 Einführung in Hash-Tabellen. 208 00:07:36,540 --> 00:07:41,189 Mein Name ist Lauren, und das ist CS50.