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
Saya Rob, dan hash yang disewakan ini
penyelesaian ini keluar.

4
00:00:16,210 --> 00:00:20,070
Jadi di sini kita akan melaksanakan
jadual hash umum.

5
00:00:20,070 --> 00:00:24,090
Kita lihat bahawa nod struct daripada hash kami
jadual akan kelihatan seperti ini.

6
00:00:24,090 --> 00:00:28,710
Jadi ia akan mempunyai perkataan char
pelbagai panjang saiz campur 1.

7
00:00:28,710 --> 00:00:32,259
Jangan lupa 1 sejak maksimum
perkataan dalam kamus ialah 45

8
00:00:32,259 --> 00:00:35,110
watak-watak, dan kemudian kita akan
memerlukan satu watak tambahan untuk

9
00:00:35,110 --> 00:00:37,070
garis sendeng terbalik 0.

10
00:00:37,070 --> 00:00:40,870
>> Dan kemudian jadual hash kita dalam setiap
baldi akan menyimpan

11
00:00:40,870 --> 00:00:42,320
senarai bersambung nod.

12
00:00:42,320 --> 00:00:44,420
Kami tidak melakukan linear menyelesaikan sesuatu di sini.

13
00:00:44,420 --> 00:00:48,430
Dan sebagainya untuk pautan ke seterusnya
elemen dalam baldi, kita memerlukan

14
00:00:48,430 --> 00:00:51,110
nod struct * seterusnya.

15
00:00:51,110 --> 00:00:53,090
Jadi itulah yang nod kelihatan seperti.

16
00:00:53,090 --> 00:00:56,180
Sekarang, di sini adalah pengakuan yang
jadual hash kami.

17
00:00:56,180 --> 00:01:01,910
Ia akan mempunyai 16,384 baldi, tetapi
jumlah itu tidak benar-benar perkara itu.

18
00:01:01,910 --> 00:01:05,450
Dan akhirnya, kita akan mempunyai
hashtable_size pembolehubah global, yang

19
00:01:05,450 --> 00:01:08,640
akan bermula sebagai 0, dan ia
akan mengesan berapa banyak perkataan

20
00:01:08,640 --> 00:01:10,080
berada dalam kamus kami.

21
00:01:10,080 --> 00:01:10,760
Baiklah.

22
00:01:10,760 --> 00:01:13,190
>> Jadi mari kita lihat beban.

23
00:01:13,190 --> 00:01:16,390
Jadi notis beban itu,
ia mengembalikan bool a.

24
00:01:16,390 --> 00:01:20,530
Anda kembali benar jika ia berjaya
dimuatkan dan palsu sebaliknya.

25
00:01:20,530 --> 00:01:23,990
Dan ia mengambil char malar * bintang
kamus, yang kamus

26
00:01:23,990 --> 00:01:25,280
yang kita mahu buka.

27
00:01:25,280 --> 00:01:27,170
Jadi itu perkara pertama
kita akan lakukan.

28
00:01:27,170 --> 00:01:30,420
Kami akan fopen kamus untuk
membaca, dan kita akan mempunyai

29
00:01:30,420 --> 00:01:34,700
memastikan bahawa ia berjaya jadi jika
ia kembali NULL, maka kita tidak

30
00:01:34,700 --> 00:01:37,440
berjaya membuka kamus
dan kita perlu kembali palsu.

31
00:01:37,440 --> 00:01:41,580
>> Tetapi menganggap bahawa ia tidak berjaya
terbuka, maka kita mahu membaca

32
00:01:41,580 --> 00:01:42,400
kamus.

33
00:01:42,400 --> 00:01:46,210
Jadi menyimpan menggelung sehingga kita menemui beberapa
sebab untuk keluar daripada ini

34
00:01:46,210 --> 00:01:47,570
gelung yang kita akan melihat.

35
00:01:47,570 --> 00:01:51,780
Jadi menjaga gelung, dan kini kita akan
untuk malloc nod tunggal.

36
00:01:51,780 --> 00:01:56,800
Dan sudah tentu, kita perlu kesilapan cek
lagi jadi jika mallocing tidak berjaya

37
00:01:56,800 --> 00:02:00,660
dan kami mahu memunggah mana-mana nod yang kita
berlaku kepada malloc sebelum, tutup

38
00:02:00,660 --> 00:02:02,590
kamus dan pulangan palsu.

39
00:02:02,590 --> 00:02:07,440
>> Tetapi mengabaikan itu, kami menganggap
berjaya, maka kita mahu menggunakan fscanf

40
00:02:07,440 --> 00:02:12,400
untuk membaca satu perkataan pun dari kami
kamus ke dalam nod kami.

41
00:02:12,400 --> 00:02:17,310
Jadi ingat bahawa perkataan kemasukan> adalah char
penampan perkataan panjang saiz campur

42
00:02:17,310 --> 00:02:20,300
satu yang kita akan
menyimpan perkataan masuk

43
00:02:20,300 --> 00:02:25,280
Jadi fscanf akan kembali 1 selagi
kerana ia mampu berjaya membaca

44
00:02:25,280 --> 00:02:26,750
perkataan dari fail.

45
00:02:26,750 --> 00:02:31,030
>> Jika sama ada kesilapan yang berlaku atau kita mencapai
akhir fail tersebut, ia tidak akan

46
00:02:31,030 --> 00:02:34,950
kembali 1 di mana jika ia tidak
kembali 1, kita akhirnya akan menghancurkan

47
00:02:34,950 --> 00:02:37,280
daripada gelung selama ini.

48
00:02:37,280 --> 00:02:42,770
Jadi kita lihat bahawa sebaik sahaja kami telah berjaya
membaca perkataan ke dalam

49
00:02:42,770 --> 00:02:48,270
kemasukan> perkataan, maka kita akan hash
bahawa perkataan menggunakan fungsi hash kami.

50
00:02:48,270 --> 00:02:49,580
Mari kita lihat
fungsi hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Jadi anda tidak benar-benar memerlukan
untuk memahami perkara ini.

53
00:02:55,610 --> 00:02:59,460
Dan sebenarnya, kita hanya ditarik ini
hash fungsi dari internet.

54
00:02:59,460 --> 00:03:04,010
Satu-satunya perkara yang anda perlu menyedari adalah
bahawa ini mengambil char malar * perkataan,

55
00:03:04,010 --> 00:03:08,960
jadi ia mengambil rentetan sebagai input dan
kembali satu int tidak ditandatangani sebagai output.

56
00:03:08,960 --> 00:03:12,360
Jadi itu sahaja fungsi hash adalah, adakah ia
mengambil masa dalam input, ia memberi anda

57
00:03:12,360 --> 00:03:14,490
indeks ke dalam jadual hash.

58
00:03:14,490 --> 00:03:18,530
Perhatikan bahawa kita modding oleh NUM_BUCKETS
maka nilai hash kembali

59
00:03:18,530 --> 00:03:21,730
sebenarnya ialah indeks ke dalam jadual hash
dan tidak indeks di luar

60
00:03:21,730 --> 00:03:24,320
batas array.

61
00:03:24,320 --> 00:03:27,855
>> Jadi memandangkan fungsi hash, kita akan
untuk hash perkataan yang kita baca

62
00:03:27,855 --> 00:03:31,700
daripada kamus dan kemudian kita akan
untuk menggunakan yang mempunyai untuk memasukkan

63
00:03:31,700 --> 00:03:33,750
masuk ke dalam jadual hash.

64
00:03:33,750 --> 00:03:38,830
Sekarang, hash hashtable adalah semasa
senarai dikaitkan dalam jadual hash, dan

65
00:03:38,830 --> 00:03:41,410
ia sangat mungkin yang hanya NULL.

66
00:03:41,410 --> 00:03:45,640
Kami mahu memasukkan kemasukan kami di
permulaan senarai ini dikaitkan, dan sebagainya

67
00:03:45,640 --> 00:03:48,910
kita akan mempunyai kemasukan semasa kami
menunjukkan apa jadual hash kini

68
00:03:48,910 --> 00:03:54,030
mata kepada dan kemudian kita akan menyimpan
dalam jadual hash di hash

69
00:03:54,030 --> 00:03:55,350
kemasukan semasa.

70
00:03:55,350 --> 00:03:59,320
>> Jadi kedua-dua baris berjaya memasukkan
penyertaan di permulaan

71
00:03:59,320 --> 00:04:02,270
senarai bersambung pada indeks yang
dalam jadual hash.

72
00:04:02,270 --> 00:04:04,900
Setelah kami selesai dengan itu, kita tahu
yang kami dapati perkataan lain dalam

73
00:04:04,900 --> 00:04:07,800
kamus dan kita kenaikan lagi.

74
00:04:07,800 --> 00:04:13,960
Oleh itu, kita terus melakukan sehingga fscanf
akhirnya kembali sesuatu bukan 1 pada

75
00:04:13,960 --> 00:04:18,560
mana titik ingat bahawa kita perlu
masuk percuma, jadi di sini, kami malloced satu

76
00:04:18,560 --> 00:04:21,329
kemasukan dan kami cuba untuk membaca sesuatu
daripada kamus.

77
00:04:21,329 --> 00:04:24,110
Dan kita tidak berjaya membaca
sesuatu dari kamus di mana

78
00:04:24,110 --> 00:04:27,440
kes kita perlu untuk membebaskan kemasukan yang kita
sebenarnya tidak pernah dimasukkan ke dalam jadual hash

79
00:04:27,440 --> 00:04:29,110
dan akhirnya pecah.

80
00:04:29,110 --> 00:04:32,750
>> Apabila kita keluar, kita perlu melihat, baik,
yang kita keluar kerana ada

81
00:04:32,750 --> 00:04:35,840
telah kesilapan membaca dari fail, atau
yang kita keluar kerana kita mencapai

82
00:04:35,840 --> 00:04:37,120
akhir fail?

83
00:04:37,120 --> 00:04:40,150
Jika ada kesilapan, kita mahu
pulangan palsu kerana beban tidak

84
00:04:40,150 --> 00:04:43,260
berjaya, dan dalam proses itu, kami mahu
memunggah semua perkataan yang kita baca

85
00:04:43,260 --> 00:04:45,670
di dalam dan menutup fail kamus.

86
00:04:45,670 --> 00:04:48,740
Andai kata kita tidak berjaya, maka kita hanya
masih perlu menutup kamus

87
00:04:48,740 --> 00:04:51,970
fail, dan akhirnya kembali benar kerana
kita telah berjaya dimuatkan

88
00:04:51,970 --> 00:04:53,040
kamus.

89
00:04:53,040 --> 00:04:54,420
Dan itu sahaja untuk beban.

90
00:04:54,420 --> 00:04:59,020
>> Jadi sekarang cek, diberikan jadual hash dimuatkan,
akan kelihatan seperti ini.

91
00:04:59,020 --> 00:05:02,690
Jadi lihat, ia kembali bool, yang
akan menunjukkan sama ada

92
00:05:02,690 --> 00:05:07,530
diluluskan dalam char * perkataan, sama ada
berlalu-dalam rentetan di dalam kamus kami.

93
00:05:07,530 --> 00:05:10,530
Jadi, jika ia ada di dalam kamus, jika ia
dalam jadual hash kami, kami akan kembali

94
00:05:10,530 --> 00:05:13,380
benar, dan jika tidak,
kita akan kembali palsu.

95
00:05:13,380 --> 00:05:17,770
Memandangkan perkataan ini diluluskan-masuk, kita akan
akan hash perkataan.

96
00:05:17,770 --> 00:05:22,020
>> Sekarang, satu perkara yang penting untuk menyedari adalah
bahawa dalam beban, kita tahu bahawa semua

97
00:05:22,020 --> 00:05:25,820
kata-kata itu akan menjadi huruf kecil,
tetapi di sini, kita tidak begitu pasti.

98
00:05:25,820 --> 00:05:29,510
Jika kita lihat fungsi hash kami,
fungsi hash kita sebenarnya

99
00:05:29,510 --> 00:05:32,700
adalah lowercasing setiap aksara
perkataan.

100
00:05:32,700 --> 00:05:37,580
Jadi, tanpa mengira permodalan
perkataan, fungsi hash kita akan

101
00:05:37,580 --> 00:05:42,270
kembali indeks yang sama untuk apa jua
permodalan adalah kerana ia akan

102
00:05:42,270 --> 00:05:45,280
kembali untuk yang sama sekali huruf kecil
versi perkataan.

103
00:05:45,280 --> 00:05:45,950
Baiklah.

104
00:05:45,950 --> 00:05:47,410
>> Jadi, itu indeks kami.

105
00:05:47,410 --> 00:05:49,790
Ia jadual hash untuk perkataan ini.

106
00:05:49,790 --> 00:05:52,940
Sekarang, ini untuk gelung akan
kepada lebih senarai dikaitkan

107
00:05:52,940 --> 00:05:55,000
yang pada indeks itu.

108
00:05:55,000 --> 00:05:59,630
Jadi notis kita Memulakan masuk
untuk menunjukkan kepada indeks itu.

109
00:05:59,630 --> 00:06:03,480
Kami akan diteruskan manakala kemasukan tidak
tidak NULL sama, dan ingat bahawa

110
00:06:03,480 --> 00:06:08,350
mengemaskini penuding dalam senarai dikaitkan kami
kemasukan sama kemasukan> depan, begitu juga

111
00:06:08,350 --> 00:06:13,840
pintu masuk semasa kami kepada
Perkara seterusnya dalam senarai berkaitan.

112
00:06:13,840 --> 00:06:14,400
Baiklah.

113
00:06:14,400 --> 00:06:19,150
>> Jadi bagi setiap penyertaan dalam senarai yang dihubungkan,
kita akan menggunakan strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Ia tidak strcmp kerana sekali lagi, kita
mahu melakukan perkara-perkara kes insensitively.

115
00:06:23,780 --> 00:06:28,830
Oleh itu, kita menggunakan strcasecmp untuk membandingkan perkataan
yang telah diluluskan untuk fungsi ini

116
00:06:28,830 --> 00:06:31,860
terhadap perkataan yang
dalam entri ini.

117
00:06:31,860 --> 00:06:35,570
Jika ia kembali 0, ini bermakna terdapat
perlawanan, di mana kita mahu

118
00:06:35,570 --> 00:06:36,630
kembali benar.

119
00:06:36,630 --> 00:06:39,590
Kami berjaya menemui
perkataan dalam jadual hash kami.

120
00:06:39,590 --> 00:06:43,040
>> Jika tidak ada perlawanan, maka kami
akan gelung lagi dan melihat

121
00:06:43,040 --> 00:06:43,990
kemasukan yang berikutnya.

122
00:06:43,990 --> 00:06:47,640
Dan kami akan terus gelung sementara ada
entri di senarai ini dikaitkan.

123
00:06:47,640 --> 00:06:50,160
Apakah yang akan berlaku jika kita memecahkan
daripada ini untuk gelung?

124
00:06:50,160 --> 00:06:55,110
Ini bermakna kita tidak mencari penyertaan yang
dipadankan perkataan ini, di mana

125
00:06:55,110 --> 00:07:00,220
kita kembali palsu untuk menunjukkan bahawa kami
jadual hash tidak mengandungi perkataan ini.

126
00:07:00,220 --> 00:07:01,910
Dan itu sahaja untuk cek.

127
00:07:01,910 --> 00:07:02,540
Baiklah.

128
00:07:02,540 --> 00:07:04,790
>> Jadi mari kita lihat pada saiz.

129
00:07:04,790 --> 00:07:09,280
Sekarang, saiz akan menjadi agak mudah
sejak ingat dalam beban bagi setiap perkataan

130
00:07:09,280 --> 00:07:12,880
kami mendapati kami incremented global
hashtable_size berubah-ubah.

131
00:07:12,880 --> 00:07:15,830
Jadi fungsi saiz hanya
akan kembali yang global

132
00:07:15,830 --> 00:07:18,150
berubah-ubah, dan itu sahaja.

133
00:07:18,150 --> 00:07:22,300
>> Kini akhirnya, kita perlu memunggah
kamus sekali semuanya dilakukan.

134
00:07:22,300 --> 00:07:25,340
Jadi bagaimana kita boleh berbuat demikian?

135
00:07:25,340 --> 00:07:30,440
Di sini, kami menggelung ke atas semua
baldi jadual hash kami.

136
00:07:30,440 --> 00:07:33,240
Jadi, terdapat NUM_BUCKETS baldi.

137
00:07:33,240 --> 00:07:37,490
Dan bagi setiap senarai dikaitkan dalam hash kami
meja, kita akan gelung ke atas

138
00:07:37,490 --> 00:07:41,070
keseluruhan senarai dikaitkan
membebaskan setiap elemen.

139
00:07:41,070 --> 00:07:46,070
Sekarang, kita perlu berhati-hati, jadi di sini kita
mempunyai pembolehubah sementara itu

140
00:07:46,070 --> 00:07:49,740
menyimpan penunjuk ke depan
elemen dalam senarai berkaitan.

141
00:07:49,740 --> 00:07:52,140
Dan kemudian kita akan bebas
elemen semasa.

142
00:07:52,140 --> 00:07:55,990
>> Kita perlu pastikan kita melakukan ini kerana kita
tidak boleh hanya membebaskan elemen semasa

143
00:07:55,990 --> 00:07:59,260
dan kemudian cuba untuk mengakses penunjuk seterusnya
sejak sebaik sahaja kami dibebaskan ia

144
00:07:59,260 --> 00:08:00,870
memori menjadi tidak sah.

145
00:08:00,870 --> 00:08:04,990
Oleh itu, kita perlu menjaga seluruh penunjuk kepada
elemen yang akan datang, maka kita boleh membebaskan

146
00:08:04,990 --> 00:08:08,360
elemen semasa, dan kemudian kita boleh mengemas kini
elemen semasa kami untuk menunjukkan

147
00:08:08,360 --> 00:08:09,590
elemen seterusnya.

148
00:08:09,590 --> 00:08:12,770
>> Kami akan gelung manakala terdapat unsur-unsur
dalam senarai ini dikaitkan.

149
00:08:12,770 --> 00:08:16,450
Kami akan melakukannya untuk semua senarai dikaitkan dalam
jadual hash, dan sebaik sahaja kami selesai

150
00:08:16,450 --> 00:08:20,180
dengan itu, kami telah dipunggah sepenuhnya
jadual hash, dan kami selesai.

151
00:08:20,180 --> 00:08:24,050
Jadi ia adalah mustahil untuk dipunggah yang pernah
pulangan palsu, dan apabila kita selesai, kita

152
00:08:24,050 --> 00:08:25,320
hanya kembali benar.

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