ROB BOWDEN: Привет. Я Роб, і давайте хеш це рішення поза. І ось ми збираємося реалізувати загальний хеш-таблиці. Ми бачимо, що структура вузла нашого хеша таблиця буде виглядати наступним чином. Так що це матиме сЬаг слово Масив розмір довжина плюс 1. Не забувайте, 1, так як максимум слово в словнику 45 символів, а потім ми збираємося потрібен один додатковий символ для зворотний слеш 0. 

А потім наш хеш-таблиці в кожному відро збирається зберігати зв'язаний список вузлів. Ми не робимо лінійну зондування тут. І тому для того, щоб зв'язати до наступного елемент у відро, ми повинні структура вузла * наступний. Так ось що вузол виглядає. Тепер, ось декларація нашої хеш-таблиці. Це матиме 16 384 відер, але це число не має великого значення. І, нарешті, ми збираємося мати глобальна змінна hashtable_size, які збирається почати як 0, і це збирається відстежувати, скільки слів були в нашому словнику. Добре. 

Так що давайте поглянемо на навантаженні. Так помітити, що навантаження, вона повертає логічне значення. Ви повертаєтеся вірно, якщо це було успішно завантажений і в іншому випадку. І це займає константних символ * зірку словник, який є словник що ми хочемо відкрити. Так ось перше, що ми збираємося зробити. Ми збираємося відкрити потік, словник для читання, і ми будемо мати щоб переконатися, що це вдалося, так що якщо він повернувся NULL, то ми не зробили успішно відкрити словник і ми повинні повернутися помилковим. 

Але якщо припустити, що це було успішно відкрито, то ми хочемо, щоб прочитати словник. Так що тримайте цикл, поки не знайдемо деякі Причина, щоб вирватися з цього цикл, який ми будемо бачити. Так що тримайте циклу, і тепер ми збираємося щоб Malloc один вузол. І, звичайно, ми повинні про помилки веб- знову, так що якщо mallocing не вдалося і ми хочемо, щоб розвантажити будь-який вузол, який ми трапилося з Танос раніше, закрити словник і повернутися помилковим. 

Але ігноруючи, що, припускаючи, що ми вдалося, то ми хочемо використовувати fscanf читати жодного слова з нашого словник в нашу вузла. Так що пам'ятайте, що вступ-> слово є символ слово буфера довжини плюс розмір той, який ми збираємося зберігати слово дюйма Так fscanf збирається повернутися 1 доти, , Як це було в змозі успішно читати слово з файлу. 

Якщо один відбувається помилка або ми досягнемо кінець файлу, він не буде повертає 1 в цьому випадку, якщо він не повертає 1, ми, нарешті, збирається зламати з цього час циклу. Отже, ми бачимо, що як тільки у нас є успішно читати слово в запис-> слово, те, що ми збираємося, щоб прояснити це слово за допомогою нашого хеш-функцію. Давайте поглянемо на хеш-функція. 

Таким чином, ви дійсно не потрібно щоб зрозуміти це. А насправді, ми просто витягнув цей хеш-функція з Інтернету. Єдине, що ви повинні визнати це що це займає константних символ * слово, так це займає рядок у якості вхідних даних і повернення без знака Int як вихід. Так що все хеш-функція, це приймає в якості внеску, це дає вам індекс у хеш-таблиці. Зверніть увагу, що ми моддінг по NUM_BUCKETS так що значення хеш повертається насправді є індексом в хеш-таблиці і не індексує за Межі масиву. 

Тому, враховуючи, що хеш-функція, ми збираємося щоб прояснити слово, що ми читаємо зі словника, а потім ми збираємося у використанні, що має для вставки вступ до хеш-таблиці. Тепер, хеш-таблиця хеш поточний зв'язаний список в хеш-таблиці, і це дуже можливо, що це просто NULL. Ми хочемо, щоб вставити нашу запис в на початку цього зв'язаного списку, і так ми збираємося, щоб мати нашу поточну запис вказують на те, що хеш-таблиці в даний час вказує на, а потім ми збираємося зберігати в хеш-таблиці на хеш поточна запис. 

Таким чином, ці дві лінії успішно вставити вступ на початку Зв'язаний список за цим індексом в хеш-таблиці. Після того, як ми закінчимо з цим, ми знаємо, що ми знайшли ще одне слово в словник і ми збільшуємо знову. Таким чином, ми продовжувати робити це до fscanf нарешті, повертається щось без 1 на чого пам'ятайте, що нам потрібно вільний вхід, тому тут ми malloced запис і ми спробували прочитати щось зі словника. І ми не успішно прочитані щось зі словника, в якому коли ми повинні звільнити запис, ми ніколи не поміщається в хеш-таблиці і, нарешті, зламати. 

Як тільки ми вирватися, ми повинні бачити, ну, ж ми вирватися, тому що Сталася помилка читання з файлу, або ж ми вирватися, тому що ми досягли кінець файлу? Якщо сталася помилка, то ми хочемо повернутися помилковим, тому що навантаження не зробив домогтися успіху, і в цьому процесі, ми хочемо вивантажити всі слова, які ми читаємо в і закрити файл словника. Припустимо, що ми досягли успіху, то ми просто ще потрібно закрити словник файл, і, нарешті, повернутися вірно, так як ми успішно завантажений словник. І це все на вантаж. 

Так що тепер перевірити, враховуючи завантажений хеш-таблиці, буде виглядати наступним чином. Тому перевірити, вона повертає логічне значення, яке збирається вказати, чи є передане символ * слова, будь то передана рядок знаходиться в нашому словнику. Таким чином, якщо вона присутня в словнику, якщо це в нашій хеш-таблиці, ми повернемося правда, і якщо це не так, ми повернемося хибним. Враховуючи це пройшло в слово, що ми збирається хеш слово. 

Тепер головне, щоб визнати, що в навантаженні, ми знали, що всі слова збиралися бути в нижньому регістрі, але тут, ми не так впевнені. Якщо ми поглянемо на наш хеш-функції, наш хеш-функція насправді є lowercasing кожен символ слова. Тому, незалежно від капіталізації Слово, наш хеш-функція буде повернутися той же індекс з яких-небудь капіталізація як вона повинна була б повернулися на зовсім нижньому регістрі варіант слова. Добре. 

Так ось наш індекс. Це хеш-таблиця для цього слова. Тепер, це цикл буде до більш ніж зв'язаний список це було за цим індексом. Так помітити ми ініціалізації запис вказати на те індекс. Ми збираємося продовжувати в той час як запис робить не дорівнює NULL, і пам'ятайте, що поновлення покажчик в нашій пов'язаного списку запис дорівнює початкового> наступна, так що є наша нинішня точка входу в Наступний пункт у зв'язаному списку. Добре. 

Таким чином, для кожного запису в пов'язаному списку, ми збираємося використовувати strcasecmp. Це не STRCMP бо ще раз, ми хочу зробити речі випадок бездушно. Тому ми використовуємо strcasecmp порівняти слово , Який був прийнятий в цю функцію проти слова, які в даній запису. Якщо вона повертає 0, це означає, що було матч, в цьому випадку ми хочемо повернутися вірно. Ми успішно знайшли Слово в нашій хеш-таблиці. 

Якби не було матчу, то ми збирається циклі знову і подивитися на Наступний запис. І ми будемо продовжувати зациклення в той час як є є записи в цій пов'язаного списку. Що станеться, якщо ми порушуємо з цього для циклу? Це означає, що ми не знайшли запис, відповідає це слово, в якому випадку ми повернутися помилковим, щоб вказати, що наш хеш-таблиці не містять це слово. І це все для перевірки. Добре. 

Так що давайте поглянемо на розмір. Тепер розмір буде досить просто так пам'ятаю, в навантаженні, для кожного слова ми виявили, що збільшується глобальна Мінлива hashtable_size. Таким чином, функція розмір як раз збирається повертатися, що глобальне змінна, і цим все сказано. 

Тепер, нарешті, ми повинні вивантажити словник, як тільки все буде зроблено. Так як ми збираємося це зробити? Прямо тут, ми пробігаємо по всіх відра нашої хеш-таблиці. Таким чином, є NUM_BUCKETS відра. І для кожного зв'язаного списку в нашій хеш стіл, ми збираємося циклу по Сукупність пов'язаного списку звільняючи кожен елемент. Тепер ми повинні бути обережні, так що тут ми є тимчасову змінну Це зберігання покажчик на наступний елемент у зв'язаному списку. А потім ми збираємося безкоштовно поточний елемент. 

Ми повинні бути впевнені, що ми робимо це, тому що ми не можу просто звільнити поточний елемент , А потім спробувати перейти до наступного покажчик так як тільки ми звільнили його пам'ять стає недійсним. Так що ми повинні тримати навколо покажчик на на наступний елемент, то ми можемо звільнити поточний елемент, і тоді ми зможемо оновити наш поточний елемент, щоб вказати на наступний елемент. 

Ми будемо цикл в той час як є елементи в цьому пов'язаному списку. Ми зробимо це для всіх пов'язаних списків в хеш-таблиця, і як тільки ми закінчимо з цим, ми повністю розвантажили хеш-таблиця, і ми закінчили. Так що це неможливо для вивантаженні небудь повернутися помилковим, і, коли ми закінчимо, ми просто повернути вірно.