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

2
00:00:11,856 --> 00:00:13,050
>> Rob Bowden: Hi.

3
00:00:13,050 --> 00:00:16,210
Mən Rob deyiləm, və edək hash
bu həlli.

4
00:00:16,210 --> 00:00:20,070
Belə ki, burada biz həyata olacaq
ümumi hash table.

5
00:00:20,070 --> 00:00:24,090
Biz görürük ki, bizim hash struct node
masa bu kimi baxmaq edir.

6
00:00:24,090 --> 00:00:28,710
Belə ki, bir char söz var olacaq
ölçüsü uzunluğu plus 1 array.

7
00:00:28,710 --> 00:00:32,259
Maksimum ildən 1 unutmayın
Lüğətə söz 45

8
00:00:32,259 --> 00:00:35,110
simvol, sonra biz olacaq
üçün bir əlavə xarakter lazımdır

9
00:00:35,110 --> 00:00:37,070
backslash 0.

10
00:00:37,070 --> 00:00:40,870
>> Və sonra hər bizim hash table
bucket saxlamaq üçün gedir bir

11
00:00:40,870 --> 00:00:42,320
qovşaqlarının bağlı siyahı.

12
00:00:42,320 --> 00:00:44,420
Biz burada probing xətti məşğul deyilik.

13
00:00:44,420 --> 00:00:48,430
Və sifariş növbəti keçid
bucket element, biz lazımdır

14
00:00:48,430 --> 00:00:51,110
struct node * Növbəti.

15
00:00:51,110 --> 00:00:53,090
Belə ki, bir node kimi görünür nə.

16
00:00:53,090 --> 00:00:56,180
İndi burada elan edir
Bizim hash masa.

17
00:00:56,180 --> 00:01:01,910
Bu 16.384 buketler var olacaq lakin
ki sayı həqiqətən etməz.

18
00:01:01,910 --> 00:01:05,450
Və nəhayət, biz olacaq
qlobal dəyişən hashtable_size olan

19
00:01:05,450 --> 00:01:08,640
0 kimi başlamaq üçün gedir və bu edilir
takip gedir neçə söz

20
00:01:08,640 --> 00:01:10,080
bizim lüğət idi.

21
00:01:10,080 --> 00:01:10,760
Bütün hüquqlar.

22
00:01:10,760 --> 00:01:13,190
>> Belə ki, yük bir nəzər salaq.

23
00:01:13,190 --> 00:01:16,390
Belə ki yük fark,
bu bir bool qaytarır.

24
00:01:16,390 --> 00:01:20,530
Uğurla, əgər doğru qayıtmaq
başqa dolu və yalan.

25
00:01:20,530 --> 00:01:23,990
Və bir const char * ulduz edir
lüğət olan lüğət,

26
00:01:23,990 --> 00:01:25,280
açmaq istəyirəm.

27
00:01:25,280 --> 00:01:27,170
Belə ki, ilk şey
biz nə olacaq.

28
00:01:27,170 --> 00:01:30,420
Biz lüğət fopen olacaq
oxu, və biz olacaq

29
00:01:30,420 --> 00:01:34,700
belə əgər nail əmin etmək
NULL döndü, sonra biz etmədik

30
00:01:34,700 --> 00:01:37,440
uğurla lüğət açmaq
və biz yalan qayıtmaq lazımdır.

31
00:01:37,440 --> 00:01:41,580
>> Amma bu uğurla etdi ki, fərz
açıq, sonra biz oxumaq istəyirəm

32
00:01:41,580 --> 00:01:42,400
lüğət.

33
00:01:42,400 --> 00:01:46,210
Biz bəzi tapmaq qədər loop saxlamaq
Bu çıxmaq üçün səbəb

34
00:01:46,210 --> 00:01:47,570
biz görəcəksiniz olan loop.

35
00:01:47,570 --> 00:01:51,780
Belə ki, loop saxlamaq, və indi biz gedirik
bir node malloc.

36
00:01:51,780 --> 00:01:56,800
Və əlbəttə ki, biz çek səhv lazımdır
daha mallocing müvəffəqiyyətli ola bilmədi əgər

37
00:01:56,800 --> 00:02:00,660
və biz ki, biz hər hansı bir node boşaltmaq istəyirəm
əvvəl malloc nə oldu da, yaxın

38
00:02:00,660 --> 00:02:02,590
lüğət və saxta qayıtmaq.

39
00:02:02,590 --> 00:02:07,440
>> Amma məhəl fərz biz
nail, sonra biz fscanf istifadə etmək istədiyiniz

40
00:02:07,440 --> 00:02:12,400
bir tək söz oxumaq bizim
bizim node daxil lüğət.

41
00:02:12,400 --> 00:02:17,310
Belə ki, giriş-> sözü xatırlayıram char
söz ölçüsü uzunluğu bufer plus

42
00:02:17,310 --> 00:02:20,300
biz olacaq ki, bir
da söz saxlamaq

43
00:02:20,300 --> 00:02:25,280
Belə ki, fscanf 1 kimi uzun qayıtmaq üçün gedir
uğurla oxumaq mümkün idi

44
00:02:25,280 --> 00:02:26,750
faylı söz.

45
00:02:26,750 --> 00:02:31,030
>> Bir səhv ya olur ya biz ulaşırsanız
fayl sonu, olmayacaq

46
00:02:31,030 --> 00:02:34,950
bu deyil, əgər bu halda 1 qayıtmaq
1 qayıtmaq, biz nəhayət qırmaq olacaq

47
00:02:34,950 --> 00:02:37,280
Bu isə loop həyata.

48
00:02:37,280 --> 00:02:42,770
Beləliklə, biz görürük ki, biz uğurla dəfə
bir sözü oxumaq

49
00:02:42,770 --> 00:02:48,270
giriş-> söz, sonra biz hash olacaq
bizim hash funksiyası istifadə ki, söz.

50
00:02:48,270 --> 00:02:49,580
Nin bir nəzər salaq
hash funksiyası.

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

52
00:02:52,430 --> 00:02:55,610
>> Beləliklə, siz həqiqətən ehtiyac yoxdur
Bu anlamaq üçün.

53
00:02:55,610 --> 00:02:59,460
Və həqiqətən, biz yalnız bu çıxardı
internet funksiyası hash.

54
00:02:59,460 --> 00:03:04,010
Siz tanımaq lazımdır yalnız şey
bu bir const char * söz edir ki,

55
00:03:04,010 --> 00:03:08,960
belə ki, giriş kimi bir string alaraq və edir
çıxış kimi bir imzasız int qaytarılması.

56
00:03:08,960 --> 00:03:12,360
Belə ki, bütün bir hash funksiyası olunur, bu
bir giriş edir, o, bir verir

57
00:03:12,360 --> 00:03:14,490
hash masa daxil index.

58
00:03:14,490 --> 00:03:18,530
Biz NUM_BUCKETS ilə modding edirik ki, görürsünüz
belə ki, hash dəyəri döndü

59
00:03:18,530 --> 00:03:21,730
əslində hash table bir göstəricidir
və nə kənarda deyil index

60
00:03:21,730 --> 00:03:24,320
serialın həddi.

61
00:03:24,320 --> 00:03:27,855
>> Belə ki, hash funksiyası, biz olacaq ki, verilmiş
biz oxumaq söz hash

62
00:03:27,855 --> 00:03:31,700
Lüğətə və sonra olacaq
ki, istifadə üçün daxil var

63
00:03:31,700 --> 00:03:33,750
hash masa daxil giriş.

64
00:03:33,750 --> 00:03:38,830
İndi hashtable hash, cari
bağlı hash cədvəldə siyahısı, və

65
00:03:38,830 --> 00:03:41,410
yalnız NULL ki, çox mümkündür.

66
00:03:41,410 --> 00:03:45,640
Biz bizim giriş əlavə etmək istəyirsiniz
Bu bağlı siyahı başlayan və belə

67
00:03:45,640 --> 00:03:48,910
biz cari giriş olacaq
Hal-hazırda nə hash masa qeyd

68
00:03:48,910 --> 00:03:54,030
bal və sonra saxlamaq olacaq
Bu hash da hash cədvəldə

69
00:03:54,030 --> 00:03:55,350
cari giriş.

70
00:03:55,350 --> 00:03:59,320
>> Belə ki, bu iki xətləri uğurla daxil
nın başında giriş

71
00:03:59,320 --> 00:04:02,270
ki, index at bağlı siyahı
hash cədvəldə.

72
00:04:02,270 --> 00:04:04,900
Biz ilə tamamlayın sonra, biz bilirik
biz başqa söz aşkar ki,

73
00:04:04,900 --> 00:04:07,800
lüğət və biz yenə arttırmayı.

74
00:04:07,800 --> 00:04:13,960
Beləliklə, biz bunu saxlamaq fscanf qədər
nəhayət qeyri bir şey 1 qaytarır

75
00:04:13,960 --> 00:04:18,560
olan point biz lazımdır ki, unutmayın
pulsuz giriş, belə ki, burada biz malloced

76
00:04:18,560 --> 00:04:21,329
giriş və biz bir şey oxumaq üçün cəhd
lüğət.

77
00:04:21,329 --> 00:04:24,110
Və biz uğurla oxumaq etməyib
Lüğətə bir şey olan

78
00:04:24,110 --> 00:04:27,440
halda ki, biz giriş azad etmək lazımdır
əslində hash masa qoymaq heç

79
00:04:27,440 --> 00:04:29,110
və nəhayət qırmaq.

80
00:04:29,110 --> 00:04:32,750
>> Biz çıxmaq sonra, biz də, görmək lazımdır
çünki orada çıxmaq etməyib

81
00:04:32,750 --> 00:04:35,840
bir səhv fayl oxu, və ya edilmişdir
biz əldə çünki biz çıxmaq etməyib

82
00:04:35,840 --> 00:04:37,120
fayl sonu?

83
00:04:37,120 --> 00:04:40,150
Bir səhv var idi, onda biz istəyirik
yük idi, çünki yalan qayıtmaq

84
00:04:40,150 --> 00:04:43,260
uğur və prosesi, biz istəyirik
biz oxumaq ki, bütün sözləri boşaltmaq

85
00:04:43,260 --> 00:04:45,670
və lüğət fayl bağlayın.

86
00:04:45,670 --> 00:04:48,740
Biz nail ola bildimi etsək, onda biz yalnız
hələ lüğət bağlamaq lazımdır

87
00:04:48,740 --> 00:04:51,970
fayl, və nəhayət ildən doğru qayıtmaq
biz uğurla yüklü etdiyiniz

88
00:04:51,970 --> 00:04:53,040
lüğət.

89
00:04:53,040 --> 00:04:54,420
Və yük üçün var.

90
00:04:54,420 --> 00:04:59,020
>> Belə ki, indi bir dolu hash table verilmiş, yoxlamaq,
bu kimi baxmaq edir.

91
00:04:59,020 --> 00:05:02,690
Belə ki, bir bool qaytarır, yoxlamaq
göstərir gedir olub

92
00:05:02,690 --> 00:05:07,530
keçdi-in char * sözü də olub
keçdi-in string bizim lüğət edir.

93
00:05:07,530 --> 00:05:10,530
Bu lüğət belə, əgər əgər
bizim hash masa, biz qayıdacaqlar

94
00:05:10,530 --> 00:05:13,380
doğru və bu deyil, əgər,
biz yalan qayıdacaqlar.

95
00:05:13,380 --> 00:05:17,770
Bu keçdi-in söz alaraq, biz istəyirik
sözü hash gedir.

96
00:05:17,770 --> 00:05:22,020
>> İndi, tanımaq üçün əhəmiyyətli bir şeydir
yük, biz bilirdik ki, bütün

97
00:05:22,020 --> 00:05:25,820
sözləri aşağı halda olacaq idi,
lakin burada, biz əmin deyilik.

98
00:05:25,820 --> 00:05:29,510
Biz hash funksiyası nəzər varsa,
həqiqətən, bizim hash funksiyası

99
00:05:29,510 --> 00:05:32,700
hər bir xarakter lowercasing olunur
Sözün.

100
00:05:32,700 --> 00:05:37,580
Belə ki, asılı olmayaraq Kapitallaşma
söz, bizim hash funksiyası gedir

101
00:05:37,580 --> 00:05:42,270
nə üçün eyni index qayıtmaq
kapitalizasiyası var ki kimi

102
00:05:42,270 --> 00:05:45,280
tamamilə kiçik qayıtdı
Sözün versiyası.

103
00:05:45,280 --> 00:05:45,950
Bütün hüquqlar.

104
00:05:45,950 --> 00:05:47,410
>> Belə ki, bizim index var.

105
00:05:47,410 --> 00:05:49,790
Bu söz üçün hash masa var.

106
00:05:49,790 --> 00:05:52,940
İndi loop üçün bu gedir
bağlı siyahı artıq üçün

107
00:05:52,940 --> 00:05:55,000
ki, index idi.

108
00:05:55,000 --> 00:05:59,630
Beləliklə, biz giriş başlatılıyor fark
ki, index qeyd etmək.

109
00:05:59,630 --> 00:06:03,480
Biz giriş nə isə davam edirik
bərabər NULL, və unutmayın ki,

110
00:06:03,480 --> 00:06:08,350
Bizim bağlı siyahısında göstərici yenilənməsi
giriş Növbəti giriş-> bərabərdir, belə ki, var

111
00:06:08,350 --> 00:06:13,840
Bu bizim cari giriş nöqtəsi
bağlı siyahısında növbəti maddə.

112
00:06:13,840 --> 00:06:14,400
Bütün hüquqlar.

113
00:06:14,400 --> 00:06:19,150
>> Belə ki bağlı siyahı hər giriş üçün,
biz strcasecmp istifadə etmək olacaq.

114
00:06:19,150 --> 00:06:23,780
Bu strcmp deyil, çünki bir dəfə daha, biz
insensitively şey işi etmək istəyirəm.

115
00:06:23,780 --> 00:06:28,830
Belə ki, biz söz müqayisə etmək strcasecmp istifadə
ki, bu funksiya keçildi

116
00:06:28,830 --> 00:06:31,860
sözü qarşı
Bu giriş edir.

117
00:06:31,860 --> 00:06:35,570
Bu 0 qaytarır ki, var idi deməkdir
biz istədiyiniz halda bir matç,

118
00:06:35,570 --> 00:06:36,630
doğru geri.

119
00:06:36,630 --> 00:06:39,590
Biz uğurla tapıldı
bizim hash cədvəldə söz.

120
00:06:39,590 --> 00:06:43,040
>> Bir matç yox idi, onda biz istəyirik
yenidən loop gedən və baxmaq

121
00:06:43,040 --> 00:06:43,990
növbəti giriş.

122
00:06:43,990 --> 00:06:47,640
Və biz isə orada loop davam edəcəyik
bu bağlı siyahısında entries var.

123
00:06:47,640 --> 00:06:50,160
Biz qırmaq əgər nə olur
loop üçün bu həyata?

124
00:06:50,160 --> 00:06:55,110
Yəni biz bir giriş tapmadı deməkdir ki,
olan halda, bu söz eşleşen

125
00:06:55,110 --> 00:07:00,220
biz göstərir yalan qayıtmaq ki, bizim
hash table bu söz yox idi.

126
00:07:00,220 --> 00:07:01,910
Və yoxlamaq üçün bu.

127
00:07:01,910 --> 00:07:02,540
Bütün hüquqlar.

128
00:07:02,540 --> 00:07:04,790
>> Belə ki, ölçüsü bir nəzər salaq.

129
00:07:04,790 --> 00:07:09,280
İndi ölçüsü olduqca sadə olacaq
ildən hər bir söz üçün, yük xatırlayıram

130
00:07:09,280 --> 00:07:12,880
biz qlobal artırılacağını tapılmadı
dəyişən hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Belə ki, ölçüsü funksiyası yalnız
ki, qlobal geri olacaq

132
00:07:15,830 --> 00:07:18,150
dəyişən, və bu.

133
00:07:18,150 --> 00:07:22,300
>> İndi, nəhayət, biz boşaltmaq lazımdır
lüğət hər şey həyata bir dəfə.

134
00:07:22,300 --> 00:07:25,340
Belə ki, necə biz bunu edəcəyik?

135
00:07:25,340 --> 00:07:30,440
Burada, biz bütün loop edirik
Bizim hash masa buketler.

136
00:07:30,440 --> 00:07:33,240
Belə ki, NUM_BUCKETS buketler var.

137
00:07:33,240 --> 00:07:37,490
Və bizim hash hər bağlıdır siyahısı üçün
masa, biz artıq loop olacaq

138
00:07:37,490 --> 00:07:41,070
bağlı siyahı bütövlükdə
hər element azad.

139
00:07:41,070 --> 00:07:46,070
İndi biz ehtiyatlı olmaq lazımdır, belə ki, burada biz
ki, bir müvəqqəti dəyişən var

140
00:07:46,070 --> 00:07:49,740
növbəti göstərici saxlanılması
bağlı siyahısında element.

141
00:07:49,740 --> 00:07:52,140
Və sonra biz pulsuz olacaq
cari element.

142
00:07:52,140 --> 00:07:55,990
>> Biz bəri bunu əmin olmaq lazımdır
yalnız cari element azad edə bilməz

143
00:07:55,990 --> 00:07:59,260
və sonra növbəti pointer daxil olmaq üçün cəhd edin
ildən sonra biz onu azad

144
00:07:59,260 --> 00:08:00,870
yaddaş etibarsız olur.

145
00:08:00,870 --> 00:08:04,990
Beləliklə, biz bir pointer ətrafında saxlamaq lazımdır
növbəti element, sonra biz azad edə bilər

146
00:08:04,990 --> 00:08:08,360
cari element, sonra biz təkmilləşdirə bilər
qeyd etmək bizim cari element

147
00:08:08,360 --> 00:08:09,590
növbəti element.

148
00:08:09,590 --> 00:08:12,770
>> Biz elementləri loop var lazımdır isə
bu bağlı siyahısında.

149
00:08:12,770 --> 00:08:16,450
Biz bütün bağlı siyahıları ki edəcəyik
hash table, və biz tamamlayın dəfə

150
00:08:16,450 --> 00:08:20,180
ki, biz tamamilə boşaldılır etdik
hash table, və biz tamamlayın.

151
00:08:20,180 --> 00:08:24,050
Belə ki, unloads üçün heç mümkün deyil
yalan qayıtmaq və biz Bitirdiğinizde, biz

152
00:08:24,050 --> 00:08:25,320
yalnız doğru qayıdın.

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