ROB Bowden: Hi. Aku Rob, dan hash mari kita solusi ini. Jadi di sini kita akan mengimplementasikan tabel hash umum. Kita melihat bahwa struct node hash kami tabel akan terlihat seperti ini. Jadi itu akan memiliki kata arang array ukuran panjang ditambah 1. Jangan lupa 1 sejak maksimal kata dalam kamus adalah 45 karakter, dan kemudian kita akan membutuhkan satu karakter tambahan untuk backslash 0. 

Dan kemudian tabel hash kami di setiap ember akan menyimpan linked list node. Kami tidak melakukan linear menyelidik sini. Dan dalam rangka untuk menghubungkan ke depan elemen dalam ember, kita perlu struct simpul * berikutnya. Jadi itulah yang simpul yang tampak seperti. Sekarang, di sini adalah deklarasi tabel hash kami. Ini akan memiliki 16.384 ember, tapi jumlah yang tidak terlalu penting. Dan akhirnya, kita akan memiliki hashtable_size variabel global, yang akan memulai sebagai 0, dan itu akan melacak berapa banyak kata-kata berada dalam kamus kami. Baik. 

Jadi mari kita lihat pada beban. Jadi melihat beban itu, ia mengembalikan bool. Anda mengembalikan true jika itu berhasil dimuat dan false jika tidak. Dan dibutuhkan const char * star kamus, yang merupakan kamus bahwa kita ingin membuka. Jadi itulah hal pertama kita akan lakukan. Kita akan fopen kamus untuk membaca, dan kita akan memiliki untuk memastikan bahwa itu berhasil jadi jika itu kembali NULL, maka kita tidak berhasil membuka kamus dan kita perlu kembali palsu. 

Tetapi dengan asumsi bahwa hal itu berhasil terbuka, maka kita ingin membaca kamus. Jadi terus looping sampai kita menemukan beberapa alasan untuk keluar dari ini lingkaran yang akan kita lihat. Jadi tetap perulangan, dan sekarang kita akan untuk malloc node tunggal. Dan tentu saja, kita perlu cek kesalahan lagi jadi jika mallocing tidak berhasil dan kami ingin membongkar setiap node yang kita terjadi pada malloc sebelumnya, tutup kamus dan kembali palsu. 

Tetapi mengabaikan itu, dengan asumsi kita berhasil, maka kita ingin menggunakan fscanf untuk membaca satu kata dari kami kamus ke simpul kami. Jadi ingat bahwa entry-> kata adalah char penyangga kata panjang plus ukuran salah satu yang kita akan menyimpan kata masuk Jadi fscanf akan kembali selama 1 seperti itu berhasil membaca kata dari file tersebut. 

Jika terjadi kesalahan yang terjadi atau kita mencapai akhir file tersebut, ia tidak akan kembali 1 dalam hal jika tidak kembali 1, kita akhirnya akan memecah dari while loop ini. Jadi kita melihat bahwa sekali kita telah berhasil membaca sebuah kata ke dalam entry-> kata, maka kita akan hash kata menggunakan fungsi hash kami. Mari kita lihat fungsi hash. 

Jadi Anda tidak benar-benar perlu untuk memahami ini. Dan sebenarnya, kami hanya menarik ini hash fungsi dari internet. Satu-satunya hal yang perlu Anda mengenali adalah bahwa ini mengambil char * const kata, jadi itu mengambil string sebagai masukan dan kembali sebuah int unsigned sebagai output. Jadi itu semua fungsi hash adalah, apakah mengambil dalam input, memberikan Anda indeks ke tabel hash. Perhatikan bahwa kita modding oleh NUM_BUCKETS sehingga nilai hash kembali sebenarnya adalah indeks ke tabel hash dan tidak indeks luar batas-batas array. 

Jadi mengingat bahwa fungsi hash, kita akan hash kata yang kita baca dari kamus dan kemudian kita akan untuk menggunakan harus memasukkan masuk ke dalam tabel hash. Sekarang, hash hashtable adalah arus linked list dalam tabel hash, dan itu sangat mungkin bahwa hanya NULL. Kami ingin memasukkan entri kami di awal linked list ini, dan sebagainya kita akan memiliki entri kami saat ini menunjukkan apa tabel hash saat ini poin dan kemudian kita akan menyimpan dalam tabel hash di hash entry ini. 

Jadi dua baris ini berhasil memasukkan entri pada awal linked list pada indeks yang dalam tabel hash. Setelah kami selesai dengan itu, kita tahu bahwa kita menemukan kata lain dalam kamus dan kami kenaikan lagi. Jadi kita terus melakukan itu sampai fscanf akhirnya kembali sesuatu non 1 di mana titik ingat bahwa kita perlu masuk gratis, jadi di sini, kami malloced an masuk dan kami mencoba untuk membaca sesuatu dari kamus. Dan kami tidak berhasil membaca sesuatu dari kamus yang kasus kita perlu membebaskan entri yang kita pernah benar-benar dimasukkan ke dalam tabel hash dan akhirnya pecah. 

Setelah kami keluar, kita perlu melihat, baik, Apakah kita keluar karena ada adalah kesalahan membaca dari file, atau Apakah kita keluar karena kita mencapai akhir file? Jika ada kesalahan, maka kita ingin kembali palsu karena beban tidak berhasil, dan dalam proses tersebut, kami ingin membongkar semua kata-kata yang kita baca dan menutup file kamus. Dengan asumsi kita tidak berhasil, maka kita hanya masih perlu menutup kamus mengajukan, dan akhirnya kembali benar karena kami telah berhasil dimuat kamus. Dan itu saja untuk beban. 

Jadi sekarang memeriksa, diberikan tabel hash dimuat, akan terlihat seperti ini. Jadi periksa, ia mengembalikan bool, yang akan menunjukkan apakah berlalu-in char * kata, apakah berlalu-in string dalam kamus kami. Jadi jika itu di kamus, jika dalam tabel hash kami, kami akan kembali benar, dan jika tidak, kami akan kembali palsu. Mengingat kata berlalu-dalam hal ini, kami akan hash kata. 

Sekarang, hal yang penting untuk mengenali adalah bahwa beban, kita tahu bahwa semua kata-kata itu akan menjadi huruf kecil, tapi di sini, kami tidak begitu yakin. Jika kita melihat pada fungsi hash kami, Fungsi hash kami benar-benar adalah lowercasing masing-masing karakter kata. Jadi terlepas dari kapitalisasi kata, fungsi hash kami akan mengembalikan indeks yang sama untuk apa pun kapitalisasi adalah karena akan memiliki kembali untuk benar-benar huruf kecil versi kata. Baik. 

Jadi itulah indeks kami. Ini adalah tabel hash untuk kata ini. Sekarang, ini untuk loop akan ke lebih dari linked list yang pada indeks itu. Jadi perhatikan kita menginisialisasi entri untuk menunjuk ke indeks. Kami akan terus masuk sementara tidak bukan NULL yang sama, dan ingat bahwa memperbarui pointer dalam linked list kami entri sama entry-> berikutnya, sehingga memiliki kami entry point saat ini ke item berikutnya dalam linked list. Baik. 

Jadi untuk setiap entri dalam linked list, kita akan menggunakan strcasecmp. Ini tidak strcmp karena sekali lagi, kita ingin melakukan hal-hal kasus insensitively. Jadi kita menggunakan strcasecmp untuk membandingkan kata yang dilewatkan ke fungsi ini terhadap kata yang adalah dalam entri ini. Jika kembali 0, yang berarti ada pertandingan, dalam hal ini kita ingin kembali benar. Kami berhasil menemukan kata dalam tabel hash kami. 

Jika tidak ada pertandingan, maka kita akan loop lagi dan melihat entri berikutnya. Dan kami akan terus looping sementara ada entri dalam daftar link ini. Apa yang terjadi jika kita istirahat keluar dari ini untuk loop? Itu berarti kita tidak menemukan entri yang cocok kata ini, dalam hal ini kita kembali palsu untuk menunjukkan bahwa kami tabel hash tidak mengandung kata ini. Dan itu saja untuk cek. Baik. 

Jadi mari kita lihat ukuran. Sekarang, ukuran akan menjadi cukup sederhana sejak ingat beban, untuk setiap kata kami menemukan kami bertambah global hashtable_size variabel. Jadi fungsi ukuran hanya akan kembali bahwa dunia variabel, dan hanya itu. 

Sekarang akhirnya, kita perlu membongkar kamus setelah semuanya selesai. Jadi bagaimana yang akan kita melakukan itu? Di sini, kita perulangan atas semua ember hash table kami. Jadi ada NUM_BUCKETS ember. Dan untuk setiap linked list dalam hash kami tabel, kita akan loop atas keseluruhan dari linked list membebaskan setiap elemen. Sekarang, kita perlu berhati-hati, jadi di sini kita memiliki variabel sementara yang menyimpan pointer ke depan elemen dalam linked list. Dan kemudian kita akan bebas elemen saat ini. 

Kita perlu memastikan bahwa kita melakukan ini karena kita tidak bisa hanya membebaskan elemen saat ini dan kemudian mencoba untuk mengakses pointer berikutnya karena setelah kami dibebaskan itu yang memori menjadi tidak valid. Jadi kita perlu menjaga sekitar pointer ke elemen berikutnya, maka kita dapat membebaskan elemen saat ini, dan kemudian kita dapat memperbarui elemen kami saat ini untuk menunjuk ke elemen berikutnya. 

Kami akan loop sementara ada unsur dalam linked list ini. Kami akan melakukannya untuk semua daftar terkait dalam tabel hash, dan setelah kami selesai dengan itu, kita sudah benar-benar dibongkar tabel hash, dan kita sudah selesai. Jadi tidak mungkin untuk unloads yang pernah kembali palsu, dan ketika kita sudah selesai, kita hanya kembali benar.