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.