1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:01,900
[Musikwiedergabe]

3
00:00:01,900 --> 00:00:05,710

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Jetzt haben Sie
wissen viel über Arrays,

5
00:00:09,150 --> 00:00:11,610
und Sie wissen viel über verkettete Listen.

6
00:00:11,610 --> 00:00:13,650
Und wir haben das zu diskutieren
Vor-und Nachteile, wir haben

7
00:00:13,650 --> 00:00:16,620
diskutiert, die Listen verbunden
kann größer und kleiner werden,

8
00:00:16,620 --> 00:00:18,630
aber sie nehmen mehr Größe.

9
00:00:18,630 --> 00:00:22,359
Arrays sind viel einfacher zu
verwenden, aber sie sind restriktiv, so viel

10
00:00:22,359 --> 00:00:24,900
wie wir haben, um die Größe festgelegt
das Array zu Beginn

11
00:00:24,900 --> 00:00:26,910
und dann werden wir mit ihm stecken.

12
00:00:26,910 --> 00:00:30,470
>> Aber das ist, wir haben ziemlich viel
alle unsere Themen erschöpft

13
00:00:30,470 --> 00:00:33,040
über verkettete Listen und Arrays.

14
00:00:33,040 --> 00:00:34,950
Oder wir haben?

15
00:00:34,950 --> 00:00:37,720
Vielleicht können wir etwas tun,
noch kreativer.

16
00:00:37,720 --> 00:00:40,950
Und diese Art von leiht
der Gedanke einer Hashtabelle.

17
00:00:40,950 --> 00:00:46,680
>> So in einer Hash-Tabelle, wir werden versuchen,
kombinieren ein Array mit einer verketteten Liste.

18
00:00:46,680 --> 00:00:49,520
Wir werden die Vorteile zu nehmen
des Arrays, wie Direktzugriffs,

19
00:00:49,520 --> 00:00:53,510
in der Lage zu gehen, nur um Array
Element 4 bzw. Array-Element 8

20
00:00:53,510 --> 00:00:55,560
ohne über laufen.

21
00:00:55,560 --> 00:00:57,260
Das ist ziemlich schnell, nicht wahr?

22
00:00:57,260 --> 00:01:00,714
>> Aber wir wollen auch, um unsere Daten
Struktur in der Lage, zu wachsen und schrumpfen.

23
00:01:00,714 --> 00:01:02,630
Wir brauchen nicht, wissen wir nicht
möchte eingeschränkt werden.

24
00:01:02,630 --> 00:01:04,588
Und wir in der Lage sein wollen,
hinzufügen und alles zu entfernen

25
00:01:04,588 --> 00:01:08,430
sehr leicht, die, wenn Sie sich erinnern,
ist sehr komplex mit einer Reihe.

26
00:01:08,430 --> 00:01:11,650
Und wir können diesen Aufruf
neue Sache eine Hash-Tabelle.

27
00:01:11,650 --> 00:01:15,190
>> Und wenn es richtig umgesetzt,
wir Art der Einnahme

28
00:01:15,190 --> 00:01:18,150
die Vorteile der beiden Daten
Strukturen Sie bereits gesehen haben,

29
00:01:18,150 --> 00:01:19,880
Arrays und verkettete Listen.

30
00:01:19,880 --> 00:01:23,070
Einsetzen kann zu starten
neigen Theta von 1.

31
00:01:23,070 --> 00:01:26,207
Theta wir nicht wirklich diskutiert,
aber Theta ist nur der Durchschnittsfall,

32
00:01:26,207 --> 00:01:27,540
was tatsächlich passieren wird.

33
00:01:27,540 --> 00:01:29,680
Sie sind nicht immer zu
haben den schlimmsten Fall

34
00:01:29,680 --> 00:01:32,555
und du bist nicht immer gehen zu müssen,
Im besten Fall, so was ist

35
00:01:32,555 --> 00:01:33,900
die durchschnittliche Szenario?

36
00:01:33,900 --> 00:01:36,500
>> Gut eine durchschnittliche Insertion
in eine Hashtabelle

37
00:01:36,500 --> 00:01:39,370
können Sie beginnen, in der Nähe von konstanter Zeit zu bekommen.

38
00:01:39,370 --> 00:01:41,570
Und Löschen erhalten können
schließen, um konstante Zeit.

39
00:01:41,570 --> 00:01:44,440
Und Lookup bekommen können
schließen, um konstante Zeit.

40
00:01:44,440 --> 00:01:48,600
That's-- wir eine Daten nicht
Struktur noch, dass das tun können,

41
00:01:48,600 --> 00:01:51,180
so dass diese bereits klingt
wie eine ziemlich große Sache.

42
00:01:51,180 --> 00:01:57,010
Wir haben wirklich entschärft die
Nachteile jeder für sich allein.

43
00:01:57,010 --> 00:01:59,160
>> Um diese Leistung zu erhalten
Upgrade aber wir

44
00:01:59,160 --> 00:02:03,580
müssen überdenken, wie wir hinzufügen
Daten in der Struktur.

45
00:02:03,580 --> 00:02:07,380
Insbesondere wollen wir die
Daten selbst, uns zu sagen

46
00:02:07,380 --> 00:02:09,725
wo es in der Struktur zu gehen.

47
00:02:09,725 --> 00:02:12,850
Und wenn wir dann zu sehen, ob es in
die Struktur, wenn wir brauchen, um es zu finden,

48
00:02:12,850 --> 00:02:16,610
wollen wir die Daten anschauen
immer in der Lage zu sein, wirksam,

49
00:02:16,610 --> 00:02:18,910
unter Verwendung der Daten, zufällig darauf zugreifen.

50
00:02:18,910 --> 00:02:20,700
Gerade indem Sie das
Daten, die wir haben sollten

51
00:02:20,700 --> 00:02:25,890
eine Vorstellung davon, wo wir genau sind
werde es in der Hash-Tabelle zu finden.

52
00:02:25,890 --> 00:02:28,770
>> Nun ist die Kehrseite einer Hash-
Tabelle ist, dass sie wirklich

53
00:02:28,770 --> 00:02:31,770
ziemlich schlecht bei der Bestellung oder Sortieren von Daten.

54
00:02:31,770 --> 00:02:34,970
Und in der Tat, wenn Sie beginnen
, sie zu benutzen, um zu bestellen oder sort

55
00:02:34,970 --> 00:02:37,990
Daten, die Sie all das zu verlieren,
Vorteile, die Sie zuvor

56
00:02:37,990 --> 00:02:40,710
hatte in Bezug auf Einfügen und Löschen.

57
00:02:40,710 --> 00:02:44,060
Die Zeit näher an
Theta von n, und wir haben im Grunde

58
00:02:44,060 --> 00:02:45,530
in einer verknüpften Liste zurückgebildet.

59
00:02:45,530 --> 00:02:48,850
Und so haben wir den Hash verwenden möchten nur
Tabellen, wenn wir nicht kümmern

60
00:02:48,850 --> 00:02:51,490
ob Daten sortiert.

61
00:02:51,490 --> 00:02:54,290
Für den Kontext, in dem
Sie werden sie in CS50 verwenden

62
00:02:54,290 --> 00:02:58,900
Sie wahrscheinlich nicht kümmern
dass die Daten sortiert.

63
00:02:58,900 --> 00:03:03,170
>> So eine Hash-Tabelle ist eine Kombination
aus zwei verschiedenen Stücken

64
00:03:03,170 --> 00:03:04,980
mit denen wir vertraut sind.

65
00:03:04,980 --> 00:03:07,930
Die erste ist eine Funktion, die
wir in der Regel rufen Sie eine Hash-Funktion.

66
00:03:07,930 --> 00:03:11,760
Und das Hash-Funktion, um gehen
Rück etwas nicht negative Ganzzahl, die

67
00:03:11,760 --> 00:03:14,870
wir in der Regel einen Hash-Code aufrufen, OK?

68
00:03:14,870 --> 00:03:20,230
Das zweite Stück ist ein Array, das ist
die Speicherung von Daten des Typs wir

69
00:03:20,230 --> 00:03:22,190
will in der Datenstruktur zu platzieren.

70
00:03:22,190 --> 00:03:24,310
Wir werden uns auf das zu warten,
verknüpften Liste Element für jetzt

71
00:03:24,310 --> 00:03:27,810
und nur mit den Grundlagen eines Start
Hash-Tabelle, um Ihren Kopf um es zu bekommen,

72
00:03:27,810 --> 00:03:30,210
und dann werden wir vielleicht zu blasen
Ihre Meinung ein wenig, wenn wir

73
00:03:30,210 --> 00:03:32,920
kombinieren Arrays und Linklisten zusammen.

74
00:03:32,920 --> 00:03:35,590
>> Die Grundidee obwohl
ist, dass wir einige Daten zu nehmen.

75
00:03:35,590 --> 00:03:37,860
Wir führen, dass die Daten durch
die Hash-Funktion.

76
00:03:37,860 --> 00:03:41,980
Und so die Daten verarbeitet
und es spuckt eine Zahl, OK?

77
00:03:41,980 --> 00:03:44,890
Und dann mit dieser Nummer
wir einfach die Daten zu speichern

78
00:03:44,890 --> 00:03:48,930
wir in die gespeichert werden sollen
Anordnung an dieser Stelle.

79
00:03:48,930 --> 00:03:53,990
So zum Beispiel, haben wir vielleicht
Diese Hash-Tabelle von Strings.

80
00:03:53,990 --> 00:03:57,350
Es hat 10 Elemente in ihr, so
Wir können 10 Saiten in ihm passen.

81
00:03:57,350 --> 00:03:59,320
>> Nehmen wir an, wir John hash möchten.

82
00:03:59,320 --> 00:04:02,979
So John als die Daten, die wir einfügen wollen
in diesen Hash-Tabelle irgendwo.

83
00:04:02,979 --> 00:04:03,770
Wo stehen wir sagen?

84
00:04:03,770 --> 00:04:05,728
Auch typischerweise mit einem
Array so weit wir wahrscheinlich

85
00:04:05,728 --> 00:04:07,610
wäre es in Feldposition 0 gebracht.

86
00:04:07,610 --> 00:04:09,960
Aber jetzt haben wir diese neue Hash-Funktion.

87
00:04:09,960 --> 00:04:13,180
>> Und lassen Sie uns sagen, dass wir laufen John
durch diese Hash-Funktion

88
00:04:13,180 --> 00:04:15,417
und es spuckt 4.

89
00:04:15,417 --> 00:04:17,500
Nun, das ist, wo wir sind
gehen, um John setzen wollen.

90
00:04:17,500 --> 00:04:22,050
Wir möchten John in Feldposition setzen
4, denn wenn wir hash John again--

91
00:04:22,050 --> 00:04:23,810
sagen wir mal später werden wir
wollen zu suchen und anzusehen

92
00:04:23,810 --> 00:04:26,960
wenn John in dieser Hash existiert
table-- alles, was wir tun müssen,

93
00:04:26,960 --> 00:04:30,310
wird es durch den gleichen Hash laufen
Funktion, bekommen die Zahl 4,

94
00:04:30,310 --> 00:04:33,929
und in der Lage, John
sofort in unserem Datenstruktur.

95
00:04:33,929 --> 00:04:34,720
Das ist ziemlich gut.

96
00:04:34,720 --> 00:04:36,928
>> Nehmen wir an, wir tun dies,
wieder, wir wollen Paul Hash.

97
00:04:36,928 --> 00:04:39,446
Wir wollen Paul hinzufügen
in diesen Hash-Tabelle.

98
00:04:39,446 --> 00:04:42,070
Nehmen wir an, dass wir dieses Mal laufen
Paul durch die Hash-Funktion,

99
00:04:42,070 --> 00:04:44,600
die Hash-Code, der generiert wird, ist 6.

100
00:04:44,600 --> 00:04:47,340
Nun können wir Paul setzen
in dem Feld Speicherort 6.

101
00:04:47,340 --> 00:04:50,040
Und wenn wir brauchen, um sich schauen, ob
Paul ist in diesem Hash-Tabelle,

102
00:04:50,040 --> 00:04:53,900
alles, was wir tun müssen, ist laufen Paul
durch die Hash-Funktion wieder

103
00:04:53,900 --> 00:04:55,830
und wir werden 6 wieder heraus.

104
00:04:55,830 --> 00:04:57,590
>> Und dann haben wir nur schauen
bei Matrixort 6.

105
00:04:57,590 --> 00:04:58,910
Ist Paul da?

106
00:04:58,910 --> 00:05:00,160
Wenn ja, ist er in der Hash-Tabelle.

107
00:05:00,160 --> 00:05:01,875
Ist Paul nicht da ist?

108
00:05:01,875 --> 00:05:03,000
Er ist nicht in der Hash-Tabelle.

109
00:05:03,000 --> 00:05:05,720
Es ist ziemlich einfach.

110
00:05:05,720 --> 00:05:07,770
>> Nun, wie Sie eine Hash-Funktion zu definieren?

111
00:05:07,770 --> 00:05:11,460
Nun gibt es wirklich keine Begrenzung für die
Anzahl der möglichen Hash-Funktionen.

112
00:05:11,460 --> 00:05:14,350
In der Tat gibt es eine Reihe von wirklich,
wirklich guten im Internet.

113
00:05:14,350 --> 00:05:17,560
Es gibt eine Reihe von wirklich,
wirklich schlecht, die auf dem Internet.

114
00:05:17,560 --> 00:05:21,080
Es ist auch recht einfach
um ein schlechtes schreiben.

115
00:05:21,080 --> 00:05:23,760
>> Also, was macht einen guten
Hash-Funktion, nicht wahr?

116
00:05:23,760 --> 00:05:27,280
Nun eine gute Hash-Funktion sollte
verwenden Sie nur die Daten, die gehasht,

117
00:05:27,280 --> 00:05:29,420
und all die Daten gehasht.

118
00:05:29,420 --> 00:05:32,500
So haben wir nicht verwenden möchten anything--
wir nichts übernehmen

119
00:05:32,500 --> 00:05:35,560
anderes als die Daten.

120
00:05:35,560 --> 00:05:37,080
Und wir wollen, um alle Daten zu verwenden.

121
00:05:37,080 --> 00:05:39,830
Wir wollen nicht einfach nur ein Stück verwenden
davon wollen wir alle es zu benutzen.

122
00:05:39,830 --> 00:05:41,710
Eine Hash-Funktion sollte
auch deterministisch sein.

123
00:05:41,710 --> 00:05:42,550
Was bedeutet das?

124
00:05:42,550 --> 00:05:46,200
Nun, es bedeutet, dass jedes Mal, wenn wir
übergeben Sie die exakt gleiche Stück von Daten

125
00:05:46,200 --> 00:05:50,040
in die Hash-Funktion haben wir immer
Sie erhalten die gleiche Hash-Code aus.

126
00:05:50,040 --> 00:05:52,870
Wenn ich übergeben John in die
Hash-Funktion Ich steige aus 4.

127
00:05:52,870 --> 00:05:56,110
Ich sollte in der Lage, das zu tun 10000
Zeiten, und ich werde immer 4.

128
00:05:56,110 --> 00:06:00,810
Also keine Zufallszahlen effektiv
finden Sie in unserer Hash einbezogen werden tables--

129
00:06:00,810 --> 00:06:02,750
in unserer Hash-Funktionen.

130
00:06:02,750 --> 00:06:05,750
>> Eine Hash-Funktion sollte auch
gleichmäßig zu verteilen Daten.

131
00:06:05,750 --> 00:06:09,700
Wenn jedes Mal, wenn Daten über die laufen
Hash-Funktion Sie den Hash-Code 0 zu erhalten,

132
00:06:09,700 --> 00:06:11,200
das ist wahrscheinlich nicht so toll, nicht wahr?

133
00:06:11,200 --> 00:06:14,600
Sie wollen wahrscheinlich groß
eine Reihe von Hash-Codes.

134
00:06:14,600 --> 00:06:17,190
Auch Dinge können verteilt werden
während der gesamten Tabelle.

135
00:06:17,190 --> 00:06:23,210
Auch wäre es toll, wenn wirklich
ähnliche Daten, wie John und Jonathan,

136
00:06:23,210 --> 00:06:26,320
vielleicht wurden verteilt, um zu wiegen
verschiedenen Orten in der Hash-Tabelle.

137
00:06:26,320 --> 00:06:28,750
Das wäre ein schöner Vorteil.

138
00:06:28,750 --> 00:06:31,250
>> Hier ist ein Beispiel einer Hash-Funktion.

139
00:06:31,250 --> 00:06:33,150
Ich schrieb diesen einen früher.

140
00:06:33,150 --> 00:06:35,047
Es ist nicht ein besonders
gute Hash-Funktion

141
00:06:35,047 --> 00:06:37,380
aus Gründen, die nicht wirklich zu tun
tragen gehen in diesem Augenblick.

142
00:06:37,380 --> 00:06:41,040
Aber wissen Sie, was ist denn hier los?

143
00:06:41,040 --> 00:06:44,420
Es scheint, als würden wir eine Variable deklarieren
genannte Summe, und wenn er gleich 0.

144
00:06:44,420 --> 00:06:50,010
Und dann anscheinend bin ich etwas zu tun,
so lange, wie strstr [j] ist ungleich

145
00:06:50,010 --> 00:06:52,490
0 Backslash.

146
00:06:52,490 --> 00:06:54,870
Was soll ich denn da?

147
00:06:54,870 --> 00:06:57,440
>> Dies ist im Grunde nur eine andere
Art der Implementierung [? strl?]

148
00:06:57,440 --> 00:06:59,773
und Erfassen, wann haben Sie
erreicht das Ende der Zeichenfolge.

149
00:06:59,773 --> 00:07:02,480
So dass ich nicht wirklich haben, um
Berechnung der Länge der Zeichenfolge,

150
00:07:02,480 --> 00:07:05,640
Ich bin einfach nur mit, wenn ich auf die
Backslash 0 Zeichen Ich weiß,

151
00:07:05,640 --> 00:07:07,185
Ich habe das Ende des Strings erreicht.

152
00:07:07,185 --> 00:07:09,560
Und dann werde ich halten
Durchlaufen dieser Zeichenkette,

153
00:07:09,560 --> 00:07:15,310
Hinzufügen strstr [j], um zu der Summe, und dann
Ende des Tages werde Summe mod zurück

154
00:07:15,310 --> 00:07:16,200
HASH_MAX.

155
00:07:16,200 --> 00:07:18,700
>> Grundsätzlich sind alle diese Hash-
Funktion macht, ist Zugabe von bis

156
00:07:18,700 --> 00:07:23,450
alle ASCII-Werte
meine Schnur, und dann ist es

157
00:07:23,450 --> 00:07:26,390
Rückkehr einige hashcode
von HASH_MAX modded.

158
00:07:26,390 --> 00:07:29,790
Es ist wahrscheinlich die Größe
meiner Array, nicht wahr?

159
00:07:29,790 --> 00:07:33,160
Ich will nicht zu sein, immer Hash
Codes, wenn meine Array der Größe 10,

160
00:07:33,160 --> 00:07:35,712
Ich will nicht zu sein, immer
aus Hash-Codes 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, kann ich nicht die Dinge in
diejenigen Stellen des Arrays,

162
00:07:38,690 --> 00:07:39,790
das wäre illegal.

163
00:07:39,790 --> 00:07:42,130
Ich würde einen Segmentation Fault zu leiden.

164
00:07:42,130 --> 00:07:45,230
>> Nun, hier ist eine weitere schnelle beiseite.

165
00:07:45,230 --> 00:07:48,470
Im Allgemeinen sind Sie wahrscheinlich nicht gehen
möchten Sie Ihre eigenen Hash-Funktionen zu schreiben.

166
00:07:48,470 --> 00:07:50,997
Es ist eigentlich ein bisschen
eine Kunst, keine Wissenschaft.

167
00:07:50,997 --> 00:07:52,580
Und es gibt eine Menge, die in sie geht.

168
00:07:52,580 --> 00:07:55,288
Das Internet, wie ich schon sagte, ist voll
wirklich gute Hash-Funktionen,

169
00:07:55,288 --> 00:07:58,470
und Sie sollten das Internet zu bedienen
Hash-Funktionen zu finden, weil es wirklich

170
00:07:58,470 --> 00:08:03,230
nur irgendwie eine unnötige
Verschwendung von Zeit Ihre eigenen zu erstellen.

171
00:08:03,230 --> 00:08:05,490
>> Sie können einfache diejenigen zu schreiben
für Testzwecke.

172
00:08:05,490 --> 00:08:08,323
Aber wenn Sie tatsächlich sind los
starten Hashing von Daten und Speicherung

173
00:08:08,323 --> 00:08:10,780
in eine Hash-Tabelle Sie
wahrscheinlich gehen zu wollen,

174
00:08:10,780 --> 00:08:14,580
um eine Funktion, die erzeugt wurde, verwenden
für Sie besteht, dass über das Internet.

175
00:08:14,580 --> 00:08:17,240
Wenn Sie nur sicher sein,
Ihre Quellen zu zitieren.

176
00:08:17,240 --> 00:08:21,740
Es gibt keinen Grund,
plagiieren hier nichts.

177
00:08:21,740 --> 00:08:25,370
>> Die Informatik-Community ist
auf jeden Fall wachsen, und wirklich Werte

178
00:08:25,370 --> 00:08:28,796
Open Source, und es ist wirklich wichtig,
Ihre Quellen zu zitieren, damit die Menschen

179
00:08:28,796 --> 00:08:30,670
kann Zuschreibung für erhalten
die Arbeit, die sie

180
00:08:30,670 --> 00:08:32,312
tut, um die Nutzen der Gemeinschaft.

181
00:08:32,312 --> 00:08:34,020
Also immer sure-- sein
und nicht nur für die Hash-

182
00:08:34,020 --> 00:08:37,270
Funktionen, aber in der Regel, wenn Sie
verwenden Code von einer externen Quelle,

183
00:08:37,270 --> 00:08:38,299
immer anführen Ihre Quelle.

184
00:08:38,299 --> 00:08:43,500
Namentlich an die Person, tat
etwas von der Arbeit, so dass Sie nicht haben, um.

185
00:08:43,500 --> 00:08:46,720
>> OK also lassen Sie uns dies überdenken
Hash-Tabelle für eine Sekunde.

186
00:08:46,720 --> 00:08:48,780
Dies ist, wo wir aufge
ab, nachdem wir einge

187
00:08:48,780 --> 00:08:53,300
Johannes und Paulus in diesen Hash-Tabelle.

188
00:08:53,300 --> 00:08:55,180
Haben Sie sich hier ein Problem?

189
00:08:55,180 --> 00:08:58,410
Sie konnten zwei zu sehen.

190
00:08:58,410 --> 00:09:02,240
Aber vor allem, sind Sie
sehen Sie dieses mögliche Problem?

191
00:09:02,240 --> 00:09:06,770
>> Was, wenn ich hash Ringo, und es
stellt sich heraus, daß nach der Verarbeitung

192
00:09:06,770 --> 00:09:14,000
daß Daten durch die Hash-Funktion
Ringo generiert auch die Hash-Code 6.

193
00:09:14,000 --> 00:09:16,810
Ich habe schon bei bekamen Daten
hashcode-- Matrixort 6.

194
00:09:16,810 --> 00:09:22,000
So ist es wahrscheinlich zu sein, ein wenig
ein Problem für mich jetzt, nicht wahr?

195
00:09:22,000 --> 00:09:23,060
>> Wir nennen dies eine Kollision.

196
00:09:23,060 --> 00:09:26,460
Und die Kollision auftritt, wenn zwei
Stücke von Daten durch den gleichen Hash ausgeführt

197
00:09:26,460 --> 00:09:29,200
Funktion ergeben den gleichen Hash-Code.

198
00:09:29,200 --> 00:09:32,850
Vermutlich wollen wir noch beide bekommen
Stücke von Daten in die Hash-Tabelle,

199
00:09:32,850 --> 00:09:36,330
sonst wären wir nicht laufen Ringo werden
beliebig durch die Hash-Funktion.

200
00:09:36,330 --> 00:09:40,870
Wir wollen, vermutlich, um zu bekommen
Ringo in diesem Array.

201
00:09:40,870 --> 00:09:46,070
>> Wie können wir es zu tun aber, wenn er
und Paul sowohl Ausbeute hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Wir wollen nicht, um Paul zu überschreiben,
wir wollen, dass Paulus an dabei sein.

203
00:09:49,520 --> 00:09:52,790
Also müssen wir einen Weg finden, um zu bekommen
Elemente in die Hash-Tabelle,

204
00:09:52,790 --> 00:09:56,550
noch unsere schnelle bewahrt
Einsetzen und kurzen Blick auf.

205
00:09:56,550 --> 00:10:01,350
Und eine Möglichkeit, damit umzugehen ist,
tun etwas namens lineares Sondieren.

206
00:10:01,350 --> 00:10:04,170
>> Mit dieser Methode, wenn wir eine
Kollision, nun, was sollen wir tun?

207
00:10:04,170 --> 00:10:08,580
Nun, wir nicht setzen ihn in Matrixort
6, oder was auch immer Hashcode generiert wurde,

208
00:10:08,580 --> 00:10:10,820
lassen wir ihn in hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
Und wenn das volle Lassen Sie uns
setzte ihn in hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Der Vorteil dieses Wesen, wenn er
nicht genau, wo wir denken, dass er,

211
00:10:17,420 --> 00:10:20,850
und wir haben die Suche zu starten,
vielleicht haben wir nicht zu weit zu gehen.

212
00:10:20,850 --> 00:10:23,900
Vielleicht werden wir nicht haben, um zu suchen
alle n Elemente der Hash-Tabelle.

213
00:10:23,900 --> 00:10:25,790
Vielleicht haben wir, um zu suchen
ein paar von ihnen.

214
00:10:25,790 --> 00:10:30,680
>> Und so sind wir immer noch in Richtung tendiert
dass die durchschnittlichen Fall die Nähe zu 1 vs

215
00:10:30,680 --> 00:10:34,280
in der Nähe von n, so vielleicht das wird funktionieren.

216
00:10:34,280 --> 00:10:38,010
Also mal sehen, wie diese
vielleicht in Wirklichkeit heraus zu arbeiten.

217
00:10:38,010 --> 00:10:41,460
Und mal sehen, ob wir vielleicht erkennen kann
das Problem, das hier auftreten können.

218
00:10:41,460 --> 00:10:42,540
>> Sagen wir, wir hash Bart.

219
00:10:42,540 --> 00:10:45,581
So, jetzt werden wir einen neuen Satz laufen
von Strings durch die Hash-Funktion,

220
00:10:45,581 --> 00:10:48,460
und wir laufen Bart durch die Hash-
Funktion, bekommen wir hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Wir werfen einen Blick sehen wir 6
leer, so können wir Bart dort setzen.

222
00:10:52,100 --> 00:10:55,410
>> Jetzt hash wir Lisa, und dass
erzeugt auch hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Nun gut, dass wir mit diesem
Linearsondierungsverfahren beginnen wir bei der 6,

224
00:10:58,330 --> 00:10:59,330
sehen wir, dass 6 voll ist.

225
00:10:59,330 --> 00:11:00,990
Wir können nicht Lisa in 6.

226
00:11:00,990 --> 00:11:02,090
Also, wo gehen wir hin?

227
00:11:02,090 --> 00:11:03,280
Lassen Sie uns bis 7 gehen.

228
00:11:03,280 --> 00:11:04,610
7 ist leer, so dass das funktioniert.

229
00:11:04,610 --> 00:11:06,510
Also lassen wir es Lisa.

230
00:11:06,510 --> 00:11:10,200
>> Jetzt hash wir Homer und wir bekommen 7.

231
00:11:10,200 --> 00:11:13,380
OK gut wir wissen, dass 7 der Voll
Jetzt, so dass wir nicht setzen Homer gibt.

232
00:11:13,380 --> 00:11:14,850
Lassen Sie uns also bis 8 gehen.

233
00:11:14,850 --> 00:11:15,664
8 zur Verfügung?

234
00:11:15,664 --> 00:11:18,330
Ja, und 8 ist in der Nähe von 7, wenn ja,
Wir haben die Suche sind wir zu starten

235
00:11:18,330 --> 00:11:20,020
nicht gehen zu müssen, zu weit zu gehen.

236
00:11:20,020 --> 00:11:22,860
Und so lassen wir Homer bei 8.

237
00:11:22,860 --> 00:11:25,151
>> Jetzt hash wir Maggie und
liefert 3, Gott sei Dank

238
00:11:25,151 --> 00:11:26,650
wir sind in der Lage, setzen Sie einfach Maggie gibt.

239
00:11:26,650 --> 00:11:29,070
Wir haben nicht zu einem zu tun
Art Sondierungs dafür.

240
00:11:29,070 --> 00:11:32,000
Jetzt hash wir Marge, und
Marge gibt auch 6.

241
00:11:32,000 --> 00:11:39,560
>> Gut 6 voll ist, 7 ist voll, 8 voll ist,
9, in Ordnung Gott sei Dank, 9 ist leer.

242
00:11:39,560 --> 00:11:41,600
Ich kann Marge auf 9 gesetzt.

243
00:11:41,600 --> 00:11:45,280
Schon sehen wir, dass wir beginnen
um dieses Problem, in dem jetzt sind wir haben

244
00:11:45,280 --> 00:11:48,780
beginnen, die Dinge Art strecken
der weit weg von ihren Hash-Codes.

245
00:11:48,780 --> 00:11:52,960
Und Theta von 1, dass die durchschnittlichen
Bei konstant Zeit,

246
00:11:52,960 --> 00:11:56,560
beginnt, ein wenig more-- erhalten
beginnen, ein wenig mehr dazu neigen,

247
00:11:56,560 --> 00:11:58,050
in Richtung Theta von n.

248
00:11:58,050 --> 00:12:01,270
Wir fangen an, dass zu verlieren
Vorteil der Hash-Tabellen.

249
00:12:01,270 --> 00:12:03,902
>> Das Problem, das wir gerade gesehen haben
so etwas wie Clustering.

250
00:12:03,902 --> 00:12:06,360
Und was ist wirklich schlecht zu
Clustering ist, dass, sobald Sie sich jetzt

251
00:12:06,360 --> 00:12:09,606
zwei Elemente, die Seite sind durch
Seite macht es noch wahrscheinlicher,

252
00:12:09,606 --> 00:12:11,480
Sie haben die doppelte
Chance, dass du gehst

253
00:12:11,480 --> 00:12:13,516
um eine weitere Kollision haben
mit diesem Cluster,

254
00:12:13,516 --> 00:12:14,890
und der Cluster wird durch einen wachsen.

255
00:12:14,890 --> 00:12:19,640
Und du wirst zu halten wächst und wächst
Ihre Wahrscheinlichkeit, dass eine Kollision.

256
00:12:19,640 --> 00:12:24,470
Und schließlich ist es genauso schlecht
nicht Sortieren der Daten überhaupt.

257
00:12:24,470 --> 00:12:27,590
>> Das andere Problem ist aber, wir
noch, und so weit bis zu diesem Punkt,

258
00:12:27,590 --> 00:12:30,336
Wir haben gerade eine Art gewesen
zu verstehen, was eine Hash-Tabelle ist,

259
00:12:30,336 --> 00:12:31,960
wir immer noch nur Platz für 10 Saiten.

260
00:12:31,960 --> 00:12:37,030
Wenn wir wollen, auch weiterhin hash
die Bürger von Springfield,

261
00:12:37,030 --> 00:12:38,790
wir können nur in dorthin zu gelangen 10 von ihnen.

262
00:12:38,790 --> 00:12:42,619
Und wenn wir es versuchen und füge eine 11. oder 12.,
wir haben nicht einen Platz, um sie gelegt.

263
00:12:42,619 --> 00:12:45,660
Wir konnten einfach werden rund um die Spinnerei in
Kreise versuchen, eine freie Stelle zu finden,

264
00:12:45,660 --> 00:12:49,000
und wir vielleicht stecken
in einer Endlosschleife.

265
00:12:49,000 --> 00:12:51,810
>> Also diese Art der leiht dem Idee
der so genannten Verkettung.

266
00:12:51,810 --> 00:12:55,790
Und das ist, wohin wir gehen, um zu bringen
verkettete Listen zurück in das Bild.

267
00:12:55,790 --> 00:13:01,300
Was wäre, wenn statt der Speicherung von nur
die Daten selbst in der Anordnung,

268
00:13:01,300 --> 00:13:04,471
jedes Element der Anordnung könnte
Halten Sie mehrere Stücke von Daten?

269
00:13:04,471 --> 00:13:05,970
Nun, das ist nicht sinnvoll, nicht wahr?

270
00:13:05,970 --> 00:13:09,280
Wir wissen, dass ein Array kann nur
jedes Element eines Arrays hold--

271
00:13:09,280 --> 00:13:12,930
kann nur ein Stück zu halten
Daten dieses Datentyps.

272
00:13:12,930 --> 00:13:16,750
>> Aber was, wenn dieser Datentyp
ist eine verkettete Liste, nicht wahr?

273
00:13:16,750 --> 00:13:19,830
So was, wenn jede
Element der Anordnung war

274
00:13:19,830 --> 00:13:22,790
ein Zeiger auf den Kopf einer verketteten Liste?

275
00:13:22,790 --> 00:13:24,680
Und dann werden wir aufbauen konnten
diese verkettete Listen

276
00:13:24,680 --> 00:13:27,120
und wachsen sie willkürlich,
da verkettete Listen ermöglichen

277
00:13:27,120 --> 00:13:32,090
uns zu wachsen und schrumpfen viel mehr
flexibler als ein Array tut.

278
00:13:32,090 --> 00:13:34,210
So was, wenn wir heute verwenden,
wir diese nutzen, oder?

279
00:13:34,210 --> 00:13:37,760
Wir beginnen, diese Ketten wachsen
aus diesen Positionen auf dem Array.

280
00:13:37,760 --> 00:13:40,740
>> Jetzt können wir eine unendliche passen
Datenmenge oder nicht unendlich,

281
00:13:40,740 --> 00:13:44,170
eine willkürliche Menge an
Daten in unser Hash-Tabelle

282
00:13:44,170 --> 00:13:47,760
ohne jemals in Laufen
das Problem der Kollision.

283
00:13:47,760 --> 00:13:50,740
Wir haben ebenfalls eliminiert
Clustering, indem Sie diese.

284
00:13:50,740 --> 00:13:54,380
Und auch wir wissen, dass, wenn wir fügen
in einer verknüpften Liste, wenn Sie sich erinnern,

285
00:13:54,380 --> 00:13:57,779
aus unserem Video auf verkettete Listen, einzeln
verkettete Listen und doppelt verkettete Listen,

286
00:13:57,779 --> 00:13:59,070
es ist eine konstante Zeitbetrieb.

287
00:13:59,070 --> 00:14:00,710
Wir sind einfach nur mit an die Front.

288
00:14:00,710 --> 00:14:04,400
>> Und sehen Sie, auch wir wissen,
dass Nachschlagen in einer verknüpften Liste

289
00:14:04,400 --> 00:14:05,785
kann ein Problem sein, oder?

290
00:14:05,785 --> 00:14:07,910
Wir haben, um durch zu suchen
es von Anfang bis Ende.

291
00:14:07,910 --> 00:14:10,460
Es gibt keine Zufalls
Zugriff in einer verketteten Liste.

292
00:14:10,460 --> 00:14:15,610
Aber wenn anstatt einer verknüpften
Liste, wo eine Lookup würde O n sein,

293
00:14:15,610 --> 00:14:19,590
wir haben jetzt 10 verkettete Listen,
oder 1.000 verkettete Listen,

294
00:14:19,590 --> 00:14:24,120
jetzt ist es O n geteilt durch 10,
oder O n geteilt durch 1.000.

295
00:14:24,120 --> 00:14:26,940
>> Und während wir uns unterhielten
theoretisch über die Komplexität

296
00:14:26,940 --> 00:14:30,061
wir Konstanten außer Acht lassen, in der realen
Welt diese Dinge eigentlich egal,

297
00:14:30,061 --> 00:14:30,560
Recht?

298
00:14:30,560 --> 00:14:33,080
Wir werden tatsächlich feststellen,
dass dies geschieht,

299
00:14:33,080 --> 00:14:36,610
zu 10-mal schneller laufen,
oder 1000 mal schneller

300
00:14:36,610 --> 00:14:41,570
weil wir die Verteilung einer lang
Kette über 1.000 kleinere Ketten.

301
00:14:41,570 --> 00:14:45,090
Und so jedes Mal müssen wir suchen
durch eine dieser Ketten können wir

302
00:14:45,090 --> 00:14:50,290
ignorieren Sie die 999-Ketten ist uns egal
zu, und suchen nur, dass man.

303
00:14:50,290 --> 00:14:53,220
>> Das ist im Durchschnitt
sein 1.000-mal kürzer.

304
00:14:53,220 --> 00:14:56,460
Und so sind wir immer noch eine Art
Stärker zur dieser Durchschnittsfall

305
00:14:56,460 --> 00:15:01,610
der konstant ist Zeit, aber
nur weil wir die Nutzung

306
00:15:01,610 --> 00:15:03,730
Division mit einem riesigen konstanten Faktor.

307
00:15:03,730 --> 00:15:05,804
Mal sehen, wie könnte dies
tatsächlich aussehen though.

308
00:15:05,804 --> 00:15:08,720
Das war also die Hash-Tabelle wir hatten
bevor wir eine Hash-Tabelle erklärt, dass

309
00:15:08,720 --> 00:15:10,270
war die Speicherung von 10 Saiten.

310
00:15:10,270 --> 00:15:11,728
Wir gehen nicht, um mehr tun.

311
00:15:11,728 --> 00:15:13,880
Wir wissen bereits, die
Grenzen dieser Methode.

312
00:15:13,880 --> 00:15:20,170
Jetzt geht unsere Hash-Tabelle zu sein
ein Array von 10 Knoten, Zeiger

313
00:15:20,170 --> 00:15:22,120
In den Köpfen der verknüpften Listen.

314
00:15:22,120 --> 00:15:23,830
>> Und jetzt ist es null.

315
00:15:23,830 --> 00:15:26,170
Jede dieser 10-Pointer ist null.

316
00:15:26,170 --> 00:15:29,870
Es gibt nichts in unserem
Hash-Tabelle im Augenblick.

317
00:15:29,870 --> 00:15:32,690
>> Lassen Sie uns jetzt beginnen, einige setzen
Dinge in dieser Hash-Tabelle.

318
00:15:32,690 --> 00:15:35,440
Und lassen Sie uns sehen, wie diese Methode
wird uns zugute kommen ein wenig.

319
00:15:35,440 --> 00:15:36,760
Lassen Sie uns nun Hash Joey.

320
00:15:36,760 --> 00:15:40,210
Wir werden die Zeichenfolge Joey durchlaufen
eine Hash-Funktion und kehren wir zurück 6.

321
00:15:40,210 --> 00:15:41,200
Nun, was machen wir jetzt?

322
00:15:41,200 --> 00:15:44,090
>> Nun arbeitet nun mit verketteten Listen,
wir sind nicht die Arbeit mit Arrays.

323
00:15:44,090 --> 00:15:45,881
Und wenn wir arbeiten
mit verknüpften Listen wir

324
00:15:45,881 --> 00:15:49,790
wissen, wir brauchen, um dynamisch zu starten
Zuweisen von Speicherplatz und Gebäudeketten.

325
00:15:49,790 --> 00:15:54,020
Das ist eine Art how-- das sind die Kern
Elemente des Aufbaus einer verketteten Liste.

326
00:15:54,020 --> 00:15:57,670
Lassen Sie uns also dynamisch
Speicherplatz zuweisen für Joey,

327
00:15:57,670 --> 00:16:00,390
und dann lassen Sie ihn in den der Kette.

328
00:16:00,390 --> 00:16:03,170
>> So, jetzt schauen, was wir getan haben.

329
00:16:03,170 --> 00:16:06,440
Wenn wir hash Joey wir haben den Hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Jetzt wird der Zeiger auf Array Lage 6
weist auf die Spitze einer verknüpften Liste,

331
00:16:11,790 --> 00:16:14,900
und jetzt ist es die einzige
Element einer verketteten Liste.

332
00:16:14,900 --> 00:16:18,350
Und der Knoten dadurch gekennzeichnet, dass
verknüpfte Liste ist Joey.

333
00:16:18,350 --> 00:16:22,300
>> Also, wenn wir müssen schauen Joey
später, wir haben nur hash Joey wieder,

334
00:16:22,300 --> 00:16:26,300
wir wieder zu bekommen, weil unsere 6
Hash-Funktion deterministisch ist.

335
00:16:26,300 --> 00:16:30,400
Und dann fangen wir an der Spitze
der verknüpften Liste hingewiesen

336
00:16:30,400 --> 00:16:33,360
durch Feldposition
6, und wir durchlaufen kann

337
00:16:33,360 --> 00:16:35,650
auf, die versuchen, Joey zu finden.

338
00:16:35,650 --> 00:16:37,780
Und wenn wir unser
effektiv Hash-Tabelle,

339
00:16:37,780 --> 00:16:41,790
und unsere Hash-Funktion effektiv
Daten gut zu verteilen,

340
00:16:41,790 --> 00:16:45,770
im Durchschnitt jedes dieser verbunden
Listen in jedem Array Ort

341
00:16:45,770 --> 00:16:50,110
wird 1/10 der Größe, wenn wir sein
musste es einfach als eine einzige riesige

342
00:16:50,110 --> 00:16:51,650
verknüpfte Liste mit allem, was in ihm.

343
00:16:51,650 --> 00:16:55,670
>> Wenn wir zu verteilen, dass riesige verbunden
Liste über 10 verketteten Listen

344
00:16:55,670 --> 00:16:57,760
Jede Liste wird 1/10 der Größe sein.

345
00:16:57,760 --> 00:17:01,432
Und damit 10 Mal schneller
zu durchsuchen.

346
00:17:01,432 --> 00:17:02,390
Lassen Sie uns also wieder tun.

347
00:17:02,390 --> 00:17:04,290
Lassen Sie uns nun Hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Und lassen Sie uns sagen, Ross, wenn wir das tun,
der Hash-Code wir zurück ist 2.

349
00:17:07,540 --> 00:17:10,630
Nun haben wir eine dynamische Zuordnung
neue Knoten legen wir Ross in diesem Knoten,

350
00:17:10,630 --> 00:17:14,900
und wir sagen jetzt Matrixort
2, statt auf null,

351
00:17:14,900 --> 00:17:18,579
weist auf den Kopf eines verknüpften
Liste, deren einzige Knoten ist Ross.

352
00:17:18,579 --> 00:17:22,660
Und wir können diesen noch einmal zu tun, die wir
kann Rachel hash und erhalten hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc einen neuen Knoten, legte Rachel in
der Knoten, und sagen, ein Array Ort

354
00:17:25,490 --> 00:17:27,839
4 zeigt nun auf den Kopf
einer verketteten Liste, deren

355
00:17:27,839 --> 00:17:31,420
einzige Element passiert mit Rachel sein.

356
00:17:31,420 --> 00:17:33,470
>> OK, aber was passiert, wenn
wir haben eine Kollision?

357
00:17:33,470 --> 00:17:38,560
Mal sehen, wie wir Kollisionen umgehen
mit der separaten Verkettungsverfahren.

358
00:17:38,560 --> 00:17:39,800
Lassen Sie uns hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Wir bekommen die hashcode 6.

360
00:17:41,094 --> 00:17:44,010
In unserem vorigen Beispiel nur waren wir
Speichern der Zeichenfolgen in der Anordnung.

361
00:17:44,010 --> 00:17:45,980
Dies war ein Problem.

362
00:17:45,980 --> 00:17:48,444
>> Wir wollen nicht clobber
Joey, und wir haben bereits

363
00:17:48,444 --> 00:17:51,110
zu sehen, dass wir einige Clustering erhalten
Probleme, wenn wir versuchen, Schritt

364
00:17:51,110 --> 00:17:52,202
durch und Sonde.

365
00:17:52,202 --> 00:17:54,660
Aber was, wenn wir nur irgendwie
behandeln dies die gleiche Art und Weise, nicht wahr?

366
00:17:54,660 --> 00:17:57,440
Es ist wie das Hinzufügen eines Elements
auf den Kopf einer verketteten Liste.

367
00:17:57,440 --> 00:18:00,220
Lassen Sie uns gerade malloc Platz für Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Wir werden nächste Zeiger Phoebes Punkte sagen
zur alten Leiter der verknüpften Liste,

369
00:18:04,764 --> 00:18:07,180
und dann 6 Punkte, nur um die
neuer Leiter der verknüpften Liste.

370
00:18:07,180 --> 00:18:10,150
Und jetzt schauen, haben wir Phoebe in geändert.

371
00:18:10,150 --> 00:18:14,210
Wir können nun speichern zwei
Elemente mit Hash-Code 6,

372
00:18:14,210 --> 00:18:17,170
und wir haben keine Probleme.

373
00:18:17,170 --> 00:18:20,147
>> Das ist so ziemlich alles,
gibt es, um die Verkettung.

374
00:18:20,147 --> 00:18:21,980
Und Verkettung ist auf jeden Fall
die Methode, die ist

375
00:18:21,980 --> 00:18:27,390
gehen, um am effektivsten für Sie, wenn
Sie Daten-Speicher werden in einer Hash-Tabelle.

376
00:18:27,390 --> 00:18:30,890
Aber diese Kombination von
Arrays und verkettete Listen

377
00:18:30,890 --> 00:18:36,080
zusammen, um eine Hash-Tabelle wirklich bilden
dramatisch verbessert Ihre Fähigkeit,

378
00:18:36,080 --> 00:18:40,550
um große Mengen von Daten zu speichern, und
sehr schnell und effizient suchen

379
00:18:40,550 --> 00:18:41,630
durch diese Daten.

380
00:18:41,630 --> 00:18:44,150
>> Es gibt noch eine weitere
Datenstruktur gibt,

381
00:18:44,150 --> 00:18:48,700
dass vielleicht sogar ein bisschen sein
besser in Bezug auf Gewährleistung

382
00:18:48,700 --> 00:18:51,920
dass unsere Insertion, Deletion und
nachschlagen Zeiten sind noch schneller.

383
00:18:51,920 --> 00:18:55,630
Und wir werden, dass in einem Video auf Versuche zu sehen.

384
00:18:55,630 --> 00:18:58,930
Ich bin Doug Lloyd, ist dies CS50.

385
00:18:58,930 --> 00:19:00,214