>> ROB Bowden: Hi.
Saya Rob, dan hash yang disewakan ini penyelesaian ini keluar.
Jadi di sini kita akan melaksanakan jadual hash umum.
Kita lihat bahawa nod struct daripada hash kami jadual akan kelihatan seperti ini.
Jadi ia akan mempunyai perkataan char pelbagai panjang saiz campur 1.
Jangan lupa 1 sejak maksimum perkataan dalam kamus ialah 45
watak-watak, dan kemudian kita akan memerlukan satu watak tambahan untuk
garis sendeng terbalik 0.
>> Dan kemudian jadual hash kita dalam setiap baldi akan menyimpan
senarai bersambung nod.
Kami tidak melakukan linear menyelesaikan sesuatu di sini.
Dan sebagainya untuk pautan ke seterusnya elemen dalam baldi, kita memerlukan
nod struct * seterusnya.
Jadi itulah yang nod kelihatan seperti.
Sekarang, di sini adalah pengakuan yang jadual hash kami.
Ia akan mempunyai 16,384 baldi, tetapi jumlah itu tidak benar-benar perkara itu.
Dan akhirnya, kita akan mempunyai hashtable_size pembolehubah global, yang
akan bermula sebagai 0, dan ia akan mengesan berapa banyak perkataan
berada dalam kamus kami.
Baiklah.
>> Jadi mari kita lihat beban.
Jadi notis beban itu, ia mengembalikan bool a.
Anda kembali benar jika ia berjaya dimuatkan dan palsu sebaliknya.
Dan ia mengambil char malar * bintang kamus, yang kamus
yang kita mahu buka.
Jadi itu perkara pertama kita akan lakukan.
Kami akan fopen kamus untuk membaca, dan kita akan mempunyai
memastikan bahawa ia berjaya jadi jika ia kembali NULL, maka kita tidak
berjaya membuka kamus dan kita perlu kembali palsu.
>> Tetapi menganggap bahawa ia tidak berjaya terbuka, maka kita mahu membaca
kamus.
Jadi menyimpan menggelung sehingga kita menemui beberapa sebab untuk keluar daripada ini
gelung yang kita akan melihat.
Jadi menjaga gelung, dan kini kita akan untuk malloc nod tunggal.
Dan sudah tentu, kita perlu kesilapan cek lagi jadi jika mallocing tidak berjaya
dan kami mahu memunggah mana-mana nod yang kita berlaku kepada malloc sebelum, tutup
kamus dan pulangan palsu.
>> Tetapi mengabaikan itu, kami menganggap berjaya, maka kita mahu menggunakan fscanf
untuk membaca satu perkataan pun dari kami kamus ke dalam nod kami.
Jadi ingat bahawa perkataan kemasukan> adalah char penampan perkataan panjang saiz campur
satu yang kita akan menyimpan perkataan masuk
Jadi fscanf akan kembali 1 selagi kerana ia mampu berjaya membaca
perkataan dari fail.
>> Jika sama ada kesilapan yang berlaku atau kita mencapai akhir fail tersebut, ia tidak akan
kembali 1 di mana jika ia tidak kembali 1, kita akhirnya akan menghancurkan
daripada gelung selama ini.
Jadi kita lihat bahawa sebaik sahaja kami telah berjaya membaca perkataan ke dalam
kemasukan> perkataan, maka kita akan hash bahawa perkataan menggunakan fungsi hash kami.
Mari kita lihat fungsi hash.
>> Jadi anda tidak benar-benar memerlukan untuk memahami perkara ini.
Dan sebenarnya, kita hanya ditarik ini hash fungsi dari internet.
Satu-satunya perkara yang anda perlu menyedari adalah bahawa ini mengambil char malar * perkataan,
jadi ia mengambil rentetan sebagai input dan kembali satu int tidak ditandatangani sebagai output.
Jadi itu sahaja fungsi hash adalah, adakah ia mengambil masa dalam input, ia memberi anda
indeks ke dalam jadual hash.
Perhatikan bahawa kita modding oleh NUM_BUCKETS maka nilai hash kembali
sebenarnya ialah indeks ke dalam jadual hash dan tidak indeks di luar
batas array.
>> Jadi memandangkan fungsi hash, kita akan untuk hash perkataan yang kita baca
daripada kamus dan kemudian kita akan untuk menggunakan yang mempunyai untuk memasukkan
masuk ke dalam jadual hash.
Sekarang, hash hashtable adalah semasa senarai dikaitkan dalam jadual hash, dan
ia sangat mungkin yang hanya NULL.
Kami mahu memasukkan kemasukan kami di permulaan senarai ini dikaitkan, dan sebagainya
kita akan mempunyai kemasukan semasa kami menunjukkan apa jadual hash kini
mata kepada dan kemudian kita akan menyimpan dalam jadual hash di hash
kemasukan semasa.
>> Jadi kedua-dua baris berjaya memasukkan penyertaan di permulaan
senarai bersambung pada indeks yang dalam jadual hash.
Setelah kami selesai dengan itu, kita tahu yang kami dapati perkataan lain dalam
kamus dan kita kenaikan lagi.
Oleh itu, kita terus melakukan sehingga fscanf akhirnya kembali sesuatu bukan 1 pada
mana titik ingat bahawa kita perlu masuk percuma, jadi di sini, kami malloced satu
kemasukan dan kami cuba untuk membaca sesuatu daripada kamus.
Dan kita tidak berjaya membaca sesuatu dari kamus di mana
kes kita perlu untuk membebaskan kemasukan yang kita sebenarnya tidak pernah dimasukkan ke dalam jadual hash
dan akhirnya pecah.
>> Apabila kita keluar, kita perlu melihat, baik, yang kita keluar kerana ada
telah kesilapan membaca dari fail, atau yang kita keluar kerana kita mencapai
akhir fail?
Jika ada kesilapan, kita mahu pulangan palsu kerana beban tidak
berjaya, dan dalam proses itu, kami mahu memunggah semua perkataan yang kita baca
di dalam dan menutup fail kamus.
Andai kata kita tidak berjaya, maka kita hanya masih perlu menutup kamus
fail, dan akhirnya kembali benar kerana kita telah berjaya dimuatkan
kamus.
Dan itu sahaja untuk beban.
>> Jadi sekarang cek, diberikan jadual hash dimuatkan, akan kelihatan seperti ini.
Jadi lihat, ia kembali bool, yang akan menunjukkan sama ada
diluluskan dalam char * perkataan, sama ada berlalu-dalam rentetan di dalam kamus kami.
Jadi, jika ia ada di dalam kamus, jika ia dalam jadual hash kami, kami akan kembali
benar, dan jika tidak, kita akan kembali palsu.
Memandangkan perkataan ini diluluskan-masuk, kita akan akan hash perkataan.
>> Sekarang, satu perkara yang penting untuk menyedari adalah bahawa dalam beban, kita tahu bahawa semua
kata-kata itu akan menjadi huruf kecil, tetapi di sini, kita tidak begitu pasti.
Jika kita lihat fungsi hash kami, fungsi hash kita sebenarnya
adalah lowercasing setiap aksara perkataan.
Jadi, tanpa mengira permodalan perkataan, fungsi hash kita akan
kembali indeks yang sama untuk apa jua permodalan adalah kerana ia akan
kembali untuk yang sama sekali huruf kecil versi perkataan.
Baiklah.
>> Jadi, itu indeks kami.
Ia jadual hash untuk perkataan ini.
Sekarang, ini untuk gelung akan kepada lebih senarai dikaitkan
yang pada indeks itu.
Jadi notis kita Memulakan masuk untuk menunjukkan kepada indeks itu.
Kami akan diteruskan manakala kemasukan tidak tidak NULL sama, dan ingat bahawa
mengemaskini penuding dalam senarai dikaitkan kami kemasukan sama kemasukan> depan, begitu juga
pintu masuk semasa kami kepada Perkara seterusnya dalam senarai berkaitan.
Baiklah.
>> Jadi bagi setiap penyertaan dalam senarai yang dihubungkan, kita akan menggunakan strcasecmp.
Ia tidak strcmp kerana sekali lagi, kita mahu melakukan perkara-perkara kes insensitively.
Oleh itu, kita menggunakan strcasecmp untuk membandingkan perkataan yang telah diluluskan untuk fungsi ini
terhadap perkataan yang dalam entri ini.
Jika ia kembali 0, ini bermakna terdapat perlawanan, di mana kita mahu
kembali benar.
Kami berjaya menemui perkataan dalam jadual hash kami.
>> Jika tidak ada perlawanan, maka kami akan gelung lagi dan melihat
kemasukan yang berikutnya.
Dan kami akan terus gelung sementara ada entri di senarai ini dikaitkan.
Apakah yang akan berlaku jika kita memecahkan daripada ini untuk gelung?
Ini bermakna kita tidak mencari penyertaan yang dipadankan perkataan ini, di mana
kita kembali palsu untuk menunjukkan bahawa kami jadual hash tidak mengandungi perkataan ini.
Dan itu sahaja untuk cek.
Baiklah.
>> Jadi mari kita lihat pada saiz.
Sekarang, saiz akan menjadi agak mudah sejak ingat dalam beban bagi setiap perkataan
kami mendapati kami incremented global hashtable_size berubah-ubah.
Jadi fungsi saiz hanya akan kembali yang global
berubah-ubah, dan itu sahaja.
>> Kini akhirnya, kita perlu memunggah kamus sekali semuanya dilakukan.
Jadi bagaimana kita boleh berbuat demikian?
Di sini, kami menggelung ke atas semua baldi jadual hash kami.
Jadi, terdapat NUM_BUCKETS baldi.
Dan bagi setiap senarai dikaitkan dalam hash kami meja, kita akan gelung ke atas
keseluruhan senarai dikaitkan membebaskan setiap elemen.
Sekarang, kita perlu berhati-hati, jadi di sini kita mempunyai pembolehubah sementara itu
menyimpan penunjuk ke depan elemen dalam senarai berkaitan.
Dan kemudian kita akan bebas elemen semasa.
>> Kita perlu pastikan kita melakukan ini kerana kita tidak boleh hanya membebaskan elemen semasa
dan kemudian cuba untuk mengakses penunjuk seterusnya sejak sebaik sahaja kami dibebaskan ia
memori menjadi tidak sah.
Oleh itu, kita perlu menjaga seluruh penunjuk kepada elemen yang akan datang, maka kita boleh membebaskan
elemen semasa, dan kemudian kita boleh mengemas kini elemen semasa kami untuk menunjukkan
elemen seterusnya.
>> Kami akan gelung manakala terdapat unsur-unsur dalam senarai ini dikaitkan.
Kami akan melakukannya untuk semua senarai dikaitkan dalam jadual hash, dan sebaik sahaja kami selesai
dengan itu, kami telah dipunggah sepenuhnya jadual hash, dan kami selesai.
Jadi ia adalah mustahil untuk dipunggah yang pernah pulangan palsu, dan apabila kita selesai, kita
hanya kembali benar.