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

2
00:00:00,500 --> 00:00:01,900
[MUSIK SPELA]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Vid det här laget du
vet en hel del om matriser,

5
00:00:09,150 --> 00:00:11,610
och du vet en hel del om länkade listor.

6
00:00:11,610 --> 00:00:13,650
Och vi har att diskutera
för- och nackdelar har vi

7
00:00:13,650 --> 00:00:16,620
diskuteras som länkade listor
kan bli större och mindre,

8
00:00:16,620 --> 00:00:18,630
men de tar upp större storlek.

9
00:00:18,630 --> 00:00:22,359
Arrayer är mycket enklare att
använda, men de är restriktiv i så mycket

10
00:00:22,359 --> 00:00:24,900
som vi måste ställa in storleken på
uppsättningen i början

11
00:00:24,900 --> 00:00:26,910
och sedan är vi fastnat med det.

12
00:00:26,910 --> 00:00:30,470
>> Men det är, vi har ganska mycket
uttömt alla våra ämnen

13
00:00:30,470 --> 00:00:33,040
om länkade listor och matriser.

14
00:00:33,040 --> 00:00:34,950
Eller har vi?

15
00:00:34,950 --> 00:00:37,720
Vi kanske kan göra något
ännu mer kreativ.

16
00:00:37,720 --> 00:00:40,950
Och den sortens lånar
tanken på en hash-tabell.

17
00:00:40,950 --> 00:00:46,680
>> Så i en hashtabell vi kommer att försöka
kombinera en matris med en länkad lista.

18
00:00:46,680 --> 00:00:49,520
Vi kommer att ta fördelarna
av matrisen, som random access,

19
00:00:49,520 --> 00:00:53,510
att kunna gå till array
elementet 4 eller gruppelement 8

20
00:00:53,510 --> 00:00:55,560
utan att iterera över.

21
00:00:55,560 --> 00:00:57,260
Det är ganska snabbt, eller hur?

22
00:00:57,260 --> 00:01:00,714
>> Men vi vill också ha våra data
struktur kunna växa och krympa.

23
00:01:00,714 --> 00:01:02,630
Vi behöver inte, vi gör inte
vill vara begränsad.

24
00:01:02,630 --> 00:01:04,588
Och vi vill kunna
att lägga till och ta bort saker

25
00:01:04,588 --> 00:01:08,430
mycket lätt, vilket om ni minns,
är mycket komplex med en array.

26
00:01:08,430 --> 00:01:11,650
Och vi kan kalla detta
ny sak en hashtabell.

27
00:01:11,650 --> 00:01:15,190
>> Och om de genomförs på rätt sätt,
vi sorts tar

28
00:01:15,190 --> 00:01:18,150
fördelarna med både data
strukturer du redan har sett,

29
00:01:18,150 --> 00:01:19,880
arrayer och länkade listor.

30
00:01:19,880 --> 00:01:23,070
Infogning kan börja
tenderar mot teta av en.

31
00:01:23,070 --> 00:01:26,207
Theta vi har inte riktigt diskuterat,
men theta är bara det genomsnittliga fallet,

32
00:01:26,207 --> 00:01:27,540
vad som faktiskt kommer att hända.

33
00:01:27,540 --> 00:01:29,680
Du är inte alltid kommer att
har det värsta scenariot,

34
00:01:29,680 --> 00:01:32,555
och du inte alltid kommer att ha
bästa fall, så vad är

35
00:01:32,555 --> 00:01:33,900
den genomsnittliga scenariot?

36
00:01:33,900 --> 00:01:36,500
>> Väl en genomsnittlig inser
in i en hash-tabell

37
00:01:36,500 --> 00:01:39,370
kan börja komma nära konstant tid.

38
00:01:39,370 --> 00:01:41,570
Och radering kan få
nära till konstant tid.

39
00:01:41,570 --> 00:01:44,440
Och lookup kan få
nära till konstant tid.

40
00:01:44,440 --> 00:01:48,600
That's-- vi inte har ett data
struktur ännu som kan göra det,

41
00:01:48,600 --> 00:01:51,180
och så detta redan låter
som en ganska stor sak.

42
00:01:51,180 --> 00:01:57,010
Vi har verkligen mildrat
nackdelar med varje på egen hand.

43
00:01:57,010 --> 00:01:59,160
>> För att få detta resultat
uppgradera men vi

44
00:01:59,160 --> 00:02:03,580
måste ompröva hur vi lägger
data i strukturen.

45
00:02:03,580 --> 00:02:07,380
Specifikt vi vill att
Uppgiften i sig att berätta för oss

46
00:02:07,380 --> 00:02:09,725
där det ska gå i strukturen.

47
00:02:09,725 --> 00:02:12,850
Och om vi då behöva se om det är i
struktur, om vi behöver hitta det,

48
00:02:12,850 --> 00:02:16,610
vi vill titta på data
igen och kunna effektivt

49
00:02:16,610 --> 00:02:18,910
med hjälp av data, slumpmässigt tillgång till den.

50
00:02:18,910 --> 00:02:20,700
Bara genom att titta på
uppgifter bör vi ha

51
00:02:20,700 --> 00:02:25,890
en uppfattning om var vi exakt är
kommer att hitta det i hashtabellen.

52
00:02:25,890 --> 00:02:28,770
>> Nu baksidan av en hash
tabellen är att de är verkligen

53
00:02:28,770 --> 00:02:31,770
ganska dåliga på att beställa eller sortera data.

54
00:02:31,770 --> 00:02:34,970
Och faktum är att om du börjar
att använda dem för att beställa eller sortera

55
00:02:34,970 --> 00:02:37,990
data du förlorar alla
fördelar du tidigare

56
00:02:37,990 --> 00:02:40,710
hade när det gäller införande och radering.

57
00:02:40,710 --> 00:02:44,060
Tiden blir närmare
theta n, och vi har i stort sett

58
00:02:44,060 --> 00:02:45,530
regredierat till en länkad lista.

59
00:02:45,530 --> 00:02:48,850
Och så vill vi bara använda hash
tabeller om vi inte bryr sig om

60
00:02:48,850 --> 00:02:51,490
om data sorteras.

61
00:02:51,490 --> 00:02:54,290
För det sammanhang i vilket
du kommer att använda dem i CS50

62
00:02:54,290 --> 00:02:58,900
du förmodligen inte bryr
att uppgifterna sorteras.

63
00:02:58,900 --> 00:03:03,170
>> Så en hashtabell är en kombination
av två olika bitar

64
00:03:03,170 --> 00:03:04,980
som vi är bekant.

65
00:03:04,980 --> 00:03:07,930
Den första är en funktion, som
vi brukar kalla en hashfunktion.

66
00:03:07,930 --> 00:03:11,760
Och det hashfunktion kommer att
tillbaka vissa icke-negativt heltal, som

67
00:03:11,760 --> 00:03:14,870
vi brukar kalla en hashkod, OK?

68
00:03:14,870 --> 00:03:20,230
Den andra delen är en array, som är
med förmåga att lagra data av den typ som vi

69
00:03:20,230 --> 00:03:22,190
vill placera in i datastrukturen.

70
00:03:22,190 --> 00:03:24,310
Vi kommer att vänta på
länkad lista element för nu

71
00:03:24,310 --> 00:03:27,810
och bara börja med grunderna i en
hash tabellen för att få huvudet runt det,

72
00:03:27,810 --> 00:03:30,210
och sedan kommer vi kanske att blåsa
ditt sinne lite när vi

73
00:03:30,210 --> 00:03:32,920
kombinera arrayer och länklistor tillsammans.

74
00:03:32,920 --> 00:03:35,590
>> Den grundläggande idén om
är vi ta några uppgifter.

75
00:03:35,590 --> 00:03:37,860
Vi kör dessa data genom
hashfunktionen.

76
00:03:37,860 --> 00:03:41,980
Och så uppgifterna behandlas
och det spottar ut ett nummer, OK?

77
00:03:41,980 --> 00:03:44,890
Och sedan med det numret
lagrar vi bara data

78
00:03:44,890 --> 00:03:48,930
vi vill lagra i
array på den platsen.

79
00:03:48,930 --> 00:03:53,990
Så till exempel har vi kanske
denna hashtabell av strängar.

80
00:03:53,990 --> 00:03:57,350
Det har fått 10 element i det, så
vi kan passa 10 strängar i det.

81
00:03:57,350 --> 00:03:59,320
>> Låt oss säga att vi vill hash John.

82
00:03:59,320 --> 00:04:02,979
Så Johannes som de data vi vill infoga
i denna hash-tabell någonstans.

83
00:04:02,979 --> 00:04:03,770
Var ska vi säga?

84
00:04:03,770 --> 00:04:05,728
Väl typiskt med en
array så långt vi förmodligen

85
00:04:05,728 --> 00:04:07,610
skulle uttrycka det i array plats 0.

86
00:04:07,610 --> 00:04:09,960
Men nu har vi denna nya hash funktion.

87
00:04:09,960 --> 00:04:13,180
>> Och låt oss säga att vi kör John
genom denna hash-funktion

88
00:04:13,180 --> 00:04:15,417
och det är spottar ut 4.

89
00:04:15,417 --> 00:04:17,500
Ja, det är där vi är
kommer att vilja sätta John.

90
00:04:17,500 --> 00:04:22,050
Vi vill sätta John i array plats
4, för om vi hash John igen--

91
00:04:22,050 --> 00:04:23,810
låt oss säga senare vi
vill söka och se

92
00:04:23,810 --> 00:04:26,960
om John existerar i denna hash
table-- allt vi behöver göra

93
00:04:26,960 --> 00:04:30,310
körs det genom samma hash
funktion, få nummer 4,

94
00:04:30,310 --> 00:04:33,929
och att kunna hitta John
omedelbart i vår datastruktur.

95
00:04:33,929 --> 00:04:34,720
Det är ganska bra.

96
00:04:34,720 --> 00:04:36,928
>> Låt oss säga att vi nu göra detta
igen, vi vill hash Paul.

97
00:04:36,928 --> 00:04:39,446
Vi vill lägga till Paul
in i denna hashtabell.

98
00:04:39,446 --> 00:04:42,070
Låt oss säga att den här gången kör vi
Paul genom hashfunktionen,

99
00:04:42,070 --> 00:04:44,600
den hashkod som genereras är sex.

100
00:04:44,600 --> 00:04:47,340
Nu kan vi sätta Paul
i matrisen plats 6.

101
00:04:47,340 --> 00:04:50,040
Och om vi måste se upp om
Paul är i detta hashtabell,

102
00:04:50,040 --> 00:04:53,900
allt vi behöver göra är att köra Paul
genom hashfunktionen igen

103
00:04:53,900 --> 00:04:55,830
och vi kommer att få 6 igen.

104
00:04:55,830 --> 00:04:57,590
>> Och sedan ser vi bara
på array plats 6.

105
00:04:57,590 --> 00:04:58,910
Är Paul det?

106
00:04:58,910 --> 00:05:00,160
Om så är fallet, är han i hashtabellen.

107
00:05:00,160 --> 00:05:01,875
Är Paul inte det?

108
00:05:01,875 --> 00:05:03,000
Han är inte i hashtabellen.

109
00:05:03,000 --> 00:05:05,720
Det är ganska enkelt.

110
00:05:05,720 --> 00:05:07,770
>> Nu hur definierar du en hashfunktion?

111
00:05:07,770 --> 00:05:11,460
Jo det finns egentligen ingen gräns för hur
antal möjliga hashfunktioner.

112
00:05:11,460 --> 00:05:14,350
I själva verket finns det ett antal riktigt,
riktigt bra på internet.

113
00:05:14,350 --> 00:05:17,560
Det finns ett antal riktigt,
riktigt dåliga på internet.

114
00:05:17,560 --> 00:05:21,080
Det är också ganska lätt
att skriva en dålig.

115
00:05:21,080 --> 00:05:23,760
>> Så vad gör en bra
hashfunktion, eller hur?

116
00:05:23,760 --> 00:05:27,280
Tja en bra hashfunktion bör
använder endast de data som hashas,

117
00:05:27,280 --> 00:05:29,420
och alla data som hashas.

118
00:05:29,420 --> 00:05:32,500
Så att vi inte vill använda anything--
vi inte införlivar något

119
00:05:32,500 --> 00:05:35,560
annanstans än uppgifterna.

120
00:05:35,560 --> 00:05:37,080
Och vi vill använda alla data.

121
00:05:37,080 --> 00:05:39,830
Vi vill inte bara använda en bit
det vill vi använda allt.

122
00:05:39,830 --> 00:05:41,710
En hashfunktion bör
också vara deterministisk.

123
00:05:41,710 --> 00:05:42,550
Vad betyder det?

124
00:05:42,550 --> 00:05:46,200
Jo det innebär att varje gång vi
passera exakt samma bit data

125
00:05:46,200 --> 00:05:50,040
i hashfunktionen vi alltid
få samma hashkod ut.

126
00:05:50,040 --> 00:05:52,870
Om jag passerar John i
hashfunktion jag kommer ut 4.

127
00:05:52,870 --> 00:05:56,110
Jag skulle kunna göra det 10000
gånger och jag kommer alltid att få 4.

128
00:05:56,110 --> 00:06:00,810
Så inga slumptal effektivt
kan vara inblandade i vår hash tables--

129
00:06:00,810 --> 00:06:02,750
i våra hashfunktioner.

130
00:06:02,750 --> 00:06:05,750
>> En hashfunktion bör också
likformigt distribuera data.

131
00:06:05,750 --> 00:06:09,700
Om varje gång du kör data via
hashfunktion du får hashkod 0,

132
00:06:09,700 --> 00:06:11,200
det är nog inte så stor, eller hur?

133
00:06:11,200 --> 00:06:14,600
Du vill förmodligen stora
ett intervall av hash-koder.

134
00:06:14,600 --> 00:06:17,190
Också saker kan spridas
ut hela tabellen.

135
00:06:17,190 --> 00:06:23,210
Och det skulle vara bra om verkligen
liknande data, som John och Jonathan,

136
00:06:23,210 --> 00:06:26,320
kanske spreds ut att väga
olika platser i hashtabellen.

137
00:06:26,320 --> 00:06:28,750
Det skulle vara en trevlig fördel.

138
00:06:28,750 --> 00:06:31,250
>> Här är ett exempel på en hash-funktion.

139
00:06:31,250 --> 00:06:33,150
Jag skrev ett upp tidigare.

140
00:06:33,150 --> 00:06:35,047
Det är inte en särskilt
bra hash-funktion

141
00:06:35,047 --> 00:06:37,380
av skäl som inte riktigt
bära gå in just nu.

142
00:06:37,380 --> 00:06:41,040
Men ser du vad som händer här?

143
00:06:41,040 --> 00:06:44,420
Det verkar som om vi förklara en variabel
kallas summa och ställa den lika med 0.

144
00:06:44,420 --> 00:06:50,010
Och sedan tydligen jag gör något
så länge som strstr [j] är icke lika

145
00:06:50,010 --> 00:06:52,490
att bakåtstreck 0.

146
00:06:52,490 --> 00:06:54,870
Vad gör jag där?

147
00:06:54,870 --> 00:06:57,440
>> Detta är i grunden bara en annan
sättet att genomföra [? strl?]

148
00:06:57,440 --> 00:06:59,773
och detektera när du har
nått slutet av strängen.

149
00:06:59,773 --> 00:07:02,480
Så jag behöver inte faktiskt
beräkna längden på strängen,

150
00:07:02,480 --> 00:07:05,640
Jag bara använda när jag träffade
backslash 0 tecken jag vet

151
00:07:05,640 --> 00:07:07,185
Jag har nått slutet av strängen.

152
00:07:07,185 --> 00:07:09,560
Och sedan kommer jag att hålla
iterera genom den strängen,

153
00:07:09,560 --> 00:07:15,310
sätta strstr [j] för att summera och sedan på
slutet av dagen kommer att återvända summan mod

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

155
00:07:16,200 --> 00:07:18,700
>> I princip allt detta hash
funktionen gör är att lägga upp

156
00:07:18,700 --> 00:07:23,450
alla ASCII-värdena av
min string, och då är det

157
00:07:23,450 --> 00:07:26,390
återvända någon hashkod
modded av HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Det är förmodligen storlek
min samling, eller hur?

159
00:07:29,790 --> 00:07:33,160
Jag vill inte att få hash
koder om min samling är av storlek 10,

160
00:07:33,160 --> 00:07:35,712
Jag vill inte vara att få
ut hash-koder 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, jag kan inte sätta saker i
dessa placeringar av arrayen,

162
00:07:38,690 --> 00:07:39,790
det skulle vara olagligt.

163
00:07:39,790 --> 00:07:42,130
Jag skulle drabbas av en segmentering fel.

164
00:07:42,130 --> 00:07:45,230
>> Nu här är en annan snabbt åt sidan.

165
00:07:45,230 --> 00:07:48,470
Generellt du förmodligen inte kommer att
vill skriva egna hashfunktioner.

166
00:07:48,470 --> 00:07:50,997
Det är faktiskt lite av
en konst, inte en vetenskap.

167
00:07:50,997 --> 00:07:52,580
Och det finns en hel del som går in i dem.

168
00:07:52,580 --> 00:07:55,288
Internet, som sagt, är full
riktigt bra hashfunktioner,

169
00:07:55,288 --> 00:07:58,470
och du bör använda Internet för att
hitta hash funktioner eftersom det är verkligen

170
00:07:58,470 --> 00:08:03,230
bara typ av en onödig
slöseri med tid att skapa din egen.

171
00:08:03,230 --> 00:08:05,490
>> Du kan skriva enkla sådana
för teständamål.

172
00:08:05,490 --> 00:08:08,323
Men när du faktiskt kommer att
börja hashing uppgifter och lagra den

173
00:08:08,323 --> 00:08:10,780
i en hashtabell du
förmodligen kommer att vilja

174
00:08:10,780 --> 00:08:14,580
att använda någon funktion som genererades
för dig, finns det på internet.

175
00:08:14,580 --> 00:08:17,240
Om du bara vill vara säker
för att citera dina källor.

176
00:08:17,240 --> 00:08:21,740
Det finns ingen anledning att
plagiera något här.

177
00:08:21,740 --> 00:08:25,370
>> Datorn vetenskapliga samfundet är
definitivt växer, och verkligen värden

178
00:08:25,370 --> 00:08:28,796
öppen källkod, och det är verkligen viktigt
för att citera dina källor så att människor

179
00:08:28,796 --> 00:08:30,670
kan få erkännande för
det arbete som de är

180
00:08:30,670 --> 00:08:32,312
gör till förmån för samhället.

181
00:08:32,312 --> 00:08:34,020
Så alltid vara sure--
och inte bara för hash

182
00:08:34,020 --> 00:08:37,270
funktioner, men i allmänhet, när du
Använd koden från en extern källa,

183
00:08:37,270 --> 00:08:38,299
alltid nämna källan.

184
00:08:38,299 --> 00:08:43,500
Ge kredit till den person som gjorde
en del av arbetet så att du inte behöver.

185
00:08:43,500 --> 00:08:46,720
>> OK så låt oss återvända till denna
hashtabell för en sekund.

186
00:08:46,720 --> 00:08:48,780
Det är där vi lämnade
rabatt när vi införas

187
00:08:48,780 --> 00:08:53,300
John och Paulus in i denna hashtabell.

188
00:08:53,300 --> 00:08:55,180
Ser du ett problem här?

189
00:08:55,180 --> 00:08:58,410
Du kan se två.

190
00:08:58,410 --> 00:09:02,240
Men framför allt, gör du
se risken för detta?

191
00:09:02,240 --> 00:09:06,770
>> Vad händer om jag hash Ringo, och det
visar sig att efter bearbetning

192
00:09:06,770 --> 00:09:14,000
att data genom hashfunktionen
Ringo genererade också hashkod 6.

193
00:09:14,000 --> 00:09:16,810
Jag har redan fått uppgifter på
hashcode-- array läge 6.

194
00:09:16,810 --> 00:09:22,000
Så det är förmodligen kommer att bli lite
av ett problem för mig nu, eller hur?

195
00:09:22,000 --> 00:09:23,060
>> Vi kallar detta en kollision.

196
00:09:23,060 --> 00:09:26,460
Och kollisionen inträffar när två
datadelar löper genom samma hash

197
00:09:26,460 --> 00:09:29,200
funktion ger samma hashkod.

198
00:09:29,200 --> 00:09:32,850
Förmodligen vi fortfarande vill få både
bitar av data i hashtabellen,

199
00:09:32,850 --> 00:09:36,330
annars skulle vi inte vara igång Ringo
godtyckligt genom hashfunktionen.

200
00:09:36,330 --> 00:09:40,870
Vi vill förmodligen för att få
RINGO in den arrayen.

201
00:09:40,870 --> 00:09:46,070
>> Hur gör vi det ändå, om han
och Paul både avkastning hashkod 6?

202
00:09:46,070 --> 00:09:49,520
Vi vill inte skriva Paul,
Vi vill att Paul att vara där också.

203
00:09:49,520 --> 00:09:52,790
Så vi måste hitta ett sätt att få
element i hash tabellen som

204
00:09:52,790 --> 00:09:56,550
fortfarande bevarar vår snabb
införande och snabb titt upp.

205
00:09:56,550 --> 00:10:01,350
Och ett sätt att ta itu med det är att
göra något som kallas linjär sondering.

206
00:10:01,350 --> 00:10:04,170
>> Med denna metod om vi har en
kollision, ja, vad gör vi?

207
00:10:04,170 --> 00:10:08,580
Väl vi inte kan sätta honom i array plats
6, eller vad hashkod genererades,

208
00:10:08,580 --> 00:10:10,820
låt oss sätta honom på hashkod plus 1.

209
00:10:10,820 --> 00:10:13,670
Och om det är fullt låt oss
satte honom i hashkod plus 2.

210
00:10:13,670 --> 00:10:17,420
Fördelen med denna varelse om han är
inte precis där vi tror att han är,

211
00:10:17,420 --> 00:10:20,850
och vi måste börja söka,
kanske vi behöver inte gå för långt.

212
00:10:20,850 --> 00:10:23,900
Vi kanske inte behöver söka
alla n element i hashtabellen.

213
00:10:23,900 --> 00:10:25,790
Kanske måste vi söka
ett par av dem.

214
00:10:25,790 --> 00:10:30,680
>> Och så vi fortfarande går mot
att den genomsnittliga fall vara nära 1 vs

215
00:10:30,680 --> 00:10:34,280
nära n, så kanske det kommer att fungera.

216
00:10:34,280 --> 00:10:38,010
Så låt oss se hur detta
skulle kunna fungera i verkligheten.

217
00:10:38,010 --> 00:10:41,460
Och låt oss se om kanske vi kan upptäcka
det problem som kan uppstå här.

218
00:10:41,460 --> 00:10:42,540
>> Låt oss säga att vi hash Bart.

219
00:10:42,540 --> 00:10:45,581
Så nu ska vi köra en ny uppsättning
strängar genom hashfunktionen,

220
00:10:45,581 --> 00:10:48,460
och vi kör Bart genom hash
funktionen, vi får hashkod 6.

221
00:10:48,460 --> 00:10:52,100
Vi tar en titt, ser vi 6
tom, så att vi kan sätta Bart där.

222
00:10:52,100 --> 00:10:55,410
>> Nu hash vi Lisa och att
även genererar hashkod 6.

223
00:10:55,410 --> 00:10:58,330
Tja nu när vi använder detta
linjär sondering metod vi börjar vid 6,

224
00:10:58,330 --> 00:10:59,330
vi se att sex är fullt.

225
00:10:59,330 --> 00:11:00,990
Vi kan inte sätta Lisa 6.

226
00:11:00,990 --> 00:11:02,090
Så där går vi?

227
00:11:02,090 --> 00:11:03,280
Låt oss gå till 7.

228
00:11:03,280 --> 00:11:04,610
7 är tomt, så det fungerar.

229
00:11:04,610 --> 00:11:06,510
Så låt oss sätta Lisa där.

230
00:11:06,510 --> 00:11:10,200
>> Nu hash vi Homer och vi får 7.

231
00:11:10,200 --> 00:11:13,380
OK väl vi vet att 7 fullständiga
nu, så att vi inte kan sätta Homer där.

232
00:11:13,380 --> 00:11:14,850
Så låt oss gå till 8.

233
00:11:14,850 --> 00:11:15,664
Är 8 Tillgänglig?

234
00:11:15,664 --> 00:11:18,330
Ja, och 8: s nära 7, så om
Vi måste börja söka vi är

235
00:11:18,330 --> 00:11:20,020
inte kommer att behöva gå för långt.

236
00:11:20,020 --> 00:11:22,860
Och så låt oss sätta Homer på 8.

237
00:11:22,860 --> 00:11:25,151
>> Nu är vi hash Maggie och
returnerar 3, tack och lov

238
00:11:25,151 --> 00:11:26,650
vi kan bara sätta Maggie där.

239
00:11:26,650 --> 00:11:29,070
Vi behöver inte göra något
sorts sondering för det.

240
00:11:29,070 --> 00:11:32,000
Nu hash vi Marge, och
Marge återvänder också 6.

241
00:11:32,000 --> 00:11:39,560
>> Väl 6 är full, 7 är full, 8 är full,
9, okej tack och lov, 9 är tom.

242
00:11:39,560 --> 00:11:41,600
Jag kan sätta Marge på 9.

243
00:11:41,600 --> 00:11:45,280
Redan kan vi se att vi börjar
att ha det här problemet där nu är vi

244
00:11:45,280 --> 00:11:48,780
börjar sträcka saker slag
av långt borta från sina hash-koder.

245
00:11:48,780 --> 00:11:52,960
Och att teta av 1, i snitt som
händelse av att vara konstant tid,

246
00:11:52,960 --> 00:11:56,560
börjar få lite more--
börjar tenderar lite mer

247
00:11:56,560 --> 00:11:58,050
mot theta n.

248
00:11:58,050 --> 00:12:01,270
Vi börjar att förlora det
fördel av hashtabeller.

249
00:12:01,270 --> 00:12:03,902
>> Detta problem som vi såg bara
är något som kallas kluster.

250
00:12:03,902 --> 00:12:06,360
Och vad är egentligen dåligt om
kluster är att när du nu

251
00:12:06,360 --> 00:12:09,606
har två element som är sida vid
sida det gör det ännu mer troligt,

252
00:12:09,606 --> 00:12:11,480
du har dubbelt
chans, att du kommer

253
00:12:11,480 --> 00:12:13,516
att ha en annan kollision
med detta kluster,

254
00:12:13,516 --> 00:12:14,890
och klustret kommer att växa med en.

255
00:12:14,890 --> 00:12:19,640
Och du ska hålla växer och växer
dina chanser att ha en kollision.

256
00:12:19,640 --> 00:12:24,470
Och till slut är det lika illa
som inte sortera data alls.

257
00:12:24,470 --> 00:12:27,590
>> Det andra problemet är dock att vi
fortfarande, och hittills fram till denna punkt,

258
00:12:27,590 --> 00:12:30,336
Vi har bara varit sorts
förstå vad en hash-tabell är,

259
00:12:30,336 --> 00:12:31,960
vi fortfarande bara har plats för 10 strängar.

260
00:12:31,960 --> 00:12:37,030
Om vi ​​vill fortsätta att hash
medborgarna i Springfield,

261
00:12:37,030 --> 00:12:38,790
Vi kan bara få 10 av dem där.

262
00:12:38,790 --> 00:12:42,619
Och om vi försöker lägga till en 11: e eller 12: e,
vi har inte en plats att sätta dem.

263
00:12:42,619 --> 00:12:45,660
Vi kunde bara snurra runt i
cirklar att försöka hitta en tom plats,

264
00:12:45,660 --> 00:12:49,000
och vi kanske fastnar
i en oändlig loop.

265
00:12:49,000 --> 00:12:51,810
>> Så här sortens lånar till idén
av något som kallas kedja.

266
00:12:51,810 --> 00:12:55,790
Och det är där vi kommer att föra
länkade listor tillbaka in i bilden.

267
00:12:55,790 --> 00:13:01,300
Tänk om istället för att lagra bara
själva uppgifterna i arrayen,

268
00:13:01,300 --> 00:13:04,471
varje element i arrayen kunde
hålla flera stycken av data?

269
00:13:04,471 --> 00:13:05,970
Tja det inte är vettigt, eller hur?

270
00:13:05,970 --> 00:13:09,280
Vi vet att en array endast kan
hold-- varje element i en array

271
00:13:09,280 --> 00:13:12,930
kan bara hålla ett stycke
av uppgifter om den datatypen.

272
00:13:12,930 --> 00:13:16,750
>> Men vad händer om den datatypen
är en länkad lista, eller hur?

273
00:13:16,750 --> 00:13:19,830
Så vad händer om varje
element i gruppen var

274
00:13:19,830 --> 00:13:22,790
en pekare till chefen för en länkad lista?

275
00:13:22,790 --> 00:13:24,680
Och då kunde vi bygga
de länkade listor

276
00:13:24,680 --> 00:13:27,120
och odla dem godtyckligt,
eftersom länkade listor tillåter

277
00:13:27,120 --> 00:13:32,090
oss att växa och krympa mycket mer
flexibelt än en array gör.

278
00:13:32,090 --> 00:13:34,210
Så vad händer om vi nu använda,
vi utnyttja denna, rätt?

279
00:13:34,210 --> 00:13:37,760
Vi börjar att odla dessa kedjor
av dessa array platser.

280
00:13:37,760 --> 00:13:40,740
>> Nu kan vi passar en oändlig
mängden data, eller inte oändlig,

281
00:13:40,740 --> 00:13:44,170
en godtycklig mängd av
data in i vår hashtabellen

282
00:13:44,170 --> 00:13:47,760
utan att någonsin köra in
problemet för kollision.

283
00:13:47,760 --> 00:13:50,740
Vi har också elimineras
kluster genom att göra detta.

284
00:13:50,740 --> 00:13:54,380
Och väl vi vet att när vi sätter
i en länkad lista, om du minns

285
00:13:54,380 --> 00:13:57,779
från vår video på länkade listor, var för sig
länkade listor och dubbelt länkade listor,

286
00:13:57,779 --> 00:13:59,070
det är en ständig time operation.

287
00:13:59,070 --> 00:14:00,710
Vi bara lägga till fronten.

288
00:14:00,710 --> 00:14:04,400
>> Och för uppslags, väl vi vet
att slå upp i en länkad lista

289
00:14:04,400 --> 00:14:05,785
kan vara ett problem, eller hur?

290
00:14:05,785 --> 00:14:07,910
Vi måste söka igenom
det från början till slut.

291
00:14:07,910 --> 00:14:10,460
Det finns ingen slumpmässig
åtkomst i en länkad lista.

292
00:14:10,460 --> 00:14:15,610
Men om istället för att ha en länkad
lista där en uppslagning skulle vara O för n,

293
00:14:15,610 --> 00:14:19,590
vi nu har 10 länkade listor,
eller 1000 länkade listor,

294
00:14:19,590 --> 00:14:24,120
nu är det O n dividerat med 10,
eller O av n dividerat med 1000.

295
00:14:24,120 --> 00:14:26,940
>> Och medan vi pratade
teoretiskt om komplexitet

296
00:14:26,940 --> 00:14:30,061
vi bortser från konstanter, i den verkliga
värld dessa saker faktiskt roll,

297
00:14:30,061 --> 00:14:30,560
höger?

298
00:14:30,560 --> 00:14:33,080
Vi faktiskt kommer att märka
att detta sker

299
00:14:33,080 --> 00:14:36,610
att springa 10 gånger snabbare,
eller 1000 gånger snabbare,

300
00:14:36,610 --> 00:14:41,570
eftersom vi distribuerar en lång
kedja över 1.000 mindre kedjor.

301
00:14:41,570 --> 00:14:45,090
Och så varje gång vi måste söka
genom en av dessa kedjor vi kan för

302
00:14:45,090 --> 00:14:50,290
ignorera de 999 kedjorna vi inte bryr
om, och bara söka den.

303
00:14:50,290 --> 00:14:53,220
>> Vilket är i genomsnitt
vara 1000 gånger kortare.

304
00:14:53,220 --> 00:14:56,460
Och så är vi fortfarande sorts
går mot denna genomsnittliga fallet

305
00:14:56,460 --> 00:15:01,610
av att vara konstant tid, men
bara för att vi är hävstångseffekt

306
00:15:01,610 --> 00:15:03,730
dividera med några stora konstant faktor.

307
00:15:03,730 --> 00:15:05,804
Låt oss se hur detta kanske
faktiskt ser dock.

308
00:15:05,804 --> 00:15:08,720
Så det här var hash tabell vi hade
innan vi förklarade en hash tabell som

309
00:15:08,720 --> 00:15:10,270
var kan lagra 10 strängar.

310
00:15:10,270 --> 00:15:11,728
Vi kommer inte att göra det längre.

311
00:15:11,728 --> 00:15:13,880
Vi vet redan
begränsningar av denna metod.

312
00:15:13,880 --> 00:15:20,170
Nu har vår hash bord kommer att bli
en matris med 10 noder, pekare

313
00:15:20,170 --> 00:15:22,120
till cheferna för länkade listor.

314
00:15:22,120 --> 00:15:23,830
>> Och just nu är det noll.

315
00:15:23,830 --> 00:15:26,170
Var och en av dessa 10 pekare är noll.

316
00:15:26,170 --> 00:15:29,870
Det finns inget i vår
hash tabellen just nu.

317
00:15:29,870 --> 00:15:32,690
>> Nu börjar sätta några
saker i denna hash-tabell.

318
00:15:32,690 --> 00:15:35,440
Och låt oss se hur denna metod är
kommer att gynna oss lite.

319
00:15:35,440 --> 00:15:36,760
Låt oss nu hash Joey.

320
00:15:36,760 --> 00:15:40,210
Vi kommer att köra strängen Joey genom
en hash funktion och vi återvänder 6.

321
00:15:40,210 --> 00:15:41,200
Och vad gör vi nu?

322
00:15:41,200 --> 00:15:44,090
>> Väl arbetar nu med länkade listor,
vi inte arbetar med arrayer.

323
00:15:44,090 --> 00:15:45,881
Och när vi jobbar
med länkade listor vi

324
00:15:45,881 --> 00:15:49,790
vet att vi måste börja dynamiskt
tilldelning av utrymme och byggkedjor.

325
00:15:49,790 --> 00:15:54,020
Det blir liksom how-- de är kärnan
element för att bygga en länkad lista.

326
00:15:54,020 --> 00:15:57,670
Så låt oss dynamiskt
allokera utrymme för Joey,

327
00:15:57,670 --> 00:16:00,390
och sedan ska vi lägga honom till kedjan.

328
00:16:00,390 --> 00:16:03,170
>> Så nu ser vad vi har gjort.

329
00:16:03,170 --> 00:16:06,440
När vi hash Joey vi fick hashkod 6.

330
00:16:06,440 --> 00:16:11,790
Nu pekaren på array plats 6
pekar på huvudet på en länkad lista,

331
00:16:11,790 --> 00:16:14,900
och just nu är det den enda
element i en länkad lista.

332
00:16:14,900 --> 00:16:18,350
Och noden i den
länkad lista är Joey.

333
00:16:18,350 --> 00:16:22,300
>> Så om vi behöver slå upp Joey
senare, vi bara hash Joey igen,

334
00:16:22,300 --> 00:16:26,300
vi får 6 igen eftersom vår
hashfunktion är deterministisk.

335
00:16:26,300 --> 00:16:30,400
Och sedan börjar vi i spetsen
av den länkade listan pekade

336
00:16:30,400 --> 00:16:33,360
till genom array plats
6, och vi kan iterera

337
00:16:33,360 --> 00:16:35,650
över att försöka hitta Joey.

338
00:16:35,650 --> 00:16:37,780
Och om vi bygger vår
hashtabell effektivt,

339
00:16:37,780 --> 00:16:41,790
och vår hashfunktion effektivt
att distribuera data väl,

340
00:16:41,790 --> 00:16:45,770
i genomsnitt vart och ett av de länkade
listor vid varje array plats

341
00:16:45,770 --> 00:16:50,110
kommer att vara 1/10 storleken på om vi
bara haft det som en enda stor

342
00:16:50,110 --> 00:16:51,650
länkad lista med allt i den.

343
00:16:51,650 --> 00:16:55,670
>> Om vi ​​distribuerar den enorma länkade
Listan över 10 länkade listor

344
00:16:55,670 --> 00:16:57,760
varje lista kommer att vara 1/10 storlek.

345
00:16:57,760 --> 00:17:01,432
Och därmed 10 gånger snabbare
att söka igenom.

346
00:17:01,432 --> 00:17:02,390
Så låt oss göra det igen.

347
00:17:02,390 --> 00:17:04,290
Låt oss nu hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Och låt oss säga Ross, när vi gör det
hash-kod vi får tillbaka är 2.

349
00:17:07,540 --> 00:17:10,630
Nåväl vi dynamiskt allokera en
nya noden, sätter vi Ross i den noden,

350
00:17:10,630 --> 00:17:14,900
och vi säger nu array plats
2, i stället för att peka på null,

351
00:17:14,900 --> 00:17:18,579
pekar på huvudet av en länkad
lista vars enda nod är Ross.

352
00:17:18,579 --> 00:17:22,660
Och vi kan göra det här en gång till, vi
kan hash Rachel och få hashkod 4.

353
00:17:22,660 --> 00:17:25,490
malloc en ny nod, sätta Rachel i
noden, och säger en array plats

354
00:17:25,490 --> 00:17:27,839
4 pekar nu mot huvudet
av en länkad lista vars

355
00:17:27,839 --> 00:17:31,420
enda element råkar vara Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, men vad händer om
Vi har en kollision?

357
00:17:33,470 --> 00:17:38,560
Låt oss se hur vi hanterar kollisioner
med användning av separata följning.

358
00:17:38,560 --> 00:17:39,800
Låt oss hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Vi får hashkod 6.

360
00:17:41,094 --> 00:17:44,010
I vårt tidigare exempel var vi bara
lagring av strängar i arrayen.

361
00:17:44,010 --> 00:17:45,980
Detta var ett problem.

362
00:17:45,980 --> 00:17:48,444
>> Vi vill inte clobber
Joey, och vi har redan

363
00:17:48,444 --> 00:17:51,110
sett att vi kan få lite klustring
problem om vi försöker och steg

364
00:17:51,110 --> 00:17:52,202
genom och sond.

365
00:17:52,202 --> 00:17:54,660
Men vad händer om vi bara typ av
behandla detta på samma sätt, eller hur?

366
00:17:54,660 --> 00:17:57,440
Det är precis som att lägga ett element
till chefen för en länkad lista.

367
00:17:57,440 --> 00:18:00,220
Låt oss bara malloc utrymme för Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Vi ska säga Phoebes nästa pekaren pekar
till den gamla chefen för den länkade listan,

369
00:18:04,764 --> 00:18:07,180
och sedan 6 bara pekar på
ny chef för den länkade listan.

370
00:18:07,180 --> 00:18:10,150
Och nu ser har vi ändrat Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Vi kan nu lagra två
element med hashkod 6,

372
00:18:14,210 --> 00:18:17,170
och vi har inte några problem.

373
00:18:17,170 --> 00:18:20,147
>> Det är ganska mycket alla
finns att kedja.

374
00:18:20,147 --> 00:18:21,980
Och kedja är definitivt
den metod som är

375
00:18:21,980 --> 00:18:27,390
kommer att vara mest effektiva för dig om
du lagra data i en hash tabell.

376
00:18:27,390 --> 00:18:30,890
Men denna kombination av
arrayer och länkade listor

377
00:18:30,890 --> 00:18:36,080
tillsammans för att bilda en hashtabell verkligen
dramatiskt förbättrar din förmåga

378
00:18:36,080 --> 00:18:40,550
att lagra stora mängder data, och
mycket snabbt och effektivt söka

379
00:18:40,550 --> 00:18:41,630
genom dessa uppgifter.

380
00:18:41,630 --> 00:18:44,150
>> Det finns fortfarande ett mer
datastruktur ute

381
00:18:44,150 --> 00:18:48,700
som kanske till och med vara lite
bättre när det gäller att garantera

382
00:18:48,700 --> 00:18:51,920
att vår insertion, deletion, och
slå upp tider är ännu snabbare.

383
00:18:51,920 --> 00:18:55,630
Och vi ser att i en video på försök.

384
00:18:55,630 --> 00:18:58,930
Jag är Doug Lloyd, är detta CS50.

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