>> 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.