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

А потым наш хэш-табліцы ў кожным вядро збіраецца захоўваць звязаны спіс вузлоў. Мы не робім лінейную зандзіравання тут. І таму для таго, каб звязаць да наступнага элемент у вядро, мы павінны структура вузла * наступны. Дык вось што вузел выглядае. Цяпер, вось дэкларацыя нашай хэш-табліцы. Гэта будзе мець 16384 вёдраў, але гэта лік не мае вялікага значэння. І, нарэшце, мы збіраемся мець глабальная пераменная 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 вядра. І для кожнага звязанага спісу ў нашай хэш стол, мы збіраемся цыкла па Сукупнасць звязанага спісу вызваляючы кожны элемент. Цяпер мы павінны быць асцярожныя, так што тут мы ёсць часовую зменную Гэта захоўвання паказальнік на наступны элемент у звязаным спісе. А потым мы збіраемся бясплатна бягучы элемент. 

Мы павінны быць упэўнены, што мы робім гэта, так як мы не магу проста вызваліць бягучы элемент , А затым паспрабаваць пераходу да наступнай паказальнік так як толькі мы вызвалілі яго памяць становіцца несапраўдным. Так што мы павінны трымаць вакол паказальнік на на наступны элемент, то мы можам вызваліць бягучы элемент, і тады мы зможам абнавіць наш бягучы элемент, каб паказаць на наступны элемент. 

Мы будзем цыкл у той час як ёсць элементы у гэтым звязаным спісе. Мы зробім гэта для ўсіх звязаных спісаў у хэш-табліца, і як толькі мы скончым з гэтым, мы цалкам разгрузілі хэш-табліца, і мы скончылі. Так што гэта немагчыма для выгрузцы калі-небудзь вярнуцца ілжывым, і, калі мы скончым, мы проста вярнуць дакладна.