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