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
без да се налага да превъртите цяла.

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
Theta ние наистина не са обсъдени,
но тета е само средния случай,

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
ние обикновено наричаме хеш-код, OK?

68
00:03:14,870 --> 00:03:20,230
Втората част е масив, което е
с възможност за съхраняване на данни от тип WE

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
И така, данните се обработват
и да го изплюе редица, OK?

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
Така John като данните, които искате да вмъкнете
в този хеш таблица някъде.

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
>> И нека да кажем, че ще свършим John
чрез този хеш-функция

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
Ние искаме да се сложи John в населено място масив
4, защото ако хеш John again--

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

92
00:04:23,810 --> 00:04:26,960
ако John съществува в този хеш
table-- всички ние трябва да направим

93
00:04:26,960 --> 00:04:30,310
е да го ползвате през една и съща хеш
функция, получи номер 4,

94
00:04:30,310 --> 00:04:33,929
и да бъде в състояние да намери John
веднага в нашата структура на данните.

95
00:04:33,929 --> 00:04:34,720
Това е доста добър.

96
00:04:34,720 --> 00:04:36,928
>> Да кажем, че ние сега да направите това
отново, искаме да хеш Paul.

97
00:04:36,928 --> 00:04:39,446
Искаме да добавим Paul
в този хеш-таблица.

98
00:04:39,446 --> 00:04:42,070
Да кажем, че този път ще свършим
Paul чрез хеш функция,

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

100
00:04:44,600 --> 00:04:47,340
Е, сега можем да сложим Paul
в мястото на масива 6.

101
00:04:47,340 --> 00:04:50,040
И ако трябва да погледнем нагоре дали
Павел е в този хеш таблица,

102
00:04:50,040 --> 00:04:53,900
всичко, което трябва да направите, е да стартирате Paul
чрез функцията за сегментиране отново

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
Така че ние не искаме да използваме 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
Функция A хеш следва
също така да бъде детерминирана.

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
Ако минавам John в
хеш функция изляза 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
>> Функция A хеш следва също
равномерно разпространение на данни.

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
И тогава очевидно аз правя нещо
докато 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 [к], за да обобщим, а след това в
края на деня ще се върне сума мод

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
връщане на някои хеш-код
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
Но когато всъщност ще
започнете хеширане на данни и съхранение

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
>> Какво става, ако хеш Ringo, и то
Оказва се, че след преработка

192
00:09:06,770 --> 00:09:14,000
че данните през разбъркващата функция
Ringo също генерира хеш-код 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
функция получава същото хеш-код.

198
00:09:29,200 --> 00:09:32,850
Предполага се, че ние все още искате да получите и двете
парчета от данни в хеш таблица,

199
00:09:32,850 --> 00:09:36,330
в противен случай ние няма да се работи Ringo
произволно чрез хеш функция.

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
Ние не искаме да презапишете Paul,
искаме Павел да бъде там също.

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
и бягаме Bart чрез хеш
функция, получаваме хеш-код 6.

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

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
Ние не можем да сложи Lisa в 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
Така че нека да поставим Lisa там.

230
00:11:06,510 --> 00:11:10,200
>> Сега ние хеш Омир и получаваме 7.

231
00:11:10,200 --> 00:11:13,380
OK добре знаем, че 7 е пълен
сега, така че не можем да сложи Homer там.

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
към тета п.

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
Ако искаме да продължим да хеш
гражданите на Springfield,

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 на п,

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

294
00:14:19,590 --> 00:14:24,120
сега това е О п делено на 10,
О или 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 пъти по-бързо,
или 1000 пъти по-бързо,

300
00:14:36,610 --> 00:14:41,570
защото ние сме разпространение на една дълга
верига през 1000-малки вериги.

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
>> Което е средно до
да бъде 1000 пъти по-кратък.

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
Ние ще ще се проведе на низа Joey чрез
хеш функция и да се върнем 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
Когато се разискват Joey ние имаме хеш-код 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
>> Така че, ако трябва да погледнем нагоре Joey
по-късно, ние просто хеш Джоуи отново,

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
Нека сега хеш Ross.

348
00:17:04,290 --> 00:17:07,540
>> И нека да кажем, Ross, когато го правим, че
кода за сегментиране се върнем е 2.

349
00:17:07,540 --> 00:17:10,630
Е, сега сме динамично разпредели
нов възел, ние поставяме Ross в този възел,

350
00:17:10,630 --> 00:17:14,900
и ние казваме сега местоположение масив
2, вместо да сочи към нула,

351
00:17:14,900 --> 00:17:18,579
сочи към главата на свързан
списък, чийто единствен възел е Ross.

352
00:17:18,579 --> 00:17:22,660
И ние можем да направим това още един път, ние
може хеш Рейчъл и да получите хеш-код 4.

353
00:17:22,660 --> 00:17:25,490
изчистване на нов възел, постави Rachel в
възела, и да кажа на местоположение масив

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
Аз съм Дъг Лойд, това е CS50.

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