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

2
00:00:07,479 --> 00:00:09,367
Než se ponoříme do hash tabulky, pojďme

3
00:00:09,367 --> 00:00:11,196
první recenzi klady a zápory některých

4
00:00:11,196 --> 00:00:13,202
jednodušší datové struktury, počínaje

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

6
00:00:14,739 --> 00:00:16,869
Připomeňme si, že pole nám umožňují uchovávat

7
00:00:16,869 --> 00:00:18,644
prvky jednoho typu dat

8
00:00:18,644 --> 00:00:21,259
souvisle v paměti.

9
00:00:21,259 --> 00:00:24,115
Vzhledem k tomu, každý prvek je spojen s

10
00:00:24,115 --> 00:00:26,513
index, nebo místo,

11
00:00:26,513 --> 00:00:27,661
máme náhodný přístup ke všem

12
00:00:27,661 --> 00:00:28,860
prvků v poli.

13
00:00:28,860 --> 00:00:31,308
Jinými slovy, můžeme přistupovat jakýkoli prvek

14
00:00:31,308 --> 00:00:33,468
v jednom kroku do indexování

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

16
00:00:35,112 --> 00:00:37,224
To je velký problém, protože algoritmy

17
00:00:37,224 --> 00:00:39,204
jako binární vyhledávání závisí na náhodné

18
00:00:39,204 --> 00:00:40,570
přístup.

19
00:00:40,570 --> 00:00:43,130
Nevýhodou polí je, že jejich velikost

20
00:00:43,130 --> 00:00:44,380
je pevná.

21
00:00:44,380 --> 00:00:46,630
Vzhledem k tomu, pole ukládat data souvislý v

22
00:00:46,630 --> 00:00:49,490
paměť, je nutné zadat velikost pole

23
00:00:49,490 --> 00:00:50,600
při deklarovat pole.

24
00:00:50,600 --> 00:00:53,510
Ty jsou skutečně žádá provozní

25
00:00:53,510 --> 00:00:55,600
systém vyhradit příslušnou částku

26
00:00:55,600 --> 00:00:58,080
paměti pro elementy pole.

27
00:00:58,080 --> 00:01:00,240
Neexistuje žádná záruka, že více paměti,

28
00:01:00,240 --> 00:01:02,370
v těsné blízkosti svého pole, bude k dispozici

29
00:01:02,370 --> 00:01:03,480
pro pozdější použití.

30
00:01:03,480 --> 00:01:05,550
Takže pole nelze snadno pěstovat.

31
00:01:05,550 --> 00:01:07,715
Připomeňme si, že jsme se také dozvěděli o propojeny

32
00:01:07,715 --> 00:01:09,630
seznamy, které mohou růst, protože jejich

33
00:01:09,630 --> 00:01:12,430
prvky nejsou souvislé v paměti.

34
00:01:12,430 --> 00:01:14,680
Každý uzel v propojeném seznamu obsahuje

35
00:01:14,680 --> 00:01:16,620
prvek, který chceme uložit, jakož i

36
00:01:16,620 --> 00:01:18,976
ukazatel na následující prvek v

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

38
00:01:19,756 --> 00:01:22,560
Bohužel, cena, kterou jsme zaplatili za

39
00:01:22,560 --> 00:01:24,945
dynamické velikost je náhodný přístup k

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

41
00:01:26,460 --> 00:01:28,760
Aby bylo možné získat přístup k určité prvek,

42
00:01:28,760 --> 00:01:30,810
je nutné přejít na celý

43
00:01:30,810 --> 00:01:32,910
Seznam dokud požadovaný prvek je

44
00:01:32,910 --> 00:01:33,950
dosáhl.

45
00:01:33,950 --> 00:01:36,450
Takže, když jsem hledal číslo 9, já bych

46
00:01:36,450 --> 00:01:39,340
sledovat ukazatele z uzlu do uzlu,

47
00:01:39,340 --> 00:01:41,350
ověření, zda hodnota každého uzlu

48
00:01:41,350 --> 00:01:42,584
se rovná 9.

49
00:01:42,584 --> 00:01:46,303
Jako takový, v nejhorším případě, vyhledá je

50
00:01:46,303 --> 00:01:48,400
O (n), který je daleko od efektivní.

51
00:01:49,690 --> 00:01:51,630
Můžeme to udělat lépe než O (n), zatímco ještě

52
00:01:51,630 --> 00:01:53,470
což naše datová struktura roste přes

53
00:01:53,470 --> 00:01:54,560
čas?

54
00:01:54,560 --> 00:01:56,810
Hash tabulky nabídnout řešení.

55
00:01:56,810 --> 00:01:58,730
Hash tabulky jsou používány při rychlé

56
00:01:58,730 --> 00:02:00,820
vkládání, mazání a vyhledávání z

57
00:02:00,820 --> 00:02:01,910
prvky je prioritou.

58
00:02:01,910 --> 00:02:05,500
Teoreticky, vkládání, mazání a vyhledávání

59
00:02:05,500 --> 00:02:07,275
mohou být dokonce provedeno v konstantní

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

61
00:02:08,890 --> 00:02:11,120
Takže, co je hash tabulka vlastně je?

62
00:02:11,120 --> 00:02:13,170
Hash tabulka je jen pole spolu

63
00:02:13,170 --> 00:02:14,940
s funkcí, kterou budeme volat hash

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

65
00:02:16,440 --> 00:02:18,610
Funkce hash se část dat

66
00:02:18,610 --> 00:02:20,778
jako vstup, zavoláme tento klíč, a

67
00:02:20,778 --> 00:02:23,700
výstupy celé číslo, běžně označované

68
00:02:23,700 --> 00:02:24,895
jako hodnota hash.

69
00:02:24,895 --> 00:02:28,810
Hodnota hash mapuje naši klíč

70
00:02:28,810 --> 00:02:30,840
Zejména index v tabulce hash.

71
00:02:32,080 --> 00:02:34,330
Byste nejprve použít funkce hash

72
00:02:34,330 --> 00:02:36,410
určit, kde v tabulce hash, aby

73
00:02:36,410 --> 00:02:38,430
uložit daný klíč.

74
00:02:38,430 --> 00:02:41,030
Později, měli byste použít stejnou funkci hash

75
00:02:41,030 --> 00:02:42,950
zjistit, kde se v tabulce hash, aby

76
00:02:42,950 --> 00:02:45,010
hledat pro daný klíč.

77
00:02:45,010 --> 00:02:47,190
Z tohoto důvodu je důležité, aby hash

78
00:02:47,190 --> 00:02:49,840
Funkce se chová konzistentně a výstupy

79
00:02:49,840 --> 00:02:53,130
stejný hash hodnotu za stejných kláves.

80
00:02:53,130 --> 00:02:54,970
Uvědomte si, že hashovací tabulky mohou být použity k

81
00:02:54,970 --> 00:02:56,310
ukládání dat všech typů.

82
00:02:56,310 --> 00:02:58,330
Ale pro zjednodušení věci, budeme soustředit na

83
00:02:58,330 --> 00:02:59,830
struny pro teď.

84
00:02:59,830 --> 00:03:01,630
Zde je jednoduchý hash funkce pro řetězce.

85
00:03:03,570 --> 00:03:05,590
Tato funkce hash vypočte hash

86
00:03:05,590 --> 00:03:07,410
funkce na základě prvního písmene

87
00:03:07,410 --> 00:03:07,910
klíč.

88
00:03:09,090 --> 00:03:11,300
"Apple" začíná písmenem "A", tak je to

89
00:03:11,300 --> 00:03:13,200
mapovány na indexu 0 v tabulce hash.

90
00:03:14,270 --> 00:03:17,402
Podobně, "banana" je namapován na index 1,

91
00:03:17,402 --> 00:03:19,829
a "kočka" je mapována na index 2.

92
00:03:21,750 --> 00:03:23,790
Je-li přítel zeptá, zda slovo "pes" je v

93
00:03:23,790 --> 00:03:26,150
tabulka, budeme vstupní "pes" do hash

94
00:03:26,150 --> 00:03:28,390
funkce, která vypíše hodnoty hash

95
00:03:28,390 --> 00:03:29,790
ze dne 3..

96
00:03:29,790 --> 00:03:33,150
Vzhledem k tomu, "pes" není uložen na indexu 3, jsme

97
00:03:33,150 --> 00:03:35,330
lze s jistotou říci, že "pes" není

98
00:03:35,330 --> 00:03:36,340
v tabulce,

99
00:03:36,340 --> 00:03:38,260
i když jsme jen zkontrolovat jeden z

100
00:03:38,260 --> 00:03:40,120
hash tabulky je 26 indexy.

101
00:03:42,170 --> 00:03:44,280
Čas hodit klíče do věcí.

102
00:03:44,280 --> 00:03:46,130
Co když chceme uložit "mravence" do

103
00:03:46,130 --> 00:03:47,820
Tabulka stejně?

104
00:03:47,820 --> 00:03:51,730
"Ant" hash index 0, stejně jako "jablko" udělal.

105
00:03:51,730 --> 00:03:53,890
Toto je příklad kolize,

106
00:03:53,890 --> 00:03:56,419
Výsledkem dvou tlačítek zatřiďování do stejné

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

108
00:03:58,140 --> 00:04:00,040
I když vaše hash tabulka je větší než

109
00:04:00,040 --> 00:04:01,980
nastavit vaše data, a vy jste si vybrali dobrý

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

111
00:04:03,060 --> 00:04:04,560
budete ještě potřebovat plán pro nakládání s

112
00:04:04,560 --> 00:04:06,420
kolize, zda a kdy se objeví.

113
00:04:07,440 --> 00:04:09,810
Pojďme diskutovat o výhodách a nevýhodách obou

114
00:04:09,810 --> 00:04:12,360
společné metody pro řešení kolizí:

115
00:04:12,360 --> 00:04:15,230
lineární snímání a oddělené zřetězení.

116
00:04:15,230 --> 00:04:17,430
S lineární snímání, jestliže klíč hash na

117
00:04:17,430 --> 00:04:19,340
stejný index jako dříve uložené

118
00:04:19,340 --> 00:04:21,840
klíč je přiřazen další dostupné

119
00:04:21,840 --> 00:04:22,862
slot v tabulce.

120
00:04:22,862 --> 00:04:27,353
Takže, "mravenec" je nyní uložena na indexu 3, protože

121
00:04:27,353 --> 00:04:30,850
indexy 0, 1 a 2 jsou již v provozu.

122
00:04:32,780 --> 00:04:34,610
A pokud se pokusíte uložit třetí slovo, které

123
00:04:34,610 --> 00:04:36,410
začíná na písmeno "A", je to zadáno

124
00:04:36,410 --> 00:04:41,263
index 4, protože indexy 0, 1, 2, a 3

125
00:04:41,263 --> 00:04:42,530
jsou plné.

126
00:04:42,530 --> 00:04:44,300
Jak můžete vidět i z tohoto jednoduchého

127
00:04:44,300 --> 00:04:46,580
Například jednou kolize nastane, vás

128
00:04:46,580 --> 00:04:48,400
výrazně zvýší pravděpodobnost, že

129
00:04:48,400 --> 00:04:50,370
další kolizi dojde ve stejném

130
00:04:50,370 --> 00:04:51,630
oblast.

131
00:04:51,630 --> 00:04:53,530
To se nazývá shlukování, a to

132
00:04:53,530 --> 00:04:56,200
Závažným nedostatkem na lineární snímání.

133
00:04:56,200 --> 00:04:59,240
Navíc, nejhorší případ vložení, mazání,

134
00:04:59,240 --> 00:05:02,008
a doba vyhledávání se převádí na O (n),

135
00:05:02,008 --> 00:05:04,200
jako další k dispozici slot může mít

136
00:05:04,200 --> 00:05:06,225
případně jako poslední slot v tabulce.

137
00:05:06,225 --> 00:05:09,210
Možná samostatné řetězení nabídne více

138
00:05:09,210 --> 00:05:10,220
přesvědčivé řešení.

139
00:05:10,220 --> 00:05:13,060
V samostatném modelu řetězení, hash

140
00:05:13,060 --> 00:05:14,930
tabulka je vlastně pole ukazatelů na

141
00:05:14,930 --> 00:05:16,220
spojové seznamy.

142
00:05:16,220 --> 00:05:18,350
Pokud dojde ke kolizi, klíč může být

143
00:05:18,350 --> 00:05:20,760
vložena v konstantním čase v čele

144
00:05:20,760 --> 00:05:22,270
vhodné spojový seznam.

145
00:05:23,420 --> 00:05:25,310
Co se stane teď, když jsme se hledat pro "jablko"

146
00:05:25,310 --> 00:05:26,900
v tabulce hash?

147
00:05:26,900 --> 00:05:28,940
V nejhorším případě musíme projít

148
00:05:28,940 --> 00:05:32,530
Celý spojový seznam, počínaje indexem 0..

149
00:05:32,530 --> 00:05:34,210
Vyhledávací čas nejhorší případ pro hash

150
00:05:34,210 --> 00:05:35,890
tabulka, která používá oddělené zřetězení je

151
00:05:35,890 --> 00:05:38,580
tedy O (n / k), kde k je

152
00:05:38,580 --> 00:05:39,687
velikost tabulky hash.

153
00:05:39,687 --> 00:05:42,940
Počkejte, k je konstanta.

154
00:05:42,940 --> 00:05:46,280
Takže O (n / k) je opravdu jen O (n),

155
00:05:46,280 --> 00:05:47,940
které bylo vyhledávání doba nejhorší případ pro

156
00:05:47,940 --> 00:05:49,320
spojový seznam.

157
00:05:49,320 --> 00:05:50,770
Už opravdu jsme prošli všechny

158
00:05:50,770 --> 00:05:52,370
potíže učení o hash tabulky

159
00:05:52,370 --> 00:05:54,927
jen aby skončil tam, kde jsme začali?

160
00:05:54,927 --> 00:05:56,975
To může být případ od teoretické

161
00:05:56,975 --> 00:05:59,087
perspektiva, ale v reálném světě,

162
00:05:59,087 --> 00:06:01,199
O (n / k) může být obrovské zlepšení oproti

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

164
00:06:03,257 --> 00:06:05,687
Přemýšlejte o tom tímto způsobem: Předpokládejme, že k je

165
00:06:05,687 --> 00:06:08,360
10 - byste raději čekat 100 sekund

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

167
00:06:11,076 --> 00:06:13,252
10 sekund od aplikace Microsoft Word dokončit

168
00:06:13,252 --> 00:06:15,608
kontrola pravopisu dokumentu.

169
00:06:15,608 --> 00:06:17,368
Jak jste právě viděli, řešení kolizí

170
00:06:17,368 --> 00:06:19,018
znamená jeden druh lineární hledání nebo

171
00:06:19,018 --> 00:06:20,558
další, což zpomaluje věci dolů

172
00:06:20,558 --> 00:06:23,280
výrazně.

173
00:06:23,280 --> 00:06:25,470
Proto, budete chtít vybrat hash

174
00:06:25,470 --> 00:06:27,470
funkce, která minimalizuje možnost

175
00:06:27,470 --> 00:06:29,170
kolize vyskytující se v první řadě.

176
00:06:30,540 --> 00:06:32,120
Zde jsou některé vlastnosti dobrého hash

177
00:06:32,120 --> 00:06:33,400
funkce je třeba mít na paměti.

178
00:06:34,610 --> 00:06:36,590
Dobrý hashovací funkce by měly využívat

179
00:06:36,590 --> 00:06:38,830
všechny informace poskytnuté daný klíč

180
00:06:38,830 --> 00:06:40,890
, aby se maximalizoval počet

181
00:06:40,890 --> 00:06:42,960
Možné hodnoty hash.

182
00:06:42,960 --> 00:06:45,540
Například, když jsme měli dva řetězce, "kočka"

183
00:06:45,540 --> 00:06:47,980
a "housenka", tak chceme, aby hash

184
00:06:47,980 --> 00:06:50,190
na různých místech na stole.

185
00:06:50,190 --> 00:06:52,410
Je-li funkce hash vzal v úvahu pouze

186
00:06:52,410 --> 00:06:54,860
První jeden, dva, nebo dokonce tři písmena

187
00:06:54,860 --> 00:06:57,290
z řetězců, kolize by mohlo dojít,

188
00:06:57,290 --> 00:06:58,970
neboť obě slova začínají na stejné

189
00:06:58,970 --> 00:06:59,560
tři písmena.

190
00:07:01,110 --> 00:07:03,100
Hash hodnoty by měly být rovnoměrně

191
00:07:03,100 --> 00:07:04,790
přes hash tabulky.

192
00:07:04,790 --> 00:07:06,300
Tím se sníží délku spojené

193
00:07:06,300 --> 00:07:08,050
seznamy by měly srážkám dochází.

194
00:07:09,390 --> 00:07:11,490
Je to také dobré znamení, pokud vaše hash hodnota

195
00:07:11,490 --> 00:07:13,600
je schopen generovat velmi odlišné

196
00:07:13,600 --> 00:07:15,660
hash hodnoty pro podobné klíče,

197
00:07:15,660 --> 00:07:17,250
takže kolize mnohem méně pravděpodobné.

198
00:07:18,420 --> 00:07:21,110
Naším cílem je rychlé vložení, mazání,

199
00:07:21,110 --> 00:07:22,100
a vyhledávání.

200
00:07:22,100 --> 00:07:24,060
Hašovací funkce hraje klíčovou roli v

201
00:07:24,060 --> 00:07:25,520
Každý z těchto procesů a bude

202
00:07:25,520 --> 00:07:26,735
volal velmi často.

203
00:07:26,735 --> 00:07:29,620
Proto se ujistěte, že používá jen velmi

204
00:07:29,620 --> 00:07:32,160
Jednoduchá a rychlá operace, aby se minimalizovalo běh

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

206
00:07:33,360 --> 00:07:34,560
Doufám, že jste si užili tento krátký

207
00:07:34,560 --> 00:07:36,540
úvod do hash tabulky.

208
00:07:36,540 --> 00:07:41,189
Mé jméno je Lauren, a to je CS50.