1
00:00:06,979 --> 00:00:07,479
[Шуму].

2
00:00:07,479 --> 00:00:09,367
Перад апусканнем у хэш-табліц, давайце

3
00:00:09,367 --> 00:00:11,196
спачатку разгледзім плюсы і мінусы некаторых

4
00:00:11,196 --> 00:00:13,202
простыя структуры дадзеных, пачынаючы з

5
00:00:13,202 --> 00:00:14,739
масівы.

6
00:00:14,739 --> 00:00:16,869
Нагадаем, што масівы дазваляюць нам захоўваць

7
00:00:16,869 --> 00:00:18,644
элементы аднаго тыпу дадзеных

8
00:00:18,644 --> 00:00:21,259
бесперапынна ў памяці.

9
00:00:21,259 --> 00:00:24,115
Паколькі кожны элемент звязаны з

10
00:00:24,115 --> 00:00:26,513
індэкс, або месца,

11
00:00:26,513 --> 00:00:27,661
у нас ёсць выпадковы доступ да ўсіх

12
00:00:27,661 --> 00:00:28,860
элементы масіва.

13
00:00:28,860 --> 00:00:31,308
Іншымі словамі, мы можам атрымаць доступ да любога элементу

14
00:00:31,308 --> 00:00:33,468
ў адным кроку ад індэксацыі ў

15
00:00:33,468 --> 00:00:35,112
масівам.

16
00:00:35,112 --> 00:00:37,224
Гэта вялікая справа, таму што алгарытмы

17
00:00:37,224 --> 00:00:39,204
як бінарнага пошуку залежаць ад выпадковых

18
00:00:39,204 --> 00:00:40,570
доступу.

19
00:00:40,570 --> 00:00:43,130
Недахопам масіваў з'яўляецца тое, што іх памер

20
00:00:43,130 --> 00:00:44,380
фіксавана.

21
00:00:44,380 --> 00:00:46,630
Паколькі дадзеныя масівы магазін бесперапынна ў

22
00:00:46,630 --> 00:00:49,490
памяці, неабходна ўказаць памер масіва

23
00:00:49,490 --> 00:00:50,600
пры аб'яўленні масіва.

24
00:00:50,600 --> 00:00:53,510
Вы эфектыўна пытаючыся аперацыйнай

25
00:00:53,510 --> 00:00:55,600
Сістэма зарэзерваваць адпаведную колькасць

26
00:00:55,600 --> 00:00:58,080
памяці для элементаў масіва.

27
00:00:58,080 --> 00:01:00,240
Там няма ніякай гарантыі, што больш памяці,

28
00:01:00,240 --> 00:01:02,370
побач з вашага масіва, будуць даступныя

29
00:01:02,370 --> 00:01:03,480
для наступнага выкарыстання.

30
00:01:03,480 --> 00:01:05,550
Так масівы не могуць лёгка расці.

31
00:01:05,550 --> 00:01:07,715
Нагадаем, што мы таксама даведаліся пра звязаныя

32
00:01:07,715 --> 00:01:09,630
спісы, якія могуць расці, таму што іх

33
00:01:09,630 --> 00:01:12,430
элементы не з'яўляюцца сумежнымі ў памяці.

34
00:01:12,430 --> 00:01:14,680
Кожны вузел у звязаным спісе ўтрымлівае

35
00:01:14,680 --> 00:01:16,620
элемент, які мы хочам захоўваць, а таксама

36
00:01:16,620 --> 00:01:18,976
паказальнік на наступнага элемента ў

37
00:01:18,976 --> 00:01:19,756
спіс.

38
00:01:19,756 --> 00:01:22,560
На жаль, цана, якую мы заплацілі за

39
00:01:22,560 --> 00:01:24,945
дынамічны памер адвольны доступ да

40
00:01:24,945 --> 00:01:26,460
элементы.

41
00:01:26,460 --> 00:01:28,760
Для таго, каб атрымаць доступ пэўны элемент,

42
00:01:28,760 --> 00:01:30,810
неабходна прайсці па ўсім

43
00:01:30,810 --> 00:01:32,910
спіс, пакуль шуканы элемент не з'яўляецца

44
00:01:32,910 --> 00:01:33,950
дасягнуты.

45
00:01:33,950 --> 00:01:36,450
Так што, калі я шукаю колькасці 9, я б

46
00:01:36,450 --> 00:01:39,340
прытрымлівайцеся паказальнікі ад вузла да вузла,

47
00:01:39,340 --> 00:01:41,350
праверкі, ці з'яўляецца значэнне кожнага вузла

48
00:01:41,350 --> 00:01:42,584
роўна 9.

49
00:01:42,584 --> 00:01:46,303
Такім чынам, у горшым выпадку, паглядзець гэта

50
00:01:46,303 --> 00:01:48,400
O (N), якое далёка не эфектыўнымі.

51
00:01:49,690 --> 00:01:51,630
Ці можам мы зрабіць лепш, чым O (N) у той жа час

52
00:01:51,630 --> 00:01:53,470
дазваляе наша структура дадзеных расці на працягу

53
00:01:53,470 --> 00:01:54,560
раз?

54
00:01:54,560 --> 00:01:56,810
Хэш-табліцы прапанаваць рашэнне.

55
00:01:56,810 --> 00:01:58,730
Выкарыстоўваюцца Хэш-табліцы, калі хуткі

56
00:01:58,730 --> 00:02:00,820
ўстаўкі, выдалення і пошуку з

57
00:02:00,820 --> 00:02:01,910
элементы з'яўляецца прыярытэтным.

58
00:02:01,910 --> 00:02:05,500
У тэорыі, устаўка, выдаленне і пошук

59
00:02:05,500 --> 00:02:07,275
можа нават быць дасягнута ў пастаяннай

60
00:02:07,275 --> 00:02:08,890
Час.

61
00:02:08,890 --> 00:02:11,120
Такім чынам, што ж уяўляе сабой хэш-табліцу ў любым выпадку?

62
00:02:11,120 --> 00:02:13,170
Хэш-табліца проста масіў у спалучэнні

63
00:02:13,170 --> 00:02:14,940
з функцыяй, якую мы будзем называць хэш

64
00:02:14,940 --> 00:02:15,440
функцыя.

65
00:02:16,440 --> 00:02:18,610
Хэш-функцыя прымае частка дадзеных

66
00:02:18,610 --> 00:02:20,778
у якасці ўваходных дадзеных, мы будзем называць гэта ключавы, і

67
00:02:20,778 --> 00:02:23,700
выводзіць цэлы лік, звычайна званы

68
00:02:23,700 --> 00:02:24,895
ў якасці хэш-значэння.

69
00:02:24,895 --> 00:02:28,810
Значэнне хэш-карты наш ключ да

70
00:02:28,810 --> 00:02:30,840
вызначаны індэкс ў хэш-табліцы.

71
00:02:32,080 --> 00:02:34,330
Вы б спачатку выкарыстоўваць хэш-функцыю для

72
00:02:34,330 --> 00:02:36,410
вызначыць, дзе ў хэш-табліцы, каб

73
00:02:36,410 --> 00:02:38,430
захоўваць зададзены ключ.

74
00:02:38,430 --> 00:02:41,030
Пазней, вы б выкарыстоўваць той жа хэш-функцыю

75
00:02:41,030 --> 00:02:42,950
каб вызначыць, дзе ў хэш-табліцы, каб

76
00:02:42,950 --> 00:02:45,010
пошук для дадзенага ключа.

77
00:02:45,010 --> 00:02:47,190
Па гэтай прычыне, важна, што хэш

78
00:02:47,190 --> 00:02:49,840
функцыя паводзіць сябе паслядоўна і выхады

79
00:02:49,840 --> 00:02:53,130
тое ж значэнне хэша для аднолькавых ключоў.

80
00:02:53,130 --> 00:02:54,970
Ведайце, што хэш-табліцы можа быць выкарыстаны для

81
00:02:54,970 --> 00:02:56,310
захоўваць дадзеныя ўсіх тыпаў.

82
00:02:56,310 --> 00:02:58,330
Але спрасціць рэчы, мы засяродзімся на

83
00:02:58,330 --> 00:02:59,830
Струны для цяпер.

84
00:02:59,830 --> 00:03:01,630
Вось просты хэш-функцыя для радкоў.

85
00:03:03,570 --> 00:03:05,590
Гэта хэш-функцыя вылічае хэш

86
00:03:05,590 --> 00:03:07,410
функцыя, заснаваная на першай літары

87
00:03:07,410 --> 00:03:07,910
ключ.

88
00:03:09,090 --> 00:03:11,300
"Яблык" пачынаецца з літары "А", так што гэта

89
00:03:11,300 --> 00:03:13,200
супастаўляецца з індэксам 0 у хэш-табліцы.

90
00:03:14,270 --> 00:03:17,402
Акрамя таго, "банан" супастаўляецца з індэксам 1,

91
00:03:17,402 --> 00:03:19,829
і "кошка" супастаўляецца з індэксам 2.

92
00:03:21,750 --> 00:03:23,790
Калі сябар пытаецца, калі слова "сабака" знаходзіцца ў

93
00:03:23,790 --> 00:03:26,150
табліца, мы будзем ўваходных "сабака" ў хэш

94
00:03:26,150 --> 00:03:28,390
Функцыя, якая будзе выводзіць значэнне хэш-функцыі

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

96
00:03:29,790 --> 00:03:33,150
З "сабака" ня захоўваецца з індэксам 3, мы

97
00:03:33,150 --> 00:03:35,330
Можна з упэўненасцю сказаць, што "сабака" ня

98
00:03:35,330 --> 00:03:36,340
ў табліцы,

99
00:03:36,340 --> 00:03:38,260
хоць мы толькі праверылі адно з

100
00:03:38,260 --> 00:03:40,120
хэш 26 індэксаў табліцы.

101
00:03:42,170 --> 00:03:44,280
Час кідаць ключ ў рэчах.

102
00:03:44,280 --> 00:03:46,130
Што рабіць, калі мы хочам захаваць "мурашкі" у

103
00:03:46,130 --> 00:03:47,820
табліца, а?

104
00:03:47,820 --> 00:03:51,730
"Мурашка" хэшы для індэкса 0, гэтак жа, як "яблык" зрабіў.

105
00:03:51,730 --> 00:03:53,890
Гэта з'яўляецца прыкладам сутыкнення,

106
00:03:53,890 --> 00:03:56,419
Вынікам двух ключоў хэшавання, каб тое ж самае

107
00:03:56,419 --> 00:03:57,080
індэкс.

108
00:03:58,140 --> 00:04:00,040
Нават калі ваш хэш-табліцы больш, чым

109
00:04:00,040 --> 00:04:01,980
ўсталяваць Вашы дадзеныя, і вы выбралі добры

110
00:04:01,980 --> 00:04:03,060
хэш-функцыя,

111
00:04:03,060 --> 00:04:04,560
Вы ўсё яшчэ патрэбен план для барацьбы з

112
00:04:04,560 --> 00:04:06,420
сутыкнення, калі і калі яны ўзнікаюць.

113
00:04:07,440 --> 00:04:09,810
Давайце абмяркуем плюсы і мінусы двух

114
00:04:09,810 --> 00:04:12,360
агульныя метады для вырашэння калізій:

115
00:04:12,360 --> 00:04:15,230
лінейная зандзіравання і асобны ланцужкі.

116
00:04:15,230 --> 00:04:17,430
З лінейным зандзіраваннем, калі ключ хэшы для

117
00:04:17,430 --> 00:04:19,340
аналагічны паказчык, як раней захаваныя

118
00:04:19,340 --> 00:04:21,840
ключ, яму прысвойваецца наступны даступны

119
00:04:21,840 --> 00:04:22,862
слот ў табліцы.

120
00:04:22,862 --> 00:04:27,353
Так, "мурашка" зараз захоўваецца з індэксам 3, так як

121
00:04:27,353 --> 00:04:30,850
індэксы 0, 1, і 2 ўжо былі ў выкарыстанні.

122
00:04:32,780 --> 00:04:34,610
І калі мы спрабуем захаваць трэцяе слова, што

123
00:04:34,610 --> 00:04:36,410
пачынаецца з літары "А", ён прызначаецца

124
00:04:36,410 --> 00:04:41,263
індэксаваць 4, так як індэксы 0, 1, 2 і 3

125
00:04:41,263 --> 00:04:42,530
поўныя.

126
00:04:42,530 --> 00:04:44,300
Як вы можаце бачыць нават з гэтага простага

127
00:04:44,300 --> 00:04:46,580
Напрыклад, як толькі ўзнікае калізія, вам

128
00:04:46,580 --> 00:04:48,400
значна павялічыць шанцы таго, што

129
00:04:48,400 --> 00:04:50,370
іншы сутыкнення будуць адбывацца ў той жа самы

130
00:04:50,370 --> 00:04:51,630
плошчу.

131
00:04:51,630 --> 00:04:53,530
Гэта называецца кластарызацыі, і гэта

132
00:04:53,530 --> 00:04:56,200
Сур'ёзным недахопам да лінейным зандзіравання.

133
00:04:56,200 --> 00:04:59,240
Акрамя таго, у горшым выпадку ўстаўкі, выдалення,

134
00:04:59,240 --> 00:05:02,008
і раз падстаноўкі ўжо перададзеныя O (N),

135
00:05:02,008 --> 00:05:04,200
як на наступны свабодны слот можа мець

136
00:05:04,200 --> 00:05:06,225
патэнцыйна быў апошнім слот ў табліцы.

137
00:05:06,225 --> 00:05:09,210
Можа быць, асобныя ланцужкі прапануе больш

138
00:05:09,210 --> 00:05:10,220
прывабным рашэннем.

139
00:05:10,220 --> 00:05:13,060
У асобнай мадэлі цепочечной хэш

140
00:05:13,060 --> 00:05:14,930
табліца на самай справе масіў паказальнікаў на

141
00:05:14,930 --> 00:05:16,220
звязаныя спісы.

142
00:05:16,220 --> 00:05:18,350
Пры ўзнікненні сутыкненняў, ключ можа быць

143
00:05:18,350 --> 00:05:20,760
ўстаўляецца ў пастаянным час на чале

144
00:05:20,760 --> 00:05:22,270
адпаведная звязаны спіс.

145
00:05:23,420 --> 00:05:25,310
Што адбываецца цяпер, калі мы шукаем "яблык"

146
00:05:25,310 --> 00:05:26,900
ў хэш-табліцы?

147
00:05:26,900 --> 00:05:28,940
У горшым выпадку, мы павінны прайсці

148
00:05:28,940 --> 00:05:32,530
Ўвесь звязаны спіс, пачынаючы з індэкса 0.

149
00:05:32,530 --> 00:05:34,210
Найгоршы час пошуку для хэш

150
00:05:34,210 --> 00:05:35,890
табліца, якая выкарыстоўвае паасобнага звязвання з'яўляецца

151
00:05:35,890 --> 00:05:38,580
Таму Аб (п / к), дзе да

152
00:05:38,580 --> 00:05:39,687
памер хэш-табліцы.

153
00:05:39,687 --> 00:05:42,940
Секундочку, да-пастаянная.

154
00:05:42,940 --> 00:05:46,280
Так O (п / к) на самай справе проста Аб (п),

155
00:05:46,280 --> 00:05:47,940
які быў найгоршы час пошуку для

156
00:05:47,940 --> 00:05:49,320
звязаны спіс.

157
00:05:49,320 --> 00:05:50,770
Ці сапраўды мы прайшлі праз усе

158
00:05:50,770 --> 00:05:52,370
Бяда даведацца пра хэш-табліцы

159
00:05:52,370 --> 00:05:54,927
толькі ў канчатковым выніку туды, дзе мы пачалі?

160
00:05:54,927 --> 00:05:56,975
Гэта можа быць у выпадку з тэарэтычнай

161
00:05:56,975 --> 00:05:59,087
перспектыва, але ў рэальным свеце,

162
00:05:59,087 --> 00:06:01,199
Аб (п / к) можа быць велізарнае паляпшэнне ў параўнанні

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

164
00:06:03,257 --> 00:06:05,687
Падумайце пра гэта так: лічыць да

165
00:06:05,687 --> 00:06:08,360
10 - вы б аддалі перавагу чакаць 100 секунд

166
00:06:08,360 --> 00:06:11,076
або 100 / да?

167
00:06:11,076 --> 00:06:13,252
10 секунд ад Microsoft Word, каб скончыць

168
00:06:13,252 --> 00:06:15,608
праверка арфаграфіі дакумента.

169
00:06:15,608 --> 00:06:17,368
Як вы толькі што бачылі, вырашэння канфліктаў

170
00:06:17,368 --> 00:06:19,018
цягне за сабой адзін від лінейнага пошуку або

171
00:06:19,018 --> 00:06:20,558
іншы, што запавольвае працу

172
00:06:20,558 --> 00:06:23,280
значна.

173
00:06:23,280 --> 00:06:25,470
Такім чынам, вы хочаце, каб выбраць хэш

174
00:06:25,470 --> 00:06:27,470
функцыя, якая зводзіць да мінімуму верагоднасць

175
00:06:27,470 --> 00:06:29,170
сутыкнення, якія адбываюцца ў першую чаргу.

176
00:06:30,540 --> 00:06:32,120
Вось некаторыя ўласцівасці добрай хэш

177
00:06:32,120 --> 00:06:33,400
функцыі, мець на ўвазе.

178
00:06:34,610 --> 00:06:36,590
Добры хэш-функцыя павінна выкарыстоўваць

179
00:06:36,590 --> 00:06:38,830
ўся інфармацыя, прадстаўленая дадзенага ключа

180
00:06:38,830 --> 00:06:40,890
каб максымізаваць колькасць

181
00:06:40,890 --> 00:06:42,960
Магчымыя значэнні хэш-функцыі.

182
00:06:42,960 --> 00:06:45,540
Напрыклад, калі ў нас было два радкі, "кошка"

183
00:06:45,540 --> 00:06:47,980
і "Вусень", мы хацелі б, каб яны хэш

184
00:06:47,980 --> 00:06:50,190
у розныя месцы на стале.

185
00:06:50,190 --> 00:06:52,410
Калі хэш-функцыя толькі ўлічылі

186
00:06:52,410 --> 00:06:54,860
першы раз, два, ці нават тры літары

187
00:06:54,860 --> 00:06:57,290
з радкоў, сутыкненне адбудзецца,

188
00:06:57,290 --> 00:06:58,970
так як абодва словы пачынаюцца з той жа

189
00:06:58,970 --> 00:06:59,560
тры літары.

190
00:07:01,110 --> 00:07:03,100
Значэнні хэш варта раўнамерна

191
00:07:03,100 --> 00:07:04,790
праз хэш-табліцы.

192
00:07:04,790 --> 00:07:06,300
Гэта дазволіць скараціць даўжыню звязаны

193
00:07:06,300 --> 00:07:08,050
спісы павінны сутыкнення адбываюцца.

194
00:07:09,390 --> 00:07:11,490
Гэта таксама добры знак, калі ваш хэш-значэнне

195
00:07:11,490 --> 00:07:13,600
здольны генераваць вельмі розныя

196
00:07:13,600 --> 00:07:15,660
хэш значэння для аналагічных ключоў,

197
00:07:15,660 --> 00:07:17,250
робячы сутыкненняў значна радзей.

198
00:07:18,420 --> 00:07:21,110
Наша мэта хутчэйшага ўстаўкі, выдалення,

199
00:07:21,110 --> 00:07:22,100
і пошук.

200
00:07:22,100 --> 00:07:24,060
Хэш-функцыя гуляе важную ролю ў

201
00:07:24,060 --> 00:07:25,520
кожны з гэтых працэсаў і будзе

202
00:07:25,520 --> 00:07:26,735
называецца вельмі часта.

203
00:07:26,735 --> 00:07:29,620
Такім чынам, пераканайцеся, што ён працуе толькі вельмі

204
00:07:29,620 --> 00:07:32,160
Проста, хутка аперацый, каб мінімізаваць прабег

205
00:07:32,160 --> 00:07:33,360
Час.

206
00:07:33,360 --> 00:07:34,560
Я спадзяюся, вам спадабалася гэта рэзюмэ

207
00:07:34,560 --> 00:07:36,540
ўвядзенне на хеши.

208
00:07:36,540 --> 00:07:41,189
Мяне клічуць Ларэн, і гэта CS50.