1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Привет.

3
00:00:13,050 --> 00:00:16,210
Я Роб, и давайте хэш
это решение вне.

4
00:00:16,210 --> 00:00:20,070
И вот мы собираемся реализовать
общий хэш-таблицы.

5
00:00:20,070 --> 00:00:24,090
Мы видим, что структура узла нашего хэша
таблица будет выглядеть следующим образом.

6
00:00:24,090 --> 00:00:28,710
Так что это будет иметь сЬаг слово
Массив размер длина плюс 1.

7
00:00:28,710 --> 00:00:32,259
Не забывайте, 1, так как максимум
слово в словаре 45

8
00:00:32,259 --> 00:00:35,110
символов, а затем мы собираемся
нужен один дополнительный символ для

9
00:00:35,110 --> 00:00:37,070
обратный слеш 0.

10
00:00:37,070 --> 00:00:40,870
>> А потом наш хэш-таблицы в каждом
ведро собирается хранить

11
00:00:40,870 --> 00:00:42,320
связанный список узлов.

12
00:00:42,320 --> 00:00:44,420
Мы не делаем линейную зондирования здесь.

13
00:00:44,420 --> 00:00:48,430
И поэтому для того, чтобы связать к следующему
элемент в ведро, мы должны

14
00:00:48,430 --> 00:00:51,110
структура узла * следующий.

15
00:00:51,110 --> 00:00:53,090
Так вот что узел выглядит.

16
00:00:53,090 --> 00:00:56,180
Теперь, вот декларация
нашей хэш-таблицы.

17
00:00:56,180 --> 00:01:01,910
Это будет иметь 16 384 ведер, но
это число не имеет большого значения.

18
00:01:01,910 --> 00:01:05,450
И, наконец, мы собираемся иметь
глобальная переменная hashtable_size, которые

19
00:01:05,450 --> 00:01:08,640
собирается начать как 0, и это
собирается отслеживать, сколько слов

20
00:01:08,640 --> 00:01:10,080
были в нашем словаре.

21
00:01:10,080 --> 00:01:10,760
Хорошо.

22
00:01:10,760 --> 00:01:13,190
>> Так что давайте взглянем на нагрузке.

23
00:01:13,190 --> 00:01:16,390
Так заметить, что нагрузки,
она возвращает логическое значение.

24
00:01:16,390 --> 00:01:20,530
Вы возвращаетесь верно, если это было успешно
загружен и в противном случае.

25
00:01:20,530 --> 00:01:23,990
И это занимает константный символ * звезду
словарь, который является словарь

26
00:01:23,990 --> 00:01:25,280
что мы хотим открыть.

27
00:01:25,280 --> 00:01:27,170
Так вот первое, что
мы собираемся сделать.

28
00:01:27,170 --> 00:01:30,420
Мы собираемся открыть поток, словарь для
чтение, и мы будем иметь

29
00:01:30,420 --> 00:01:34,700
чтобы убедиться, что это удалось, так что если
он вернулся NULL, то мы не сделали

30
00:01:34,700 --> 00:01:37,440
успешно открыть словарь
и мы должны вернуться ложным.

31
00:01:37,440 --> 00:01:41,580
>> Но если предположить, что это было успешно
открыто, то мы хотим, чтобы прочитать

32
00:01:41,580 --> 00:01:42,400
словарь.

33
00:01:42,400 --> 00:01:46,210
Так что держите цикл, пока не найдем некоторые
Причина, чтобы вырваться из этого

34
00:01:46,210 --> 00:01:47,570
цикл, который мы будем видеть.

35
00:01:47,570 --> 00:01:51,780
Так что держите цикла, и теперь мы собираемся
чтобы Malloc один узел.

36
00:01:51,780 --> 00:01:56,800
И, конечно, мы должны об ошибках веб-
снова, так что если mallocing не удалось

37
00:01:56,800 --> 00:02:00,660
и мы хотим, чтобы разгрузить любой узел, который мы
случилось с таНос раньше, закрыть

38
00:02:00,660 --> 00:02:02,590
словарь и вернуться ложным.

39
00:02:02,590 --> 00:02:07,440
>> Но игнорируя, что, предполагая, что мы
удалось, то мы хотим использовать fscanf

40
00:02:07,440 --> 00:02:12,400
читать ни одного слова из нашего
словарь в нашу узла.

41
00:02:12,400 --> 00:02:17,310
Так что помните, что вступление-> слово является символ
слово буфера длины плюс размер

42
00:02:17,310 --> 00:02:20,300
тот, который мы собираемся
хранить слово дюйма

43
00:02:20,300 --> 00:02:25,280
Так fscanf собирается вернуться 1 до тех пор,
, как это было в состоянии успешно читать

44
00:02:25,280 --> 00:02:26,750
слово из файла.

45
00:02:26,750 --> 00:02:31,030
>> Если один происходит ошибка или мы достигнем
конец файла, он не будет

46
00:02:31,030 --> 00:02:34,950
возвращает 1 в этом случае, если он не
возвращает 1, мы, наконец, собирается сломать

47
00:02:34,950 --> 00:02:37,280
из этого время цикла.

48
00:02:37,280 --> 00:02:42,770
Итак, мы видим, что как только у нас есть успешно
читать слово в

49
00:02:42,770 --> 00:02:48,270
запись-> слово, то, что мы собираемся, чтобы прояснить
это слово с помощью нашего хэш-функцию.

50
00:02:48,270 --> 00:02:49,580
Давайте взглянем на
хэш-функция.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> Таким образом, вы действительно не нужно
чтобы понять это.

53
00:02:55,610 --> 00:02:59,460
А на самом деле, мы просто вытащил этот
хэш-функция из Интернета.

54
00:02:59,460 --> 00:03:04,010
Единственное, что вы должны признать это
что это занимает константный символ * слово,

55
00:03:04,010 --> 00:03:08,960
так это занимает строку в качестве входных данных и
возвращения без знака Int как выход.

56
00:03:08,960 --> 00:03:12,360
Так что все хэш-функция, это
принимает в качестве вклада, это дает вам

57
00:03:12,360 --> 00:03:14,490
индекс в хэш-таблице.

58
00:03:14,490 --> 00:03:18,530
Обратите внимание, что мы моддинг по NUM_BUCKETS
так что значение хэш возвращается

59
00:03:18,530 --> 00:03:21,730
на самом деле является индексом в хэш-таблице
и не индексирует за

60
00:03:21,730 --> 00:03:24,320
Границы массива.

61
00:03:24,320 --> 00:03:27,855
>> Поэтому, учитывая, что хэш-функция, мы собираемся
чтобы прояснить слово, что мы читаем

62
00:03:27,855 --> 00:03:31,700
из словаря, а затем мы собираемся
в использовании, что имеет для вставки

63
00:03:31,700 --> 00:03:33,750
вступление в хэш-таблице.

64
00:03:33,750 --> 00:03:38,830
Теперь, хеш-таблица хэш текущий
связанный список в хэш-таблице, и

65
00:03:38,830 --> 00:03:41,410
это очень возможно, что это просто NULL.

66
00:03:41,410 --> 00:03:45,640
Мы хотим, чтобы вставить нашу запись в
в начале этого связанного списка, и так

67
00:03:45,640 --> 00:03:48,910
мы собираемся, чтобы иметь нашу текущую запись
указывают на то, что хэш-таблице в настоящее время

68
00:03:48,910 --> 00:03:54,030
указывает на, а затем мы собираемся хранить
в хэш-таблице на хэш

69
00:03:54,030 --> 00:03:55,350
текущая запись.

70
00:03:55,350 --> 00:03:59,320
>> Таким образом, эти две линии успешно вставить
вступление в начале

71
00:03:59,320 --> 00:04:02,270
Связанный список по этому индексу
в хэш-таблице.

72
00:04:02,270 --> 00:04:04,900
После того, как мы закончим с этим, мы знаем,
что мы нашли еще одно слово в

73
00:04:04,900 --> 00:04:07,800
словарь и мы увеличиваем снова.

74
00:04:07,800 --> 00:04:13,960
Таким образом, мы продолжать делать это до fscanf
наконец, возвращается что-то без 1 на

75
00:04:13,960 --> 00:04:18,560
чего помните, что нам нужно
свободный вход, поэтому здесь мы malloced

76
00:04:18,560 --> 00:04:21,329
запись и мы попытались прочитать что-то
из словаря.

77
00:04:21,329 --> 00:04:24,110
И мы не успешно прочитаны
что-то из словаря, в котором

78
00:04:24,110 --> 00:04:27,440
когда мы должны освободить запись, мы
никогда не помещается в хэш-таблице

79
00:04:27,440 --> 00:04:29,110
и, наконец, сломать.

80
00:04:29,110 --> 00:04:32,750
>> Как только мы вырваться, мы должны видеть, ну,
же мы вырваться, потому что

81
00:04:32,750 --> 00:04:35,840
Произошла ошибка чтения из файла, или
же мы вырваться, потому что мы достигли

82
00:04:35,840 --> 00:04:37,120
конец файла?

83
00:04:37,120 --> 00:04:40,150
Если произошла ошибка, то мы хотим
вернуться ложным, потому что нагрузка не сделал

84
00:04:40,150 --> 00:04:43,260
добиться успеха, и в этом процессе, мы хотим
выгрузить все слова, которые мы читаем

85
00:04:43,260 --> 00:04:45,670
в и закрыть файл словаря.

86
00:04:45,670 --> 00:04:48,740
Предположим, что мы преуспели, то мы просто
еще нужно закрыть словарь

87
00:04:48,740 --> 00:04:51,970
файл, и, наконец, вернуться верно, так как
мы успешно загружен

88
00:04:51,970 --> 00:04:53,040
словарь.

89
00:04:53,040 --> 00:04:54,420
И это все на груз.

90
00:04:54,420 --> 00:04:59,020
>> Так что теперь проверить, учитывая загруженный хеш-таблицы,
будет выглядеть следующим образом.

91
00:04:59,020 --> 00:05:02,690
Поэтому проверить, она возвращает логическое значение, которое
собирается указать, является ли

92
00:05:02,690 --> 00:05:07,530
переданное символ * слова, будь то
переданная строка находится в нашем словаре.

93
00:05:07,530 --> 00:05:10,530
Таким образом, если она присутствует в словаре, если это
в нашей хэш-таблицы, мы вернемся

94
00:05:10,530 --> 00:05:13,380
правда, и если это не так,
мы вернемся ложным.

95
00:05:13,380 --> 00:05:17,770
Учитывая это прошло в слово, что мы
собирается хэш слово.

96
00:05:17,770 --> 00:05:22,020
>> Теперь главное, чтобы признать,
что в нагрузке, мы знали, что все

97
00:05:22,020 --> 00:05:25,820
слова собирались быть в нижнем регистре,
но здесь, мы не так уверены.

98
00:05:25,820 --> 00:05:29,510
Если мы взглянем на наш хэш-функции,
наш хэш-функция на самом деле

99
00:05:29,510 --> 00:05:32,700
является lowercasing каждый символ
слова.

100
00:05:32,700 --> 00:05:37,580
Поэтому, независимо от капитализации
Слово, наш хэш-функция будет

101
00:05:37,580 --> 00:05:42,270
вернуться тот же индекс по каким-либо
капитализация как она должна была бы

102
00:05:42,270 --> 00:05:45,280
вернулись на совершенно нижнем регистре
вариант слова.

103
00:05:45,280 --> 00:05:45,950
Хорошо.

104
00:05:45,950 --> 00:05:47,410
>> Так вот наш индекс.

105
00:05:47,410 --> 00:05:49,790
Это хэш-таблица для этого слова.

106
00:05:49,790 --> 00:05:52,940
Теперь, это цикл будет
до более чем связанный список

107
00:05:52,940 --> 00:05:55,000
это было по этому индексу.

108
00:05:55,000 --> 00:05:59,630
Так заметить мы инициализации запись
указать на то индекс.

109
00:05:59,630 --> 00:06:03,480
Мы собираемся продолжать в то время как запись делает
не равно NULL, и помните, что

110
00:06:03,480 --> 00:06:08,350
обновления указатель в нашей связанного списка
запись равна начального> следующая, так что есть

111
00:06:08,350 --> 00:06:13,840
наша нынешняя точка входа в
Следующий пункт в связанном списке.

112
00:06:13,840 --> 00:06:14,400
Хорошо.

113
00:06:14,400 --> 00:06:19,150
>> Таким образом, для каждой записи в связанном списке,
мы собираемся использовать strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Это не STRCMP потому что еще раз, мы
хочу сделать вещи случай бесчувственно.

115
00:06:23,780 --> 00:06:28,830
Поэтому мы используем strcasecmp сравнить слово
, который был принят в эту функцию

116
00:06:28,830 --> 00:06:31,860
против слова, которые
в данной записи.

117
00:06:31,860 --> 00:06:35,570
Если она возвращает 0, это означает, что было
матч, в этом случае мы хотим

118
00:06:35,570 --> 00:06:36,630
вернуться верно.

119
00:06:36,630 --> 00:06:39,590
Мы успешно нашли
Слово в нашей хэш-таблицы.

120
00:06:39,590 --> 00:06:43,040
>> Если бы не было матча, то мы
собирается цикле снова и посмотреть на

121
00:06:43,040 --> 00:06:43,990
Следующая запись.

122
00:06:43,990 --> 00:06:47,640
И мы будем продолжать зацикливание в то время как есть
являются записи в этой связанного списка.

123
00:06:47,640 --> 00:06:50,160
Что произойдет, если мы нарушаем
из этого для цикла?

124
00:06:50,160 --> 00:06:55,110
Это означает, что мы не нашли запись,
соответствует это слово, в каком случае

125
00:06:55,110 --> 00:07:00,220
мы вернуться ложным, чтобы указать, что наш
хэш-таблицы не содержат это слово.

126
00:07:00,220 --> 00:07:01,910
И это все для проверки.

127
00:07:01,910 --> 00:07:02,540
Хорошо.

128
00:07:02,540 --> 00:07:04,790
>> Так что давайте взглянем на размер.

129
00:07:04,790 --> 00:07:09,280
Теперь размер будет довольно просто
так помню, в нагрузке, для каждого слова

130
00:07:09,280 --> 00:07:12,880
мы обнаружили, что увеличивается глобальная
Переменная hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Таким образом, функция размер как раз
собирается возвращаться, что глобальное

132
00:07:15,830 --> 00:07:18,150
переменная, и этим все сказано.

133
00:07:18,150 --> 00:07:22,300
>> Теперь, наконец, мы должны выгрузить
словарь, как только все будет сделано.

134
00:07:22,300 --> 00:07:25,340
Так как мы собираемся это сделать?

135
00:07:25,340 --> 00:07:30,440
Прямо здесь, мы пробегаем по всем
ведра нашей хэш-таблицы.

136
00:07:30,440 --> 00:07:33,240
Таким образом, есть NUM_BUCKETS ведра.

137
00:07:33,240 --> 00:07:37,490
И для каждого связанного списка в нашей хэш
стол, мы собираемся цикла по

138
00:07:37,490 --> 00:07:41,070
Совокупность связанного списка
освобождая каждый элемент.

139
00:07:41,070 --> 00:07:46,070
Теперь мы должны быть осторожны, так что здесь мы
есть временную переменную Это

140
00:07:46,070 --> 00:07:49,740
хранения указатель на следующий
элемент в связанном списке.

141
00:07:49,740 --> 00:07:52,140
А потом мы собираемся бесплатно
текущий элемент.

142
00:07:52,140 --> 00:07:55,990
>> Мы должны быть уверены, что мы делаем это, так как мы
не могу просто освободить текущий элемент

143
00:07:55,990 --> 00:07:59,260
, а затем попытаться перехода к следующей указатель
так как только мы освободили его

144
00:07:59,260 --> 00:08:00,870
память становится недействительным.

145
00:08:00,870 --> 00:08:04,990
Так что мы должны держать вокруг указатель на
на следующий элемент, то мы можем освободить

146
00:08:04,990 --> 00:08:08,360
текущий элемент, и тогда мы сможем обновить
наш текущий элемент, чтобы указать на

147
00:08:08,360 --> 00:08:09,590
следующий элемент.

148
00:08:09,590 --> 00:08:12,770
>> Мы будем цикл в то время как есть элементы
в этом связанном списке.

149
00:08:12,770 --> 00:08:16,450
Мы сделаем это для всех связанных списков в
хэш-таблица, и как только мы закончим

150
00:08:16,450 --> 00:08:20,180
с этим, мы полностью разгрузили
хэш-таблица, и мы закончили.

151
00:08:20,180 --> 00:08:24,050
Так что это невозможно для выгрузке когда-либо
вернуться ложным, и, когда мы закончим, мы

152
00:08:24,050 --> 00:08:25,320
просто вернуть верно.

153
00:08:25,320 --> 00:08:27,563