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
Aku Rob, dan hash mari kita
solusi ini.

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

5
00:00:20,070 --> 00:00:24,090
Kita melihat bahwa struct node hash kami
tabel akan terlihat seperti ini.

6
00:00:24,090 --> 00:00:28,710
Jadi itu akan memiliki kata arang
array ukuran panjang ditambah 1.

7
00:00:28,710 --> 00:00:32,259
Jangan lupa 1 sejak maksimal
kata dalam kamus adalah 45

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

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

10
00:00:37,070 --> 00:00:40,870
>> Dan kemudian tabel hash kami di setiap
ember akan menyimpan

11
00:00:40,870 --> 00:00:42,320
linked list node.

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

13
00:00:44,420 --> 00:00:48,430
Dan dalam rangka untuk menghubungkan ke depan
elemen dalam ember, kita perlu

14
00:00:48,430 --> 00:00:51,110
struct simpul * berikutnya.

15
00:00:51,110 --> 00:00:53,090
Jadi itulah yang simpul yang tampak seperti.

16
00:00:53,090 --> 00:00:56,180
Sekarang, di sini adalah deklarasi
tabel hash kami.

17
00:00:56,180 --> 00:01:01,910
Ini akan memiliki 16.384 ember, tapi
jumlah yang tidak terlalu penting.

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

19
00:01:05,450 --> 00:01:08,640
akan memulai sebagai 0, dan itu
akan melacak berapa banyak kata-kata

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

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

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

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

24
00:01:16,390 --> 00:01:20,530
Anda mengembalikan true jika itu berhasil
dimuat dan false jika tidak.

25
00:01:20,530 --> 00:01:23,990
Dan dibutuhkan const char * star
kamus, yang merupakan kamus

26
00:01:23,990 --> 00:01:25,280
bahwa kita ingin membuka.

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

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

29
00:01:30,420 --> 00:01:34,700
untuk memastikan bahwa itu berhasil jadi jika
itu kembali NULL, maka kita tidak

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

31
00:01:37,440 --> 00:01:41,580
>> Tetapi dengan asumsi bahwa hal itu berhasil
terbuka, maka kita ingin membaca

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

33
00:01:42,400 --> 00:01:46,210
Jadi terus looping sampai kita menemukan beberapa
alasan untuk keluar dari ini

34
00:01:46,210 --> 00:01:47,570
lingkaran yang akan kita lihat.

35
00:01:47,570 --> 00:01:51,780
Jadi tetap perulangan, dan sekarang kita akan
untuk malloc node tunggal.

36
00:01:51,780 --> 00:01:56,800
Dan tentu saja, kita perlu cek kesalahan
lagi jadi jika mallocing tidak berhasil

37
00:01:56,800 --> 00:02:00,660
dan kami ingin membongkar setiap node yang kita
terjadi pada malloc sebelumnya, tutup

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

39
00:02:02,590 --> 00:02:07,440
>> Tetapi mengabaikan itu, dengan asumsi kita
berhasil, maka kita ingin menggunakan fscanf

40
00:02:07,440 --> 00:02:12,400
untuk membaca satu kata dari kami
kamus ke simpul kami.

41
00:02:12,400 --> 00:02:17,310
Jadi ingat bahwa entry-> kata adalah char
penyangga kata panjang plus ukuran

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

43
00:02:20,300 --> 00:02:25,280
Jadi fscanf akan kembali selama 1
seperti itu berhasil membaca

44
00:02:25,280 --> 00:02:26,750
kata dari file tersebut.

45
00:02:26,750 --> 00:02:31,030
>> Jika terjadi kesalahan yang terjadi atau kita mencapai
akhir file tersebut, ia tidak akan

46
00:02:31,030 --> 00:02:34,950
kembali 1 dalam hal jika tidak
kembali 1, kita akhirnya akan memecah

47
00:02:34,950 --> 00:02:37,280
dari while loop ini.

48
00:02:37,280 --> 00:02:42,770
Jadi kita melihat bahwa sekali kita telah berhasil
membaca sebuah kata ke dalam

49
00:02:42,770 --> 00:02:48,270
entry-> kata, maka kita akan hash
kata 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 perlu
untuk memahami ini.

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

54
00:02:59,460 --> 00:03:04,010
Satu-satunya hal yang perlu Anda mengenali adalah
bahwa ini mengambil char * const kata,

55
00:03:04,010 --> 00:03:08,960
jadi itu mengambil string sebagai masukan dan
kembali sebuah int unsigned sebagai output.

56
00:03:08,960 --> 00:03:12,360
Jadi itu semua fungsi hash adalah, apakah
mengambil dalam input, memberikan Anda

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

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

59
00:03:18,530 --> 00:03:21,730
sebenarnya adalah indeks ke tabel hash
dan tidak indeks luar

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

61
00:03:24,320 --> 00:03:27,855
>> Jadi mengingat bahwa fungsi hash, kita akan
hash kata yang kita baca

62
00:03:27,855 --> 00:03:31,700
dari kamus dan kemudian kita akan
untuk menggunakan harus memasukkan

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

64
00:03:33,750 --> 00:03:38,830
Sekarang, hash hashtable adalah arus
linked list dalam tabel hash, dan

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

66
00:03:41,410 --> 00:03:45,640
Kami ingin memasukkan entri kami di
awal linked list ini, dan sebagainya

67
00:03:45,640 --> 00:03:48,910
kita akan memiliki entri kami saat ini
menunjukkan apa tabel hash saat ini

68
00:03:48,910 --> 00:03:54,030
poin dan kemudian kita akan menyimpan
dalam tabel hash di hash

69
00:03:54,030 --> 00:03:55,350
entry ini.

70
00:03:55,350 --> 00:03:59,320
>> Jadi dua baris ini berhasil memasukkan
entri pada awal

71
00:03:59,320 --> 00:04:02,270
linked list pada indeks yang
dalam tabel hash.

72
00:04:02,270 --> 00:04:04,900
Setelah kami selesai dengan itu, kita tahu
bahwa kita menemukan kata lain dalam

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

74
00:04:07,800 --> 00:04:13,960
Jadi kita terus melakukan itu sampai fscanf
akhirnya kembali sesuatu non 1 di

75
00:04:13,960 --> 00:04:18,560
mana titik ingat bahwa kita perlu
masuk gratis, jadi di sini, kami malloced an

76
00:04:18,560 --> 00:04:21,329
masuk dan kami mencoba untuk membaca sesuatu
dari kamus.

77
00:04:21,329 --> 00:04:24,110
Dan kami tidak berhasil membaca
sesuatu dari kamus yang

78
00:04:24,110 --> 00:04:27,440
kasus kita perlu membebaskan entri yang kita
pernah benar-benar dimasukkan ke dalam tabel hash

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

80
00:04:29,110 --> 00:04:32,750
>> Setelah kami keluar, kita perlu melihat, baik,
Apakah kita keluar karena ada

81
00:04:32,750 --> 00:04:35,840
adalah kesalahan membaca dari file, atau
Apakah kita keluar karena kita mencapai

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

83
00:04:37,120 --> 00:04:40,150
Jika ada kesalahan, maka kita ingin
kembali palsu karena beban tidak

84
00:04:40,150 --> 00:04:43,260
berhasil, dan dalam proses tersebut, kami ingin
membongkar semua kata-kata yang kita baca

85
00:04:43,260 --> 00:04:45,670
dan menutup file kamus.

86
00:04:45,670 --> 00:04:48,740
Dengan asumsi kita tidak berhasil, maka kita hanya
masih perlu menutup kamus

87
00:04:48,740 --> 00:04:51,970
mengajukan, dan akhirnya kembali benar karena
kami telah berhasil dimuat

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

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

90
00:04:54,420 --> 00:04:59,020
>> Jadi sekarang memeriksa, diberikan tabel hash dimuat,
akan terlihat seperti ini.

91
00:04:59,020 --> 00:05:02,690
Jadi periksa, ia mengembalikan bool, yang
akan menunjukkan apakah

92
00:05:02,690 --> 00:05:07,530
berlalu-in char * kata, apakah
berlalu-in string dalam kamus kami.

93
00:05:07,530 --> 00:05:10,530
Jadi jika itu di kamus, jika
dalam tabel hash kami, kami akan kembali

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

95
00:05:13,380 --> 00:05:17,770
Mengingat kata berlalu-dalam hal ini, kami
akan hash kata.

96
00:05:17,770 --> 00:05:22,020
>> Sekarang, hal yang penting untuk mengenali adalah
bahwa beban, kita tahu bahwa semua

97
00:05:22,020 --> 00:05:25,820
kata-kata itu akan menjadi huruf kecil,
tapi di sini, kami tidak begitu yakin.

98
00:05:25,820 --> 00:05:29,510
Jika kita melihat pada fungsi hash kami,
Fungsi hash kami benar-benar

99
00:05:29,510 --> 00:05:32,700
adalah lowercasing masing-masing karakter
kata.

100
00:05:32,700 --> 00:05:37,580
Jadi terlepas dari kapitalisasi
kata, fungsi hash kami akan

101
00:05:37,580 --> 00:05:42,270
mengembalikan indeks yang sama untuk apa pun
kapitalisasi adalah karena akan memiliki

102
00:05:42,270 --> 00:05:45,280
kembali untuk benar-benar huruf kecil
versi kata.

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

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

105
00:05:47,410 --> 00:05:49,790
Ini adalah tabel hash untuk kata ini.

106
00:05:49,790 --> 00:05:52,940
Sekarang, ini untuk loop akan
ke lebih dari linked list

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

108
00:05:55,000 --> 00:05:59,630
Jadi perhatikan kita menginisialisasi entri
untuk menunjuk ke indeks.

109
00:05:59,630 --> 00:06:03,480
Kami akan terus masuk sementara tidak
bukan NULL yang sama, dan ingat bahwa

110
00:06:03,480 --> 00:06:08,350
memperbarui pointer dalam linked list kami
entri sama entry-> berikutnya, sehingga memiliki

111
00:06:08,350 --> 00:06:13,840
kami entry point saat ini ke
item berikutnya dalam linked list.

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

113
00:06:14,400 --> 00:06:19,150
>> Jadi untuk setiap entri dalam linked list,
kita akan menggunakan strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Ini tidak strcmp karena sekali lagi, kita
ingin melakukan hal-hal kasus insensitively.

115
00:06:23,780 --> 00:06:28,830
Jadi kita menggunakan strcasecmp untuk membandingkan kata
yang dilewatkan ke fungsi ini

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

117
00:06:31,860 --> 00:06:35,570
Jika kembali 0, yang berarti ada
pertandingan, dalam hal ini kita ingin

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

119
00:06:36,630 --> 00:06:39,590
Kami berhasil menemukan
kata dalam tabel hash kami.

120
00:06:39,590 --> 00:06:43,040
>> Jika tidak ada pertandingan, maka kita
akan loop lagi dan melihat

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

122
00:06:43,990 --> 00:06:47,640
Dan kami akan terus looping sementara ada
entri dalam daftar link ini.

123
00:06:47,640 --> 00:06:50,160
Apa yang terjadi jika kita istirahat
keluar dari ini untuk loop?

124
00:06:50,160 --> 00:06:55,110
Itu berarti kita tidak menemukan entri yang
cocok kata ini, dalam hal ini

125
00:06:55,110 --> 00:07:00,220
kita kembali palsu untuk menunjukkan bahwa kami
tabel hash tidak mengandung kata ini.

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

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

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

129
00:07:04,790 --> 00:07:09,280
Sekarang, ukuran akan menjadi cukup sederhana
sejak ingat beban, untuk setiap kata

130
00:07:09,280 --> 00:07:12,880
kami menemukan kami bertambah global
hashtable_size variabel.

131
00:07:12,880 --> 00:07:15,830
Jadi fungsi ukuran hanya
akan kembali bahwa dunia

132
00:07:15,830 --> 00:07:18,150
variabel, dan hanya itu.

133
00:07:18,150 --> 00:07:22,300
>> Sekarang akhirnya, kita perlu membongkar
kamus setelah semuanya selesai.

134
00:07:22,300 --> 00:07:25,340
Jadi bagaimana yang akan kita melakukan itu?

135
00:07:25,340 --> 00:07:30,440
Di sini, kita perulangan atas semua
ember hash table kami.

136
00:07:30,440 --> 00:07:33,240
Jadi ada NUM_BUCKETS ember.

137
00:07:33,240 --> 00:07:37,490
Dan untuk setiap linked list dalam hash kami
tabel, kita akan loop atas

138
00:07:37,490 --> 00:07:41,070
keseluruhan dari linked list
membebaskan setiap elemen.

139
00:07:41,070 --> 00:07:46,070
Sekarang, kita perlu berhati-hati, jadi di sini kita
memiliki variabel sementara yang

140
00:07:46,070 --> 00:07:49,740
menyimpan pointer ke depan
elemen dalam linked list.

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

142
00:07:52,140 --> 00:07:55,990
>> Kita perlu memastikan bahwa kita melakukan ini karena kita
tidak bisa hanya membebaskan elemen saat ini

143
00:07:55,990 --> 00:07:59,260
dan kemudian mencoba untuk mengakses pointer berikutnya
karena setelah kami dibebaskan itu yang

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

145
00:08:00,870 --> 00:08:04,990
Jadi kita perlu menjaga sekitar pointer ke
elemen berikutnya, maka kita dapat membebaskan

146
00:08:04,990 --> 00:08:08,360
elemen saat ini, dan kemudian kita dapat memperbarui
elemen kami saat ini untuk menunjuk ke

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

148
00:08:09,590 --> 00:08:12,770
>> Kami akan loop sementara ada unsur
dalam linked list ini.

149
00:08:12,770 --> 00:08:16,450
Kami akan melakukannya untuk semua daftar terkait dalam
tabel hash, dan setelah kami selesai

150
00:08:16,450 --> 00:08:20,180
dengan itu, kita sudah benar-benar dibongkar
tabel hash, dan kita sudah selesai.

151
00:08:20,180 --> 00:08:24,050
Jadi tidak mungkin untuk unloads yang pernah
kembali palsu, dan ketika kita sudah selesai, kita

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

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