У чым розніца хэш-табліцы і слоўніка пры праграмаванні?


адказ 1:

З тэхнічнага пункту гледжання яны ў асноўным могуць быць аднолькавымі. Абодва выкарыстоўваюцца для захоўвання дадзеных з пэўным наборам індэксаў для адназначнай ідэнтыфікацыі кожнай запісу. Звычайна ў выглядзе пары ключа-значэння, дзе і ключ, і значэнне могуць мець любы тып дадзеных, уключаючы структуры / класы.

Для гэтага тыпу збору дадзеных для хуткага пошуку канкрэтнай запісу выкарыстоўваецца ключавое значэнне. Гэта лепш за ўсё працуе, калі індэкс / ключ адсартаваны ў парадку ўзрастання ці ў змяншэнні. Гэта дазваляе бінарны пошук, каб вы маглі знайсці запіс з мінімальнай колькасцю параўнанняў. Аднак гэта павялічвае накладныя выдаткі, калі вам трэба ўставіць новую запіс, бо вам можа спатрэбіцца ўставіць яе дзесьці ў сярэдзіне індэкса, каб захаваць парадак сартавання. Гэта азначае, што кожны індэкс таксама павінен быць перамешчаны ў індэксе. Пакуль пошук ідзе хутка, даданне новых запісаў немагчыма. (У выпадку дрэва пошуку даданне запісаў можна зрабіць даволі хутка, хаця вы можаце вывесці дрэва з раўнавагі ...)

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

Сам вядро пажадана мець толькі адзін запіс, але хэш можа прывесці да сутыкнення, і таму ў адным вядры можа быць шмат запісаў. Калі ў вас 1000 запісаў, у сярэднім вядры будзе 10 запісаў у кожнай, калі ў нас 100 вёдраў. Аднак пошук у 10 запісах нашмат хутчэй, чым пошук у 1000 запісах. Калі вы выкарыстоўваеце большы спіс вёдраў, у вас звычайна запіс менш.

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

Слоўнік лічыцца асацыятыўным масівам, а хэш-табліца - неўпарадкаваным асацыятыўным масівам. У слоўніках вы можаце сартаваць альбо несортировать. Большасць распрацоўнікаў выкарыстоўваюць несортированный, які, як правіла, проста хэш-табліца! Гэта таму, што гэта шмат у чым.

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

Гэта ставіць мяне ў недабрабыт хэшавых дрэў, таму што вы можаце знайсці запісы, якія адпавядаюць ключу, які адпавядае пэўнай схеме. Напрыклад, усе, імя якіх пачынаецца з літары "W". Або любое лік ад 45 да 60. У дрэве пошуку вы можаце лёгка знайсці тое, што вы шукаеце, пашукаючы першую запіс, якая адпавядае гэтаму запыту, а потым ідзеце ўверх і ўніз, каб знайсці больш запісаў, пакуль вы не Пошук запісаў, якія не існуюць, ужо не супадае. З дапамогай хэш-табліцы вам прыйдзецца праверыць усе запісы.

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

У хэш-табліцы вам спатрэбіцца мільён параўнанняў ...

Каб знайсці дакладны ключ, хэш-табліца патрабуе толькі параўнання, а двайковае дрэва да 20 ...

Што тычыцца слоўніка. Гэта альбо хэш-табліцы, альбо дрэвы пошуку. Ён вызначаецца кодам, які стаіць за ім. Некаторыя рэалізацыі слоўнікаў могуць нават выкарыстоўваць абодва, паколькі яны будуць выкарыстоўваць асобны масіў для вёдраў, у той час як паказальнікі для наступнай і папярэдняй запісу выкарыстоўваюцца для стварэння дрэва пошуку. Таму выкананне запытаў па гэтых структурах спачатку вызначыць, які спосаб пошуку будзе найбольш эфектыўным. Калі вы хочаце знайсці пэўны ключ, выкарыстоўваецца хэш-табліца. Калі вам трэба шукаць пэўную вобласць, замест гэтага выкарыстоўваецца дрэва пошуку.

Дык розніца? Хэш-табліца - гэта толькі адна методыка захоўвання пары ключа-значэння. Слоўнік захоўвае пары ключавых дадзеных, але не ўказвае спосаб захавання. За слоўнікам можа стаяць хэш-табліца!


адказ 2:

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

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

Слоўнік выкарыстоўвае ключ для абазначэння значэння непасрэдна ў асацыятыўным масіве.

г.зн. (KEY => VALUE)

Хэш больш часта апісваецца як хэш-табліца, якая выкарыстоўвае хэш-функцыю для вылічэння пазіцыі ў памяці (ці больш проста масіў), дзе знаходзіцца значэнне. Хэш прымае KEY як уваходны і вызначае значэнне як выснову. Затым змесціце гэта значэнне ў індэкс памяці або масіва.

гэта значыць KEY => HASH FUNCTION => VALUE

Структура дадзеных хэша


адказ 3:

Слоўнік з'яўляецца больш агульным тыпам, у той час як HashTable не з'яўляецца агульным. Паколькі слоўнік універсальны, ён хутчэй (такія аперацыі, як устаўка, выдаленне, пошук), чым HashTable. Здача дадзеных адбываецца павольней, чым у слоўніка з-за бокса / распакоўкі, калі вы паспрабуеце атрымаць доступ да ключа, які не знаходзіцца ў паказанай хэш-табліцы, будуць дадзены нулявыя значэнні. Калі вы паспрабуеце атрымаць ключ у слоўніку, які не існуе ў паказаным слоўніку, выдаецца памылка.

HashTable з'яўляецца бяспечным для тэмы. Слоўнік таксама бяспечны для тэмы, але толькі для публічных статычных членаў.