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

2
00:00:00,500 --> 00:00:01,900
[Мусиц плаиинг]

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

4
00:00:05,710 --> 00:00:09,150
>> Даг Ллоид: До сада сте
Знам доста о низовима,

5
00:00:09,150 --> 00:00:11,610
и знате много о повезаним листама.

6
00:00:11,610 --> 00:00:13,650
И имамо разговарају о
прос анд цонс смо

7
00:00:13,650 --> 00:00:16,620
о томе разговарали повезане листе
можете добити већа и мања,

8
00:00:16,620 --> 00:00:18,630
али они заузимају више величина.

9
00:00:18,630 --> 00:00:22,359
Низови су много јасније да
користити, али они су рестриктивно у колико

10
00:00:22,359 --> 00:00:24,900
јер имамо да подесите величину
Низ на самом почетку

11
00:00:24,900 --> 00:00:26,910
и онда смо заглавили са њим.

12
00:00:26,910 --> 00:00:30,470
>> Али то је, имамо прилично
исцрпљени сви наши тема

13
00:00:30,470 --> 00:00:33,040
о повезаним листама и низова.

14
00:00:33,040 --> 00:00:34,950
Или имамо?

15
00:00:34,950 --> 00:00:37,720
Можда можемо да урадимо нешто
још креативнији.

16
00:00:37,720 --> 00:00:40,950
И та врста даје
Идеја хеш табели.

17
00:00:40,950 --> 00:00:46,680
>> Дакле, у хасх табели ћемо покушати
комбинују низ са повезане листе.

18
00:00:46,680 --> 00:00:49,520
Идемо да се предности
од низа, као и случајним приступом,

19
00:00:49,520 --> 00:00:53,510
бити у стању да само идите на низ
Елемент 4 или низ елемената 8

20
00:00:53,510 --> 00:00:55,560
без потребе да преко поновити.

21
00:00:55,560 --> 00:00:57,260
То је прилично брзо, зар не?

22
00:00:57,260 --> 00:01:00,714
>> Али ми такође желимо да имамо наше податке
структура моћи да расту и смањују.

23
00:01:00,714 --> 00:01:02,630
Не треба нам, не знамо
Желим да буде ограничена.

24
00:01:02,630 --> 00:01:04,588
И ми желимо да будемо у стању
да додате и уклоните ствари

25
00:01:04,588 --> 00:01:08,430
врло лако, што ако се сећате,
је веома комплекс са низом.

26
00:01:08,430 --> 00:01:11,650
И можемо назвати
нова ствар хасх табела.

27
00:01:11,650 --> 00:01:15,190
>> А ако правилно спроведен,
ми смо на неки начин узимања

28
00:01:15,190 --> 00:01:18,150
предности оба података
структуре сте већ видели,

29
00:01:18,150 --> 00:01:19,880
низови и повезане листе.

30
00:01:19,880 --> 00:01:23,070
Убацивање може да почне да
нагињу тета 1.

31
00:01:23,070 --> 00:01:26,207
Тета нисмо баш разговарали,
али тета је само просек случај,

32
00:01:26,207 --> 00:01:27,540
шта се заправо дешава да се деси.

33
00:01:27,540 --> 00:01:29,680
Нећеш увек да
имају најгори могући сценарио,

34
00:01:29,680 --> 00:01:32,555
и не увек ће имати
најбољи сценарио, па шта је

35
00:01:32,555 --> 00:01:33,900
просечна сценарију?

36
00:01:33,900 --> 00:01:36,500
>> Па у просеку уметање
у хеш табели

37
00:01:36,500 --> 00:01:39,370
може да почне да се приближи сталном време.

38
00:01:39,370 --> 00:01:41,570
И брисање могу да добију
затворити у сталном време.

39
00:01:41,570 --> 00:01:44,440
И ИП адресу могу да добију
затворити у сталном време.

40
00:01:44,440 --> 00:01:48,600
Је-- немамо податак
Структура али да могу то да урадим,

41
00:01:48,600 --> 00:01:51,180
па то већ звучи
као прилично велику ствар.

42
00:01:51,180 --> 00:01:57,010
Заиста смо ублажило
недостаци сваког по себи.

43
00:01:57,010 --> 00:01:59,160
>> Да бисте добили ову представу
упграде иако, ми

44
00:01:59,160 --> 00:02:03,580
треба да се преиспита како додамо
података у структури.

45
00:02:03,580 --> 00:02:07,380
Посебно желимо да
Сама подаци да нам каже

46
00:02:07,380 --> 00:02:09,725
где је треба да иде у структури.

47
00:02:09,725 --> 00:02:12,850
А ако онда треба да видимо да ли је у
структура, ако морамо да га нађемо,

48
00:02:12,850 --> 00:02:16,610
желимо да погледамо податке
поново и бити у стању да ефикасно,

49
00:02:16,610 --> 00:02:18,910
користећи податке, насумично јој приступе.

50
00:02:18,910 --> 00:02:20,700
Само гледајући
подаци које треба да има

51
00:02:20,700 --> 00:02:25,890
идеја где се тачно смо
ће га наћи у хасх табеле.

52
00:02:25,890 --> 00:02:28,770
>> Сада је мана хашх
табела је да су стварно

53
00:02:28,770 --> 00:02:31,770
прилично лоше, при наручивању, или сортирање података.

54
00:02:31,770 --> 00:02:34,970
У ствари, ако почнете
да их користе да нареди или врста

55
00:02:34,970 --> 00:02:37,990
Подаци губите све од
Предности које сте претходно

56
00:02:37,990 --> 00:02:40,710
имала у смислу уметање и брисања.

57
00:02:40,710 --> 00:02:44,060
Време постаје ближи
тета од н, и имамо основи

58
00:02:44,060 --> 00:02:45,530
назадовала у повезане листе.

59
00:02:45,530 --> 00:02:48,850
И тако смо само желите да користите хасх
столови, ако не стало

60
00:02:48,850 --> 00:02:51,490
да ли се подаци поредани.

61
00:02:51,490 --> 00:02:54,290
За контекста у којем
ћете их користити у ЦС50

62
00:02:54,290 --> 00:02:58,900
вероватно не занима
да се подаци сортирана.

63
00:02:58,900 --> 00:03:03,170
>> Тако хасх табела представља комбинацију
два различита комада

64
00:03:03,170 --> 00:03:04,980
са којима смо упознати.

65
00:03:04,980 --> 00:03:07,930
Први је функција, која
што се обично назива хасх функцију.

66
00:03:07,930 --> 00:03:11,760
И то хасх функција ће се
вратити неке не-негативан цео број, који

67
00:03:11,760 --> 00:03:14,870
обично зовемо хасхЦоде, у реду?

68
00:03:14,870 --> 00:03:20,230
Други део је низ, који је
способан за складиштење података типа ве

69
00:03:20,230 --> 00:03:22,190
Желим да поставите у структуру података.

70
00:03:22,190 --> 00:03:24,310
Ми ћемо задржати на
повезан елемент листе за сада

71
00:03:24,310 --> 00:03:27,810
и само почети са основама
хасх табелу да спусти главу око тога,

72
00:03:27,810 --> 00:03:30,210
и онда можда ћеш потрошити
ваш ум мало када смо

73
00:03:30,210 --> 00:03:32,920
комбинују низовима и линк листе заједно.

74
00:03:32,920 --> 00:03:35,590
>> Основна идеја иако
је да узмемо неке податке.

75
00:03:35,590 --> 00:03:37,860
Ми смо покренули те податке кроз
хасх функција.

76
00:03:37,860 --> 00:03:41,980
Тако подаци се обрађују
и избацује број, у реду?

77
00:03:41,980 --> 00:03:44,890
И онда са тим бројем
ми само складишти податке

78
00:03:44,890 --> 00:03:48,930
желимо да сачувате у
Арраи на тој локацији.

79
00:03:48,930 --> 00:03:53,990
Тако, на пример да можда имамо
ово хасх табела низова.

80
00:03:53,990 --> 00:03:57,350
Има 10 елемената у њој, тако
можемо уклопити 10 конце у њој.

81
00:03:57,350 --> 00:03:59,320
>> Рецимо желимо да хасх Јохн.

82
00:03:59,320 --> 00:04:02,979
Дакле, Јована као података желимо да убаците
у овом хасх табели негде.

83
00:04:02,979 --> 00:04:03,770
Где смо га ставили?

84
00:04:03,770 --> 00:04:05,728
Па обично са неким
Арраи до сада смо вероватно

85
00:04:05,728 --> 00:04:07,610
би га ставите у арраи локацији 0.

86
00:04:07,610 --> 00:04:09,960
Али сада имамо ову нову функцију хасх.

87
00:04:09,960 --> 00:04:13,180
>> И рецимо да трчимо Јохн
кроз овај хеш функције

88
00:04:13,180 --> 00:04:15,417
и то избацује 4.

89
00:04:15,417 --> 00:04:17,500
Па то је где смо
хтети да стави Јохн.

90
00:04:17,500 --> 00:04:22,050
Желимо да стави Јована у арраи локацији
4, јер ако хасх Јохн Поново:

91
00:04:22,050 --> 00:04:23,810
хајде да касније да смо
желите да претражите и види

92
00:04:23,810 --> 00:04:26,960
ако Џон постоји у овом хасх
табле-- све што треба да урадите

93
00:04:26,960 --> 00:04:30,310
Да ли је пролазе кроз исти хасх
функција, добити број 4 из,

94
00:04:30,310 --> 00:04:33,929
и бити у стању да нађем Џона
одмах у нашој структури података.

95
00:04:33,929 --> 00:04:34,720
То је прилично добро.

96
00:04:34,720 --> 00:04:36,928
>> Рецимо сад да радимо ово
опет, желимо да хасх Павла.

97
00:04:36,928 --> 00:04:39,446
Желимо да додате Паул
у овом хасх табели.

98
00:04:39,446 --> 00:04:42,070
Рецимо да смо овај пут води
Павле кроз хеш функције,

99
00:04:42,070 --> 00:04:44,600
хасхЦоде који се генерише је 6.

100
00:04:44,600 --> 00:04:47,340
Па сада можемо ставити Паул
у низу локацији 6.

101
00:04:47,340 --> 00:04:50,040
А ако треба да се угледају ли
Павле је у овом хасх табели,

102
00:04:50,040 --> 00:04:53,900
све што треба да урадите је да покренете Пол
опет кроз хеш функције

103
00:04:53,900 --> 00:04:55,830
а ми ћемо добити 6 опет.

104
00:04:55,830 --> 00:04:57,590
>> И онда да погледамо
на локацији низа 6.

105
00:04:57,590 --> 00:04:58,910
Паул тамо?

106
00:04:58,910 --> 00:05:00,160
Ако је тако, он је у хасх табели.

107
00:05:00,160 --> 00:05:01,875
Да ли је Павле не?

108
00:05:01,875 --> 00:05:03,000
Он није у хасх табели.

109
00:05:03,000 --> 00:05:05,720
То је прилично једноставан.

110
00:05:05,720 --> 00:05:07,770
>> Сада како се дефинише хасх функцију?

111
00:05:07,770 --> 00:05:11,460
Па заиста нема граница до
Број могућих хеш функцијама.

112
00:05:11,460 --> 00:05:14,350
У ствари, постоји велики број заиста,
стварно добри на Интернету.

113
00:05:14,350 --> 00:05:17,560
Постоји велики број заиста,
стварно лоши на Интернету.

114
00:05:17,560 --> 00:05:21,080
Такође је прилично лако
да напишем једну лошу.

115
00:05:21,080 --> 00:05:23,760
>> Шта чини А Гоод
хасх функција, зар не?

116
00:05:23,760 --> 00:05:27,280
Па добро хасх функција треба
користити само су подаци који се хеширану,

117
00:05:27,280 --> 00:05:29,420
и све податке који се хеширану.

118
00:05:29,420 --> 00:05:32,500
Тако да не желите да користите све--
не уграде ништа

119
00:05:32,500 --> 00:05:35,560
друго осим подацима.

120
00:05:35,560 --> 00:05:37,080
И желимо да користимо све податке.

121
00:05:37,080 --> 00:05:39,830
Ми не желимо само да користи комад
од тога, желимо да користимо све то.

122
00:05:39,830 --> 00:05:41,710
Хеш функција треба да
такође бити детерминистичка.

123
00:05:41,710 --> 00:05:42,550
Шта то значи?

124
00:05:42,550 --> 00:05:46,200
Па то значи да сваки пут ми
проћи потпуно исти податак

125
00:05:46,200 --> 00:05:50,040
у хасх функцију увек
добити исту хасхЦоде напоље.

126
00:05:50,040 --> 00:05:52,870
Ако прође Јохн Инто тхе
хасх функција изађем 4.

127
00:05:52,870 --> 00:05:56,110
Требало би да могу то да урадим 10.000
пута, а ја ћу увек добити 4.

128
00:05:56,110 --> 00:06:00,810
Значи нема случајних бројева ефикасно
могу бити укључени у нашој хасх таблес--

129
00:06:00,810 --> 00:06:02,750
у нашим хеш функције.

130
00:06:02,750 --> 00:06:05,750
>> Хеш функција треба да се
равномерно расподелити податке.

131
00:06:05,750 --> 00:06:09,700
Ако сваки пут када покренете податке кроз
хасх функција добијете хасхЦоде 0,

132
00:06:09,700 --> 00:06:11,200
то је вероватно није толико велика, зар не?

133
00:06:11,200 --> 00:06:14,600
Вероватно Желиш да велики
распон хеш кодова.

134
00:06:14,600 --> 00:06:17,190
Такође, ствари се могу ширити
у цијелој табели.

135
00:06:17,190 --> 00:06:23,210
Такође било би сјајно ако стварно
слични подаци, као што су Јован и Јонатхан,

136
00:06:23,210 --> 00:06:26,320
Можда су раширили да одмери
различите локације у хасх табеле.

137
00:06:26,320 --> 00:06:28,750
То би било лепо предност.

138
00:06:28,750 --> 00:06:31,250
>> Ево примера хеш функције.

139
00:06:31,250 --> 00:06:33,150
Ја сам написао ово горе раније.

140
00:06:33,150 --> 00:06:35,047
То није посебно
добра хасх функција

141
00:06:35,047 --> 00:06:37,380
због разлога који немају баш
беар иде у сада.

142
00:06:37,380 --> 00:06:41,040
Али видиш шта се овде дешава?

143
00:06:41,040 --> 00:06:44,420
Чини се као да прогласи променљиву
зове сума и постављање га једнако 0.

144
00:06:44,420 --> 00:06:50,010
А онда очигледно радим нешто
све док стрстр [ј] није једнако

145
00:06:50,010 --> 00:06:52,490
да Бацксласх 0.

146
00:06:52,490 --> 00:06:54,870
Шта ја тамо?

147
00:06:54,870 --> 00:06:57,440
>> Ово је у суштини само једна
начин спровођења [? СТРЛ?]

148
00:06:57,440 --> 00:06:59,773
и откривање када сте
стигли до краја стринга.

149
00:06:59,773 --> 00:07:02,480
Дакле, не морам да стварно
израчунати дужину стринга,

150
00:07:02,480 --> 00:07:05,640
Ја само користим када сам ударио
обрнута коса црта 0 карактер Знам

151
00:07:05,640 --> 00:07:07,185
Ја сам стигао до краја стринга.

152
00:07:07,185 --> 00:07:09,560
И онда ћу задржати
итератинг кроз тај низ,

153
00:07:09,560 --> 00:07:15,310
додајући стрстр [Ј] да сумирамо, а затим у
крај дана ће се вратити сум мод

154
00:07:15,310 --> 00:07:16,200
ХАСХ_МАКС.

155
00:07:16,200 --> 00:07:18,700
>> У основи свега овога хасх
Функција ради се саберу

156
00:07:18,700 --> 00:07:23,450
све АСЦИИ вредности
мој стринг и онда је

157
00:07:23,450 --> 00:07:26,390
враћа неке хасхЦоде
моддед од ХАСХ_МАКС.

158
00:07:26,390 --> 00:07:29,790
Вероватно је величине
моје низа, зар не?

159
00:07:29,790 --> 00:07:33,160
Не желим да се добро хасх
кодови ако је мој низ је величине 10,

160
00:07:33,160 --> 00:07:35,712
Ја не желим да будем добијање
од хасх кодови 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, ја не могу да ствари у
те локације низа,

162
00:07:38,690 --> 00:07:39,790
то би било незаконито.

163
00:07:39,790 --> 00:07:42,130
Ја бих претрпети сегментације грешку.

164
00:07:42,130 --> 00:07:45,230
>> Сада овде је још један брз страну.

165
00:07:45,230 --> 00:07:48,470
Генерално се вероватно неће
Желим да напишем своје хеш функција.

166
00:07:48,470 --> 00:07:50,997
То је заправо мало
уметност, а не наука.

167
00:07:50,997 --> 00:07:52,580
И има доста који иде у њих.

168
00:07:52,580 --> 00:07:55,288
Интернет, као што сам рекао, је пуна
стварно добрих хеш функције,

169
00:07:55,288 --> 00:07:58,470
и требало би да користе интернет у
финд хеш функција, јер је стварно

170
00:07:58,470 --> 00:08:03,230
некако непотребна
губљење времена да створи свој.

171
00:08:03,230 --> 00:08:05,490
>> Можете писати једноставне оне
за потребе тестирања.

172
00:08:05,490 --> 00:08:08,323
Али када ствари иду у
старт хасхинг податке и складиштења

173
00:08:08,323 --> 00:08:10,780
у хасх табелу си
Вероватно це хтети

174
00:08:10,780 --> 00:08:14,580
да користите неку функцију која је генерисана
за вас, која постоји на интернету.

175
00:08:14,580 --> 00:08:17,240
Ако само буди сигуран
да наведе своје изворе.

176
00:08:17,240 --> 00:08:21,740
Нема разлога да
плагирају ништа овде.

177
00:08:21,740 --> 00:08:25,370
>> Рачунар наука заједница је
дефинитивно расте, и заиста вредности

178
00:08:25,370 --> 00:08:28,796
опен соурце и то је заиста важно
да наведе своје изворе, тако да људи

179
00:08:28,796 --> 00:08:30,670
можете добити приписивање за
рад да су они

180
00:08:30,670 --> 00:08:32,312
раде за добробит заједнице.

181
00:08:32,312 --> 00:08:34,020
Дакле, увек бити суре--
и не само за хасх

182
00:08:34,020 --> 00:08:37,270
функције, али углавном када вас
користити код са спољашњег извора,

183
00:08:37,270 --> 00:08:38,299
Увек ците свој извор.

184
00:08:38,299 --> 00:08:43,500
Дајте кредит особу која је урадила
неке од рада, тако да не морате да.

185
00:08:43,500 --> 00:08:46,720
>> ОК, хајде поново ово
хасх табела за секунду.

186
00:08:46,720 --> 00:08:48,780
Ово је место где смо оставили
искључује након што уметнута

187
00:08:48,780 --> 00:08:53,300
Џон и Пол у овом хасх табели.

188
00:08:53,300 --> 00:08:55,180
Да ли видите проблем?

189
00:08:55,180 --> 00:08:58,410
Можда ћете видети два.

190
00:08:58,410 --> 00:09:02,240
Али конкретно, зар не
погледајте овај могући проблем?

191
00:09:02,240 --> 00:09:06,770
>> Шта ако хасх Ринго, и то
Испада да је након обраде

192
00:09:06,770 --> 00:09:14,000
да су подаци кроз хеш функције
Ринго такође генерише на хасхЦоде 6.

193
00:09:14,000 --> 00:09:16,810
Већ имам податке на
хасхцоде-- низ локација 6.

194
00:09:16,810 --> 00:09:22,000
Тако да је вероватно ће бити мало
проблем за мене сада, зар не?

195
00:09:22,000 --> 00:09:23,060
>> Ми то називамо судар.

196
00:09:23,060 --> 00:09:26,460
И судара се јавља када два
комада података пролазе кроз исти хасх

197
00:09:26,460 --> 00:09:29,200
Функција давати исти хасхЦоде.

198
00:09:29,200 --> 00:09:32,850
Претпоставља се и даље желимо да обоје
комада података у хасх табеле,

199
00:09:32,850 --> 00:09:36,330
иначе не бисмо се ради Ринго
произвољно кроз хеш функције.

200
00:09:36,330 --> 00:09:40,870
Ми вероватно желе да се
Ринго у тај низ.

201
00:09:40,870 --> 00:09:46,070
>> Како ми то радимо, иако, ако је
и Паул и принос хасхЦоде 6?

202
00:09:46,070 --> 00:09:49,520
Ми не желимо да замените Павла,
желимо да Павле бити тамо.

203
00:09:49,520 --> 00:09:52,790
Зато морамо да нађемо начин да се
елемената у хеш табели која

204
00:09:52,790 --> 00:09:56,550
и даље чува Наши брзи
убацивање и брз поглед горе.

205
00:09:56,550 --> 00:10:01,350
А један од начина да се носи са тим је
уради нешто што се зове линеарни прескок.

206
00:10:01,350 --> 00:10:04,170
>> Користећи овај метод ако имамо
судар, па, шта да радимо?

207
00:10:04,170 --> 00:10:08,580
Па не можемо да га ставимо у арраи локацији
6, или било хасхЦоде је генерисана,

208
00:10:08,580 --> 00:10:10,820
хајде да га стави на хасхЦоде плус 1.

209
00:10:10,820 --> 00:10:13,670
И ако је то пуна Хајде да
стави га у хасхЦоде плус 2.

210
00:10:13,670 --> 00:10:17,420
Предност овог бића ако је
није тачно где ми мислимо да јесте,

211
00:10:17,420 --> 00:10:20,850
и морамо да бисте започели претрагу,
Можда не морамо да идемо предалеко.

212
00:10:20,850 --> 00:10:23,900
Можда не морамо тражити
све н елементи хасх табеле.

213
00:10:23,900 --> 00:10:25,790
Можда морамо тражити
пар њих.

214
00:10:25,790 --> 00:10:30,680
>> И тако смо увек тежи ка
да је просјечна случај био близу 1 ВС

215
00:10:30,680 --> 00:10:34,280
близу н, па можда да ће радити.

216
00:10:34,280 --> 00:10:38,010
Дакле, хајде да видимо како ово
можда неће радити у стварности.

217
00:10:38,010 --> 00:10:41,460
И да видимо да ли можда можемо открити
проблем који може доћи овде.

218
00:10:41,460 --> 00:10:42,540
>> Рецимо да хасх Барта.

219
00:10:42,540 --> 00:10:45,581
Дакле, сада ћемо покренути нови сет
жица кроз хеш функције,

220
00:10:45,581 --> 00:10:48,460
и трчимо Барт кроз хасх
функција, добијамо хасхЦоде 6.

221
00:10:48,460 --> 00:10:52,100
Ми погледамо, видимо 6 је
празан, тако да можемо ставити Барт тамо.

222
00:10:52,100 --> 00:10:55,410
>> Сада хасх Лизу и да
Такође генерише хасхЦоде 6.

223
00:10:55,410 --> 00:10:58,330
Па сад кад смо користећи овај
линеарни прескок начин почињемо у 6,

224
00:10:58,330 --> 00:10:59,330
видимо да 6 је пуна.

225
00:10:59,330 --> 00:11:00,990
Не можемо ставити Лиса у 6.

226
00:11:00,990 --> 00:11:02,090
Па где идемо?

227
00:11:02,090 --> 00:11:03,280
Идемо до 7.

228
00:11:03,280 --> 00:11:04,610
7 је празна, тако да ради.

229
00:11:04,610 --> 00:11:06,510
Дакле, хајде да ставимо Лиса тамо.

230
00:11:06,510 --> 00:11:10,200
>> Сада хасх Хомер и добијамо 7.

231
00:11:10,200 --> 00:11:13,380
У реду добро знамо да је пун 7
сада, тако да не могу да Хомер тамо.

232
00:11:13,380 --> 00:11:14,850
Дакле, идемо до 8.

233
00:11:14,850 --> 00:11:15,664
Да ли је 8 доступан?

234
00:11:15,664 --> 00:11:18,330
Да, и 8 блиски до 7, па ако
морамо да почнемо потрази смо

235
00:11:18,330 --> 00:11:20,020
неће морати да иде предалеко.

236
00:11:20,020 --> 00:11:22,860
И тако ставимо Хомера у 8.

237
00:11:22,860 --> 00:11:25,151
>> Сада хасх Меги и
враћа 3, хвала богу

238
00:11:25,151 --> 00:11:26,650
ми смо у стању да само стави Маггие тамо.

239
00:11:26,650 --> 00:11:29,070
Ми не треба да урадите било
врста сондирање за то.

240
00:11:29,070 --> 00:11:32,000
Сада хасх Марџ, и
Марџ такође враћа 6.

241
00:11:32,000 --> 00:11:39,560
>> Па 6 је пуна, 7 је пуна, 8 је пун,
9, у реду хвала Богу, 9 је празна.

242
00:11:39,560 --> 00:11:41,600
Ја могу ставити Марге на 9.

243
00:11:41,600 --> 00:11:45,280
Већ можемо видети да смо почели
да се овај проблем где сада смо

244
00:11:45,280 --> 00:11:48,780
почевши да се протегне ствари некако
од далеко од својих хасх кодова.

245
00:11:48,780 --> 00:11:52,960
И то тета 1, тај просек
случај буде константна времена,

246
00:11:52,960 --> 00:11:56,560
почиње да се мало море--
Почињем да мало теже

247
00:11:56,560 --> 00:11:58,050
ка тхета н.

248
00:11:58,050 --> 00:12:01,270
Ми смо почели да губе да
Предност хеш табеле.

249
00:12:01,270 --> 00:12:03,902
>> Овај проблем који смо управо видели
је нешто што се зове груписање.

250
00:12:03,902 --> 00:12:06,360
И оно што је заиста лоше о
груписање је да када тебе

251
00:12:06,360 --> 00:12:09,606
има два елемента који су раме уз
стране то чини још вероватније,

252
00:12:09,606 --> 00:12:11,480
ви имате двоструко
шанса да идеш

253
00:12:11,480 --> 00:12:13,516
да још један судар
са тим кластер,

254
00:12:13,516 --> 00:12:14,890
и кластер ће порасти за један.

255
00:12:14,890 --> 00:12:19,640
А ти ћеш стално расте и расте
ваш вероватноћа да судар.

256
00:12:19,640 --> 00:12:24,470
И на крају то је само тако лоше
како не сортирање података уопште.

257
00:12:24,470 --> 00:12:27,590
>> Други проблем је што, иако
даље, па сада до ове тачке,

258
00:12:27,590 --> 00:12:30,336
смо управо били некако
разумевање шта хасх сто је,

259
00:12:30,336 --> 00:12:31,960
и даље само простор за 10 низова.

260
00:12:31,960 --> 00:12:37,030
Ако желимо да наставимо да хасх
грађани Спрингфиелд,

261
00:12:37,030 --> 00:12:38,790
можемо само да њих 10 унутра.

262
00:12:38,790 --> 00:12:42,619
И ако покушамо и додај 11. или 12.,
немамо где да их стави.

263
00:12:42,619 --> 00:12:45,660
Могли би да се врти око у
кругови покушавају да пронађу празан место,

264
00:12:45,660 --> 00:12:49,000
а ми можда запети
у бескрајној петљи.

265
00:12:49,000 --> 00:12:51,810
>> Дакле, ова врста погодна за идеје
нечега што се зове цхаининг.

266
00:12:51,810 --> 00:12:55,790
И ово је место где ћемо довести
повезаних листа назад у слику.

267
00:12:55,790 --> 00:13:01,300
Шта ако уместо чувања само
сама података у низу,

268
00:13:01,300 --> 00:13:04,471
сваки елемент низа могао
држите више комада података?

269
00:13:04,471 --> 00:13:05,970
Па то нема смисла, зар не?

270
00:13:05,970 --> 00:13:09,280
Ми знамо да само низ цан
холд-- сваки елемент низа

271
00:13:09,280 --> 00:13:12,930
могу само једну комад
података те врсте података.

272
00:13:12,930 --> 00:13:16,750
>> Али шта ако је тип података
је повезана листа, зар не?

273
00:13:16,750 --> 00:13:19,830
Па шта ако сваки
елемент низа био је

274
00:13:19,830 --> 00:13:22,790
показивач на челу повезане листе?

275
00:13:22,790 --> 00:13:24,680
И онда бисмо могли изградити
оне повезане листе

276
00:13:24,680 --> 00:13:27,120
и расте их произвољно,
јер повезане листе дозвољавају

277
00:13:27,120 --> 00:13:32,090
да расте и смањују много више
флексибилно него низ ради.

278
00:13:32,090 --> 00:13:34,210
Па шта ако сада користимо,
ми искористити, зар не?

279
00:13:34,210 --> 00:13:37,760
Почињемо да расту ове ланце
из ових арраи локација.

280
00:13:37,760 --> 00:13:40,740
>> Сада можемо да стане неограничен
количина података, или не бесконачна,

281
00:13:40,740 --> 00:13:44,170
произвољна количина
података, у нашем хасх табеле

282
00:13:44,170 --> 00:13:47,760
без икаквог налетим
проблем судара.

283
00:13:47,760 --> 00:13:50,740
Такође смо елиминисани
груписање радећи ово.

284
00:13:50,740 --> 00:13:54,380
И добро знамо да када смо убацили
у повезане листе, ако се сећате

285
00:13:54,380 --> 00:13:57,779
из наше видео на повезаних листи, појединачно
повезане листе и двоструко повезане листе,

286
00:13:57,779 --> 00:13:59,070
То је операција константа време.

287
00:13:59,070 --> 00:14:00,710
Ми само додавање на фронт.

288
00:14:00,710 --> 00:14:04,400
>> А за Погледам горе, па знамо
да погледате у повезане листе

289
00:14:04,400 --> 00:14:05,785
може бити проблем, зар не?

290
00:14:05,785 --> 00:14:07,910
Морамо да претражујете
је од почетка до краја.

291
00:14:07,910 --> 00:14:10,460
Нема случајно
приступ у повезане листе.

292
00:14:10,460 --> 00:14:15,610
Али, ако уместо једног повезан
Листа гдје би ИП адресу бити О Н,

293
00:14:15,610 --> 00:14:19,590
сада имамо 10 повезане листе,
или 1.000 повезане листе,

294
00:14:19,590 --> 00:14:24,120
сада је о од н подељено са 10,
или О од н подељено 1.000.

295
00:14:24,120 --> 00:14:26,940
>> И док смо причали
теоретски о сложености

296
00:14:26,940 --> 00:14:30,061
занемаримо константе, у реалном
свет те ствари заиста важно,

297
00:14:30,061 --> 00:14:30,560
jel tako?

298
00:14:30,560 --> 00:14:33,080
Ми ћемо заправо приметити
да се то деси

299
00:14:33,080 --> 00:14:36,610
да ради 10 пута брже,
или 1.000 пута брже,

300
00:14:36,610 --> 00:14:41,570
јер смо дистрибуирање један дуг
ланац преко 1.000 мањих ланаца.

301
00:14:41,570 --> 00:14:45,090
И тако сваки пут морамо тражити
кроз један од тих ланаца можемо

302
00:14:45,090 --> 00:14:50,290
игноришу 999 ланце не брину
о, и само тражи тај.

303
00:14:50,290 --> 00:14:53,220
>> Који је у просеку
бе 1.000 пута краће.

304
00:14:53,220 --> 00:14:56,460
И тако ми смо и даље некако
тежи ка том случају просечне

305
00:14:56,460 --> 00:15:01,610
да буде константан времена, али
само зато што су усклађивање

306
00:15:01,610 --> 00:15:03,730
дељењем неком огромном сталним фактором.

307
00:15:03,730 --> 00:15:05,804
Хајде да видимо како би ово могло
заправо изгледају иако.

308
00:15:05,804 --> 00:15:08,720
Дакле, ово је тараба сто смо имали
пре него што смо прогласили хасх табелу која

309
00:15:08,720 --> 00:15:10,270
био способан за складиштење 10 конце.

310
00:15:10,270 --> 00:15:11,728
Нећемо више да урадим.

311
00:15:11,728 --> 00:15:13,880
Ми већ знамо да
ограничења тог метода.

312
00:15:13,880 --> 00:15:20,170
Сада наша хасх табела ће бити
низ од 10 чворова, показивачи

313
00:15:20,170 --> 00:15:22,120
шефовима повезаних листи.

314
00:15:22,120 --> 00:15:23,830
>> И сада је нула.

315
00:15:23,830 --> 00:15:26,170
Сваки од тих 10 показивача нулл.

316
00:15:26,170 --> 00:15:29,870
Нема ништа у нашој
хасх сто сада.

317
00:15:29,870 --> 00:15:32,690
>> Сада почнимо да се неке
ствари у ову хасх табеле.

318
00:15:32,690 --> 00:15:35,440
И хајде да видимо како ова метода је
да нам користи мало.

319
00:15:35,440 --> 00:15:36,760
Идемо сада хасх Јоеи.

320
00:15:36,760 --> 00:15:40,210
Ми ћемо се покренути низ Јоеи кроз
хасх функција и враћамо 6.

321
00:15:40,210 --> 00:15:41,200
Па шта сада да радимо?

322
00:15:41,200 --> 00:15:44,090
>> Па сада раде са повезаним листама,
не радимо са низовима.

323
00:15:44,090 --> 00:15:45,881
И када радимо
са повезаним листама ми

324
00:15:45,881 --> 00:15:49,790
знам да треба да почне динамички
додељивање простора и изградњу ланаца.

325
00:15:49,790 --> 00:15:54,020
То је врста Како-- оне су срж
елементи изградње повезану листу.

326
00:15:54,020 --> 00:15:57,670
Тако је нека динамички
доделити простор за Јоеи,

327
00:15:57,670 --> 00:16:00,390
а онда да га додате у ланцу.

328
00:16:00,390 --> 00:16:03,170
>> Дакле, сада погледајте шта смо урадили.

329
00:16:03,170 --> 00:16:06,440
Када смо хасх Јоеи имамо хасхЦоде 6.

330
00:16:06,440 --> 00:16:11,790
Сада је показивач на арраи локацији 6
указује на челу повезане листе,

331
00:16:11,790 --> 00:16:14,900
а сада је то једини
елемент повезане листе.

332
00:16:14,900 --> 00:16:18,350
И чвор у томе
линкед лист је Џои.

333
00:16:18,350 --> 00:16:22,300
>> Дакле, ако треба да се угледају Јоеи
касније, управо смо хасх Јоеи опет,

334
00:16:22,300 --> 00:16:26,300
добијамо 6 поново јер наша
хасх функција је детерминистички.

335
00:16:26,300 --> 00:16:30,400
А онда смо се крећу од главе
од повезане листе указао

336
00:16:30,400 --> 00:16:33,360
да од низа локација
6, и можемо поновити

337
00:16:33,360 --> 00:16:35,650
преко које покушавају да пронађу Јоеи.

338
00:16:35,650 --> 00:16:37,780
А ако градимо наше
хасх табле ефикасно,

339
00:16:37,780 --> 00:16:41,790
а наш хасх функција ефикасно
добро дистрибуира податке,

340
00:16:41,790 --> 00:16:45,770
у просеку свакој од ових повезани
Листе на сваком месту арраи

341
00:16:45,770 --> 00:16:50,110
ће бити 1/10 величине ако се
Управо је имао као један велики

342
00:16:50,110 --> 00:16:51,650
линкед лист са свиме у њему.

343
00:16:51,650 --> 00:16:55,670
>> Ако ми дистрибуирамо да огромна повезан
Листа преко 10 повезаних листи

344
00:16:55,670 --> 00:16:57,760
Свака листа ће бити 1/10 величина.

345
00:16:57,760 --> 00:17:01,432
И тако 10 пута брже
за претраживање преко.

346
00:17:01,432 --> 00:17:02,390
Дакле, хајде да поновимо.

347
00:17:02,390 --> 00:17:04,290
Идемо сада хасх Росс.

348
00:17:04,290 --> 00:17:07,540
>> И рецимо Росс, када смо то
хасх код вратимо је 2.

349
00:17:07,540 --> 00:17:10,630
Па сада имамо динамички додели
нови чвор, ставимо Росс у том чвору,

350
00:17:10,630 --> 00:17:14,900
и сада рећи низ локација
2, уместо указујући на нулл,

351
00:17:14,900 --> 00:17:18,579
указује на челу повезан
Листа чија је једина чвор је Рос.

352
00:17:18,579 --> 00:17:22,660
И можемо да урадимо ово још једном, ми
може хасх Рејчел и да хасхЦоде 4.

353
00:17:22,660 --> 00:17:25,490
Маллоц нови чвор, пут Рацхел у
чвор и изговорите арраи локације

354
00:17:25,490 --> 00:17:27,839
4 сада указује на главу
од повезане листе чији

355
00:17:27,839 --> 00:17:31,420
Једини елемент дешава да се Рејчел.

356
00:17:31,420 --> 00:17:33,470
>> У реду, али шта се дешава ако
имамо судар?

357
00:17:33,470 --> 00:17:38,560
Хајде да видимо како можемо носити сударе
користећи посебан метод цхаининг.

358
00:17:38,560 --> 00:17:39,800
Идемо хасх Фиби.

359
00:17:39,800 --> 00:17:41,094
Схватили смо хасхЦоде 6.

360
00:17:41,094 --> 00:17:44,010
У нашем претходном примеру смо били
складиштење конце у низу.

361
00:17:44,010 --> 00:17:45,980
То је био проблем.

362
00:17:45,980 --> 00:17:48,444
>> Ми не желимо да разбије
Џои, и већ смо

363
00:17:48,444 --> 00:17:51,110
види да можемо добити неки груписање
Проблеми Ако покушамо и корак

364
00:17:51,110 --> 00:17:52,202
кроз и сонда.

365
00:17:52,202 --> 00:17:54,660
Али, шта ако смо некако
третирати ово на исти начин, зар не?

366
00:17:54,660 --> 00:17:57,440
То је као додавање елемент
на челу повезане листе.

367
00:17:57,440 --> 00:18:00,220
Хајде само маллоц простор за Фиби.

368
00:18:00,220 --> 00:18:04,764
>> Ми ћемо рећи Фиби је следећи показивача бодова
старом главе повезане листе,

369
00:18:04,764 --> 00:18:07,180
и онда само 6 поена до
нови шеф повезане листе.

370
00:18:07,180 --> 00:18:10,150
И сад погледај, променили смо Фиби у.

371
00:18:10,150 --> 00:18:14,210
Сада можете сачувати два
елементи са хасхЦоде 6,

372
00:18:14,210 --> 00:18:17,170
и немамо никаквих проблема.

373
00:18:17,170 --> 00:18:20,147
>> То је отприлике све
ту је уланчавања.

374
00:18:20,147 --> 00:18:21,980
И Уланчавање је дефинитивно
метод који је

375
00:18:21,980 --> 00:18:27,390
ће бити најефикаснији за вас ако
сте чувања података у хасх табели.

376
00:18:27,390 --> 00:18:30,890
Али ово комбинација
низови и повезане листе

377
00:18:30,890 --> 00:18:36,080
заједно формирају хеш табели јако
драматично побољшава ваше способности

378
00:18:36,080 --> 00:18:40,550
за складиштење велике количине података, и
врло брзо и ефикасно претраживање

379
00:18:40,550 --> 00:18:41,630
кроз тих података.

380
00:18:41,630 --> 00:18:44,150
>> Има још још један
структура података тамо

381
00:18:44,150 --> 00:18:48,700
да би чак бити мало
боље смислу гарантовања

382
00:18:48,700 --> 00:18:51,920
да је наш уметање, брисање и
Лоок Уп пута су још брже.

383
00:18:51,920 --> 00:18:55,630
И ми ћемо видети да у видео на покушаја.

384
00:18:55,630 --> 00:18:58,930
Ја сам Доуг Ллоид, ово је ЦС50.

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