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
Гэта будзе мець 16384 вёдраў, але
гэта лік не мае вялікага значэння.

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