ROB BOWDEN: Hi. Es esmu Rob, un pieņemsim hash Šis risinājums out. Tāpēc šeit mēs ejam, lai īstenotu Kopumā hash tabulu. Mēs redzam, ka struktūrai mezgla mūsu hash tabula gatavojas izskatās šādi. Tātad, tas notiek, lai būtu char vārds masīvs izmēra garumu plus 1. Neaizmirstiet 1 kopš maksimāli vārdu vārdnīcā ir 45 rakstzīmes, un tad mēs ejam uz vajag vienu papildus rakstzīmi slīpsvītru 0. 

Un tad mūsu hash tabulu katrā kauss ir gatavojas glabāt saistīts saraksts mezglu. Mēs nedarām lineāra zondēšana šeit. Un tāpēc, lai saite uz nākamā elements spainī, mums ir nepieciešams struct mezglā * nākamo. Tātad, tas ir tas, ko mezglā izskatās. Tagad šeit ir deklarācija mūsu hash tabulu. Tas nāksies 16384 kausi, bet šis numurs nav īsti jautājums. Un visbeidzot, mēs esam nāksies globālo mainīgo hashtable_size, kas gatavojas sākt ar 0, un tas ir būs izsekot, cik daudz vārdu bija mūsu vārdnīcā. Labi. 

Tātad, pieņemsim to apskatīt slodzes. Tāpēc ievērosiet, ka slodze, tā atgriež bool. Jūs atgrieztos taisnība, ja tas bija veiksmīgi piekrauts un viltus citādi. Un tas notiek const char * zvaigzne vārdnīcā, kas ir vārdnīcā ka mēs vēlamies, lai atvērtu. Tā ka ir pirmā lieta, mēs gatavojamies darīt. Mēs ejam, lai fopen vārdnīcu, lai lasījumā, un mēs esam nāksies lai pārliecinātos, ka tas ir izdevies, tādēļ, ja tas atgriezās NULL, tad mēs neesam veiksmīgi atvērt vārdnīcu un mums ir nepieciešams, lai atgrieztos nepatiesa. 

Bet, pieņemot, ka tā veiksmīgi atvērt, tad mēs vēlamies, lai izlasītu vārdnīca. Lai saglabātu looping kamēr mēs atrodam kādu iemesls, lai izkļūt no šīs cilpa, ko mēs redzēsim. Tāpēc saglabājiet looping, un tagad mēs ejam lai malloc vienu mezglu. Un, protams, mums ir nepieciešams, lai kļūdu pārbaude vēlreiz, tāpēc, ja mallocing neizdevās , un mēs vēlamies, lai izkrautu jebkuru mezglu, ko mēs notika ar malloc pirms slēgt vārdnīcu un atgriezties viltus. 

Bet ignorējot, ka, pieņemot, ka mēs izdevies, tad mēs vēlamies izmantot fscanf lasīt vienu vārdu no mūsu vārdnīca mūsu mezglā. Tātad, atcerieties, ka ieejas-> vārds ir char vārdu bufera izmēra garumu plus viens, ka mēs ejam uzglabāt vārdu iekšā Tāpēc fscanf gatavojas atgriezties 1 tik ilgi jo tas varēja veiksmīgi nolasīt vārdu no lietas materiāliem. 

Ja nu kļūda notiek, vai mēs sasniegsim faila beigas, tas nav return 1 tādā gadījumā, ja tā nav atgriezties 1, mēs beidzot gatavojas lauzt no šīs kamēr cilpa. Tātad mēs redzam, ka tad, kad mēs esam veiksmīgi lasīt vārdu uz Ierakstu-> vārdu, tad mēs ejam uz hash šis vārds, izmantojot mūsu hash funkciju. Pieņemsim to apskatīt hash funkciju. 

Tātad jums nav tiešām ir nepieciešams saprast. Un patiesībā, mēs vienkārši velk to hash funkciju no interneta. Vienīgais, kas jums ir nepieciešams atzīt, ka tas aizņem const char * vārdu, tāpēc tas ir ņemot virkni kā priekšnodokli un atgriešanās neparakstītu int kā produkciju. Tātad tas viss hash funkciju, tas ir uzņem ieejas, tas dod jums indekss par hash tabulu. Ievērojiet, ka mēs esam modding ar NUM_BUCKETS tāpēc hash vērtība atgriezās patiesībā ir rādītājs uz hash tabulu un nav rādītājs pārsniedz robežas no masīva. 

Tāpēc, ka hash funkciju, mēs ejam hash vārdu, ka mēs lasām No vārdnīcas, un tad mēs ejam izmantot, kas ir, lai ievietotu stāšanās hash tabulu. Tagad, Hashtable hash ir pašreizējā saistīts saraksts hash tabulā, un tas ir ļoti iespējams, ka ir tikai NULL. Mēs vēlamies, lai ievietotu savu ienākšanu sākot no šīs saistīta saraksta, un tā Mēs ejam, lai būtu mūsu pašreizējo ierakstu norāda uz to, ko hash tabulā šobrīd punkti, un tad mēs ejam, lai saglabātu hash tabulu, hash pašreizējais ieraksts. 

Tātad šīs divas līnijas veiksmīgi ievietot ieraksts sākumā saistīts saraksts šajā indeksā hash tabulā. Pēc tam, kad mēs esam darīts ar to, ka mēs zinām, ka mēs atradām vēl vienu vārdu vārdnīcu un mēs solis vēlreiz. Tāpēc mēs turpinām darām līdz fscanf beidzot atgriežas kaut kas nav 1 pie Kurā brīdī atcerēties, ka mums ir nepieciešams, lai bezmaksas ieeja, tāpēc šeit mēs malloced ierakstu, un mēs mēģinājām lasīt kaut ko no vārdnīcas. Un mēs neesam veiksmīgi nolasīt kaut kas no vārdnīcas, kurā gadījumā mums ir nepieciešams, lai atbrīvotu ierakstu, ka mēs nekad faktiski laisti hash tabulu un beidzot pauze. 

Kad mēs izcelties, mums ir nepieciešams, lai redzētu, labi, mēs esam izcelties, jo tur bija kļūda lasot no lietas materiāliem, vai mēs esam izcelties, jo mēs nonācām faila beigas? Ja tur bija kļūda, tad mēs vēlamies atgriezties viltus jo slodze nebija panākumus, un šajā procesā, mēs vēlamies izkraut visus vārdus, ka mēs lasām iekšā un aizveriet vārdnīcas faila. Pieņemot, ka mums izdosies, tad mēs vienkārši joprojām ir nepieciešams, lai aizvērtu vārdnīcu failu, un visbeidzot atgriezties taisnība, jo mēs esam veiksmīgi ielādēta vārdnīca. Un tas ir tas, lai slodze. 

Tāpēc tagad pārbaudiet, ņemot piekrauts hash tabulu, gatavojas izskatās šādi. Lai pārbaudītu, tas atgriež bool, kas gatavojas, lai norādītu, vai pagājis-in char * vārdu, vai pagājis-in virkne ir mūsu vārdnīcā. Tātad, ja tas ir norādīts vārdnīcā, ja tas ir mūsu hash tabulu, mēs atgriezīsimies taisnība, un, ja tā nav, mēs atgriezīsimies nepatiesa. Ņemot vērā šo pagājis-in vārdu, mēs esam gatavojas hash vārdu. 

Tagad svarīga lieta atzīt, ka slodzes, zinājām, ka visi vārdi bija būs mazie burti, bet šeit, mēs neesam tik pārliecināts. Ja mēs to apskatīt mūsu hash funkciju, mūsu hash funkcija faktiski ir lowercasing katru rakstzīmi vārda. Tāpēc neatkarīgi no kapitalizācijas Vārds, mūsu hash funkcija būs atpakaļ to pašu indeksu neatkarīgi kapitalizācija ir tā, kā būtu atpakaļ uz pavisam mazie burti versija vārda. Labi. 

Tātad tas ir mūsu indeksa. Tas ir hash tabulu par šo vārdu. Tagad šis cilpa notiek lai pār to saistīts saraksts tas bija šajā indeksā. Tāpēc paziņojums mums ir inicializēta ierakstu , lai norādītu uz minētā indeksa. Mēs turpināsim, bet ieraksts nav nav vienāds NULL, un atcerieties, ka atjauninot rādītāju mūsu saistīts sarakstā ieraksts ir vienāds ieraksts-> blakus, tāpēc ir Mūsu pašreizējais sākumpunkts Nākamais punkts saistītajā sarakstā. Labi. 

Tātad uz katru ierakstu saistītajā sarakstā, mēs ejam, lai izmantotu strcasecmp. Tas nav strcmp jo atkal mēs gribu darīt lietas lietu insensitively. Tāpēc mēs izmantojam strcasecmp salīdzināt vārdu , kas tika pieņemts, lai šo funkciju pret vārdu, kas ir šajā ierakstā. Ja tas atgriež 0, tas nozīmē, ka tur bija spēles, un tādā gadījumā mēs vēlamies atgriezties true. Mēs veiksmīgi atraduši vārdu mūsu hash tabulā. 

Ja nebija spēle, tad mēs esam dodas uz cilpu atkal un apskatīt Nākamais ieraksts. Un mēs turpināsim looping, bet tur Ir ieraksti šajā saistīta sarakstā. Kas notiek, ja mēs pārkāpjam no šīs cilpa? Tas nozīmē, ka mēs neesam atrast ierakstu, kas saskaņota šo vārdu, tādā gadījumā mēs atgriežamies viltus, lai norādītu, ka mūsu hash tabulu neietvēra šo vārdu. Un tas ir tas, lai pārbaudi. Labi. 

Tātad, pieņemsim to apskatīt lieluma. Tagad lielums būs diezgan vienkāršs jo atceros, slodzes, katram vārdam mēs noskaidrojām, mēs palielina globālās mainīgais hashtable_size. Tā lielums funkcija ir tikai gatavojas atgriezties, ka globālās mainīgs, un tas arī viss. 

Beidzot, mums ir nepieciešams, lai izkrautu vārdnīca, kad viss ir izdarīts. Tātad, kā mēs gatavojamies darīt? Tieši šeit, mēs esam looping visā spaiņi mūsu hash tabulu. Tāpēc ir NUM_BUCKETS kausi. Un katram, kas saistīta saraksta mūsu hash galda, mēs ejam, lai cilpa pār veselums saistītā saraksta atbrīvojot katru elementu. Tagad, mums ir jābūt uzmanīgiem, tāpēc šeit mēs ir pagaidu mainīgo, kas ir uzglabāšanas rādītāju uz nākamā elements saistītajā sarakstā. Un tad mēs ejam uz brīvu pašreizējais elements. 

Mums ir nepieciešams, lai pārliecinātos, mēs to darām, jo ​​mēs var ne tikai brīvi Pašlaik skatītās elements un tad mēģināt piekļūtu nākamajai rādītāju jo, kad mēs atbrīvojušies to atmiņa kļūst nederīgs. Tāpēc mums ir nepieciešams, lai saglabātu apmēram rādītāju uz nākamais elements, tad mēs varam brīvi strāvas elements, un pēc tam, mēs var atjaunināt Mūsu pašreizējais elements, lai norādītu nākamais elements. 

Mēs cilpas, bet tur ir elementi Šajā saistīts sarakstā. Mēs darīsim, ka visiem, kas saistīti sarakstos hash tabulu, un pēc tam, kad mēs esam darījuši ar to, ka mēs esam pilnīgi izkrauts hash tabulu, un mēs esam darījuši. Tātad, tas ir neiespējami izkrauj kādreiz atgriezties viltus, un, kad mēs esam darīts, mēs vienkārši atgriezties true.