1
00:00:06,979 --> 00:00:07,479
[NOISE].

2
00:00:07,479 --> 00:00:09,367
Før dykking i hash tabeller, la oss

3
00:00:09,367 --> 00:00:11,196
først gjennom fordeler og ulemper av noen

4
00:00:11,196 --> 00:00:13,202
enklere datastrukturer, som starter med

5
00:00:13,202 --> 00:00:14,739
arrays.

6
00:00:14,739 --> 00:00:16,869
Husker at arrays tillate oss å lagre

7
00:00:16,869 --> 00:00:18,644
elementer av en enkelt datatype

8
00:00:18,644 --> 00:00:21,259
contiguously i minnet.

9
00:00:21,259 --> 00:00:24,115
Fordi hvert element er forbundet med

10
00:00:24,115 --> 00:00:26,513
en indeks, eller plassering,

11
00:00:26,513 --> 00:00:27,661
Vi har direkte tilgang til alle

12
00:00:27,661 --> 00:00:28,860
elementer i en matrise.

13
00:00:28,860 --> 00:00:31,308
Med andre ord, kan vi få tilgang til noe element

14
00:00:31,308 --> 00:00:33,468
i et enkelt trinn ved å indeksere inn i det

15
00:00:33,468 --> 00:00:35,112
array.

16
00:00:35,112 --> 00:00:37,224
Dette er en stor avtale, fordi algoritmer

17
00:00:37,224 --> 00:00:39,204
som binære søk avhenge av tilfeldig

18
00:00:39,204 --> 00:00:40,570
tilgang.

19
00:00:40,570 --> 00:00:43,130
En ulempe av matriser er at deres størrelse

20
00:00:43,130 --> 00:00:44,380
er fast.

21
00:00:44,380 --> 00:00:46,630
Fordi arrays lagre data contiguously i

22
00:00:46,630 --> 00:00:49,490
minne, må du angi en rekke størrelse

23
00:00:49,490 --> 00:00:50,600
når du erklærer matrisen.

24
00:00:50,600 --> 00:00:53,510
Du er effektivt å spørre drifts

25
00:00:53,510 --> 00:00:55,600
system for å reservere det aktuelle beløpet

26
00:00:55,600 --> 00:00:58,080
minne for tabellens elementer.

27
00:00:58,080 --> 00:01:00,240
Det er ingen garanti for at mer minne,

28
00:01:00,240 --> 00:01:02,370
ved siden av din array, vil være tilgjengelig

29
00:01:02,370 --> 00:01:03,480
for senere bruk.

30
00:01:03,480 --> 00:01:05,550
Så arrays kan ikke lett vokse.

31
00:01:05,550 --> 00:01:07,715
Husker at vi også lært om koblede

32
00:01:07,715 --> 00:01:09,630
lister, som kan vokse fordi deres

33
00:01:09,630 --> 00:01:12,430
elementer er ikke sammenhengende i minnet.

34
00:01:12,430 --> 00:01:14,680
Hver node i en lenket liste inneholder

35
00:01:14,680 --> 00:01:16,620
element som vi ønsker å oppbevare, samt

36
00:01:16,620 --> 00:01:18,976
en peker til den etterfølgende element i

37
00:01:18,976 --> 00:01:19,756
listen.

38
00:01:19,756 --> 00:01:22,560
Dessverre, den prisen vi har betalt for

39
00:01:22,560 --> 00:01:24,945
dynamisk størrelse er tilfeldig tilgang til

40
00:01:24,945 --> 00:01:26,460
elementer.

41
00:01:26,460 --> 00:01:28,760
For å få tilgang til et visst element,

42
00:01:28,760 --> 00:01:30,810
det er nødvendig å traversere hele

43
00:01:30,810 --> 00:01:32,910
listen inntil det ønskede element er

44
00:01:32,910 --> 00:01:33,950
nådd.

45
00:01:33,950 --> 00:01:36,450
Så, hvis jeg leter etter antall 9, hadde jeg

46
00:01:36,450 --> 00:01:39,340
følg pekere fra node til node,

47
00:01:39,340 --> 00:01:41,350
sjekke om verdien av hver node

48
00:01:41,350 --> 00:01:42,584
er lik 9.

49
00:01:42,584 --> 00:01:46,303
Som sådan, i verste fall, slå opp er

50
00:01:46,303 --> 00:01:48,400
O (n), som er langt fra effektiv.

51
00:01:49,690 --> 00:01:51,630
Kan vi gjøre det bedre enn O (n) mens de fortsatt

52
00:01:51,630 --> 00:01:53,470
slik at vår datastruktur for å vokse over

53
00:01:53,470 --> 00:01:54,560
tid?

54
00:01:54,560 --> 00:01:56,810
Hash tabeller tilby en løsning.

55
00:01:56,810 --> 00:01:58,730
Hash tabeller brukes når rask

56
00:01:58,730 --> 00:02:00,820
innsetting, sletting, og oppslag av

57
00:02:00,820 --> 00:02:01,910
elementene er prioritert.

58
00:02:01,910 --> 00:02:05,500
I teorien, innsetting, sletting, og oppslag

59
00:02:05,500 --> 00:02:07,275
kan til og med bli oppnådd i konstant

60
00:02:07,275 --> 00:02:08,890
tid.

61
00:02:08,890 --> 00:02:11,120
Så, hva er en hash table likevel?

62
00:02:11,120 --> 00:02:13,170
En hash table er bare en matrise kombinert

63
00:02:13,170 --> 00:02:14,940
med en funksjon, som vi vil kalle den hash

64
00:02:14,940 --> 00:02:15,440
funksjon.

65
00:02:16,440 --> 00:02:18,610
Hash-funksjonen tar en bit av data

66
00:02:18,610 --> 00:02:20,778
som input, vil vi kalle dette en nøkkel, og

67
00:02:20,778 --> 00:02:23,700
sender ut et helt tall, ofte referert til

68
00:02:23,700 --> 00:02:24,895
som en hash-verdi.

69
00:02:24,895 --> 00:02:28,810
Hash-verdi kartene våre nøkkelen til en

70
00:02:28,810 --> 00:02:30,840
Særlig indeksen i hash table.

71
00:02:32,080 --> 00:02:34,330
Du ville i utgangspunktet bruke hash-funksjon for å

72
00:02:34,330 --> 00:02:36,410
bestemme hvor i hash tabellen til

73
00:02:36,410 --> 00:02:38,430
lagre en gitt nøkkel.

74
00:02:38,430 --> 00:02:41,030
Senere vil du bruke den samme hash-funksjon

75
00:02:41,030 --> 00:02:42,950
å bestemme hvor i hash tabellen til

76
00:02:42,950 --> 00:02:45,010
søke etter en gitt nøkkel.

77
00:02:45,010 --> 00:02:47,190
Av denne grunn er det avgjørende at en hash

78
00:02:47,190 --> 00:02:49,840
funksjon oppfører seg konsekvent og utganger

79
00:02:49,840 --> 00:02:53,130
samme hash-verdi for identiske nøkler.

80
00:02:53,130 --> 00:02:54,970
Vet at hash tabeller kan brukes til

81
00:02:54,970 --> 00:02:56,310
lagre data av alle typer.

82
00:02:56,310 --> 00:02:58,330
Men for å forenkle ting, vil vi fokusere på

83
00:02:58,330 --> 00:02:59,830
strenger for nå.

84
00:02:59,830 --> 00:03:01,630
Her er en enkel hash-funksjon for strenger.

85
00:03:03,570 --> 00:03:05,590
Denne hash-funksjon beregner en hash

86
00:03:05,590 --> 00:03:07,410
funksjon basert på den første bokstaven i

87
00:03:07,410 --> 00:03:07,910
tasten.

88
00:03:09,090 --> 00:03:11,300
"Apple" begynner med bokstaven "A", så det er

89
00:03:11,300 --> 00:03:13,200
kartlagt til indeks 0 i hash tabellen.

90
00:03:14,270 --> 00:03:17,402
Tilsvarende er "banan" kartlagt å indeksere en,

91
00:03:17,402 --> 00:03:19,829
og "cat" er kartlagt til å indeksere to.

92
00:03:21,750 --> 00:03:23,790
Hvis en venn spør om ordet "hund" er i

93
00:03:23,790 --> 00:03:26,150
bordet, vil vi input "hund" i hash

94
00:03:26,150 --> 00:03:28,390
funksjon, som vil sende ut en hash-verdi

95
00:03:28,390 --> 00:03:29,790
av tre.

96
00:03:29,790 --> 00:03:33,150
Siden "hund" ikke lagres på indeks 3, vi

97
00:03:33,150 --> 00:03:35,330
kan trygt si at "hunden" er ikke

98
00:03:35,330 --> 00:03:36,340
i tabellen

99
00:03:36,340 --> 00:03:38,260
selv om vi har bare sjekket en av de

100
00:03:38,260 --> 00:03:40,120
hash tabellen 26 indekser.

101
00:03:42,170 --> 00:03:44,280
Tid for å kaste en nøkkel inn i ting.

102
00:03:44,280 --> 00:03:46,130
Hva hvis vi ønsker å lagre "maur" inn i

103
00:03:46,130 --> 00:03:47,820
tabellen også?

104
00:03:47,820 --> 00:03:51,730
"Ant" hasher til indeks 0, akkurat som "eple" gjorde.

105
00:03:51,730 --> 00:03:53,890
Dette er et eksempel på en kollisjon, er

106
00:03:53,890 --> 00:03:56,419
produktet av to nøkler hashing til samme

107
00:03:56,419 --> 00:03:57,080
indeks.

108
00:03:58,140 --> 00:04:00,040
Selv om din hash tabellen er større enn

109
00:04:00,040 --> 00:04:01,980
loggeren med, og du har valgt en god

110
00:04:01,980 --> 00:04:03,060
hash-funksjon,

111
00:04:03,060 --> 00:04:04,560
du fortsatt trenger en plan for å håndtere

112
00:04:04,560 --> 00:04:06,420
kollisjoner, hvis og når de oppstår.

113
00:04:07,440 --> 00:04:09,810
La oss diskutere fordeler og ulemper med to

114
00:04:09,810 --> 00:04:12,360
vanlige metoder for å løse kollisjoner:

115
00:04:12,360 --> 00:04:15,230
lineær sondering og separat kjeding.

116
00:04:15,230 --> 00:04:17,430
Med lineær sondering, hvis en nøkkel hashes til

117
00:04:17,430 --> 00:04:19,340
samme indeks som den tidligere lagret

118
00:04:19,340 --> 00:04:21,840
nøkkel, er det tildelt den neste tilgjengelige

119
00:04:21,840 --> 00:04:22,862
spalte i tabellen.

120
00:04:22,862 --> 00:04:27,353
Så, er "maur" nå lagret på index 3, siden

121
00:04:27,353 --> 00:04:30,850
indekser 0, 1 og 2 allerede var i bruk.

122
00:04:32,780 --> 00:04:34,610
Og hvis vi prøver å lagre et tredje ord som

123
00:04:34,610 --> 00:04:36,410
starter med bokstaven "A", er det tildelt

124
00:04:36,410 --> 00:04:41,263
å index 4, ettersom indekser 0, 1, 2 og 3.

125
00:04:41,263 --> 00:04:42,530
er full.

126
00:04:42,530 --> 00:04:44,300
Som du kan se selv fra denne enkle

127
00:04:44,300 --> 00:04:46,580
eksempel når det oppstår en kollisjon, du

128
00:04:46,580 --> 00:04:48,400
betydelig øke sjansene for at

129
00:04:48,400 --> 00:04:50,370
en annen kollisjon vil skje i samme

130
00:04:50,370 --> 00:04:51,630
området.

131
00:04:51,630 --> 00:04:53,530
Dette kalles clustering, og det er en

132
00:04:53,530 --> 00:04:56,200
alvorlig ulempe til lineær sondering.

133
00:04:56,200 --> 00:04:59,240
Videre worst-case innsetting, sletting,

134
00:04:59,240 --> 00:05:02,008
og oppslags ganger har delegert til O (n),

135
00:05:02,008 --> 00:05:04,200
som den neste tilgjengelige sporet kan ha

136
00:05:04,200 --> 00:05:06,225
potensielt vært den siste spalte i tabellen.

137
00:05:06,225 --> 00:05:09,210
Kanskje separat kjeding vil tilby en mer

138
00:05:09,210 --> 00:05:10,220
overbevisende løsning.

139
00:05:10,220 --> 00:05:13,060
I separat kjeding modell, hash

140
00:05:13,060 --> 00:05:14,930
Tabellen er faktisk en rekke pekere til

141
00:05:14,930 --> 00:05:16,220
lenkede lister.

142
00:05:16,220 --> 00:05:18,350
Når det oppstår en kollisjon, kan nøkkelen bli

143
00:05:18,350 --> 00:05:20,760
innsatt i konstant tid på hodet av

144
00:05:20,760 --> 00:05:22,270
riktig lenket liste.

145
00:05:23,420 --> 00:05:25,310
Hva skjer nå når vi søker etter "apple"

146
00:05:25,310 --> 00:05:26,900
i hash table?

147
00:05:26,900 --> 00:05:28,940
I verste fall må vi traversere

148
00:05:28,940 --> 00:05:32,530
Hele lenket liste, starter på indeksen 0.

149
00:05:32,530 --> 00:05:34,210
Den verst tenkelige oppslag tid for en hash

150
00:05:34,210 --> 00:05:35,890
tabell som bruker separat kjeding er

151
00:05:35,890 --> 00:05:38,580
Derfor O (n / k), der k er

152
00:05:38,580 --> 00:05:39,687
Størrelsen på hash-tabellen.

153
00:05:39,687 --> 00:05:42,940
Vent litt, er k en konstant.

154
00:05:42,940 --> 00:05:46,280
Så O (n / k) er egentlig bare O (n),

155
00:05:46,280 --> 00:05:47,940
som var det verst tenkelige oppslag tid for

156
00:05:47,940 --> 00:05:49,320
en lenket liste.

157
00:05:49,320 --> 00:05:50,770
Har vi virkelig gått gjennom alle

158
00:05:50,770 --> 00:05:52,370
bryet med å lære om hash tabeller

159
00:05:52,370 --> 00:05:54,927
bare for å ende opp tilbake der vi startet?

160
00:05:54,927 --> 00:05:56,975
Det kan være tilfelle fra en teoretisk

161
00:05:56,975 --> 00:05:59,087
perspektiv, men i den virkelige verden,

162
00:05:59,087 --> 00:06:01,199
O (n / k) kan være en stor forbedring i forhold til

163
00:06:01,199 --> 00:06:03,257
O (n).

164
00:06:03,257 --> 00:06:05,687
Tenk på det på denne måten: anta at k er

165
00:06:05,687 --> 00:06:08,360
10 - ville du heller vente 100 sekunder

166
00:06:08,360 --> 00:06:11,076
eller 100 / k?

167
00:06:11,076 --> 00:06:13,252
10 sekunder fra Microsoft Word til å fullføre

168
00:06:13,252 --> 00:06:15,608
stavekontroll dokumentet.

169
00:06:15,608 --> 00:06:17,368
Som du nettopp så, løse kollisjoner

170
00:06:17,368 --> 00:06:19,018
innebærer en form for lineær søk eller

171
00:06:19,018 --> 00:06:20,558
en annen, noe som bremser ned ting

172
00:06:20,558 --> 00:06:23,280
betraktelig.

173
00:06:23,280 --> 00:06:25,470
Derfor, vil du ønsker å velge en hash

174
00:06:25,470 --> 00:06:27,470
funksjon som minimerer sjansen for

175
00:06:27,470 --> 00:06:29,170
kollisjoner oppstår i første omgang.

176
00:06:30,540 --> 00:06:32,120
Her er noen egenskaper ved god hash

177
00:06:32,120 --> 00:06:33,400
funksjoner for å huske på.

178
00:06:34,610 --> 00:06:36,590
En god hash-funksjon bør gjøre bruk av

179
00:06:36,590 --> 00:06:38,830
all informasjon gitt av en gitt nøkkel

180
00:06:38,830 --> 00:06:40,890
for å maksimere antallet

181
00:06:40,890 --> 00:06:42,960
mulige hash verdier.

182
00:06:42,960 --> 00:06:45,540
For eksempel, hvis vi hadde to strenger, "katt"

183
00:06:45,540 --> 00:06:47,980
og "caterpillar", ville vi vil ha dem til hasj

184
00:06:47,980 --> 00:06:50,190
til forskjellige steder på bordet.

185
00:06:50,190 --> 00:06:52,410
Hvis en hash-funksjon bare tok hensyn

186
00:06:52,410 --> 00:06:54,860
den første en, to, eller tre bokstaver

187
00:06:54,860 --> 00:06:57,290
av strengene, vil en kollisjon oppstår

188
00:06:57,290 --> 00:06:58,970
siden begge ord starter med den samme

189
00:06:58,970 --> 00:06:59,560
tre bokstaver.

190
00:07:01,110 --> 00:07:03,100
Hash verdier skal fordeles jevnt

191
00:07:03,100 --> 00:07:04,790
over hash tabellen.

192
00:07:04,790 --> 00:07:06,300
Dette vil redusere lengden på koblede

193
00:07:06,300 --> 00:07:08,050
listene bør kollisjoner oppstår.

194
00:07:09,390 --> 00:07:11,490
Det er også et godt tegn hvis hash-verdi

195
00:07:11,490 --> 00:07:13,600
er i stand til å generere svært forskjellige

196
00:07:13,600 --> 00:07:15,660
hash verdier for tilsvarende tastene,

197
00:07:15,660 --> 00:07:17,250
gjør kollisjoner mye mindre sannsynlig.

198
00:07:18,420 --> 00:07:21,110
Vårt mål er rask innsetting, sletting,

199
00:07:21,110 --> 00:07:22,100
og oppslag.

200
00:07:22,100 --> 00:07:24,060
Hash-funksjon spiller en avgjørende rolle i

201
00:07:24,060 --> 00:07:25,520
hver av disse prosesser og vil bli

202
00:07:25,520 --> 00:07:26,735
kalles veldig ofte.

203
00:07:26,735 --> 00:07:29,620
Derfor, sørg for at den sysselsetter bare veldig

204
00:07:29,620 --> 00:07:32,160
enkle, raske operasjoner for å minimere løp

205
00:07:32,160 --> 00:07:33,360
tid.

206
00:07:33,360 --> 00:07:34,560
Jeg håper du har hatt glede av denne korte

207
00:07:34,560 --> 00:07:36,540
introduksjon til hasj tabeller.

208
00:07:36,540 --> 00:07:41,189
Mitt navn er Lauren, og dette er CS50.