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
Тэта мы не абмяркоўвалі,
але тэта толькі ў сярэднім выпадку,

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
Час становіцца бліжэй да
тэта п, і мы ў асноўным

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
мы звычайна называем хэш-код, ОК?

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
хэш, які генеруецца 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
Такім чынам, мы не хочам, каб выкарыстоўваць 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
у хэш-функцыі мы заўсёды
атрымаць той жа хэш-код з.

126
00:05:50,040 --> 00:05:52,870
Калі я праходжу Джона ў
Хэш функцыя я выходжу 4.

127
00:05:52,870 --> 00:05:56,110
Я павінен быць у стане зрабіць гэта 10000
раз, і я заўсёды буду атрымаць 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
Калі кожны раз, калі вы запусціце дадзеныя праз
Хэш функцыя, якую вы атрымаеце хэш 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
вяртанне некаторы хэш
Каментары ад 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
>> ТАКІМ ЧЫНАМ, давайце вярнуцца да гэтага
Хэш-табліца на секунду.

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
Я ўжо атрымаў дадзеныя ў
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
у адваротным выпадку мы б не працуе Рынга
адвольна праз хэш-функцыі.

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
давайце яго на 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
Можа быць, мы не павінны шукаць
усе п элементаў хэш-табліцы.

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
Так, і блізка да 7, 8, так, калі
у нас ёсць, каб пачаць пошук мы

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
Калі мы хочам працягваць хэш
грамадзяне Спрынгфілда,

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,
ці Аб п дзеліцца на 1000.

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 паказальнікаў NULL.

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
Так давайце дынамічна
вылучыць месца для Joey,

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
Цяпер мы можам захоўваць два
элементы з 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