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
>> Даг LLOYD: До сега
Знаеме многу за низи,

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
без да iterate во пречник.

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
That's-- немаме податоци
структура сепак тоа може да го направат тоа,

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
Времето станува поблиску до
тета на n, и ние сме во основа

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
За контекстот во кој
ќе ги користите во CS50

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
ние обично го нарекуваме hashCode, во ред?

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, затоа што ако ние хаш Џон again--

91
00:04:22,050 --> 00:04:23,810
да речеме подоцна ние
сакате да пребарувате и да видиме

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

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
на hashCode која е генерирана е 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
И добра хеш функција треба
користете само се hashed податоците,

117
00:05:27,280 --> 00:05:29,420
и сите на податоците кои се hashed.

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

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
во функција на хаш ние секогаш
добиете истиот hashCode надвор.

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
Па нема случајни броеви ефикасно
можат да бидат вклучени во нашата хаш tables--

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
Ако секој пат кога ќе се кандидира на податоци преку
хеш функција ќе го добиете hashCode 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
И тогаш очигледно правам нешто
па додека strstr [j] не е еднаква

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
>> Ова е во основа само уште еден
начин на спроведување [? strl?]

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
додавајќи strstr [j] да ги сумира, а потоа на
крајот на денот ќе се врати сума МО

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

155
00:07:16,200 --> 00:07:18,700
>> Во суштина сето ова хаш
функција го прави е да се збира

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

157
00:07:23,450 --> 00:07:26,390
враќаат некои hashCode
modded страна HASH_MAX.

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
Но кога ќе всушност се случува да се
почне hashing податоци и складирање

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
Затоа секогаш бидете sure--
и не само за хаш

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
>> OK, па ајде да го ревидира овој
хаш табелата за една секунда.

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
тие податоци преку функцијата на хаш
Ринго исто така генерирана за hashCode 6.

193
00:09:14,000 --> 00:09:16,810
Јас веќе имам на податоци во
hashcode-- локација низа 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
функција се добие принос од истиот hashCode.

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
>> Како ние да го направи тоа, иако, ако тој
и Павле и принос hashCode 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, или што и hashCode е генерирана,

208
00:10:08,580 --> 00:10:10,820
ајде да го доведе во hashCode плус 1.

209
00:10:10,820 --> 00:10:13,670
И ако тоа е целосна ајде
го стави во hashCode плус 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
Можеби и ние не треба да го бара
сите n елементи од хаш табелата.

213
00:10:23,900 --> 00:10:25,790
Можеби и ние треба да го бара
неколку од нив.

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

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

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
и трчаме Барт преку хаш
функција, да добиеме hashCode 6.

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

222
00:10:52,100 --> 00:10:55,410
>> Сега ние хаш Лиза и дека
исто така, генерира hashCode 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
почнува да се добие малку more--
почнуваат да имаат тенденција малку повеќе

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

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
Ние знаеме дека низа може само
hold-- секој елемент од низата

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
Но, ако наместо да се има еден поврзан
листа, каде што еден пребарување ќе биде O на n,

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

294
00:14:19,590 --> 00:14:24,120
сега тоа е О од n поделено со 10,
или O од n поделено со 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
нели?

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
Тоа е вид на how-- тие се јадрото
елементи на градење на поврзани листа.

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
Кога ние хаш Џои добивме hashCode 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, а ние може да iterate

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
И можеме да го направиме ова уште еднаш, ние
може хаш Рејчел и да добијат hashCode 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
Добиеме hashCode 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
>> Ние не сакаме да clobber
Џои, и ние сме веќе

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
Сега ние може да се сместат двајца
елементи со hashCode 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
Јас сум Даг Лојд, ова е CS50.

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