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