Phenquestions
Predpokladajme, že ste vlastníkom veľkého obchodu s potravinami v kraji, kde žijete. Predpokladajme, že žijete vo veľkej oblasti, ktorá nie je komerčnou oblasťou. Nie ste jediný, kto má v tejto oblasti obchod s potravinami; máš pár konkurentov. A potom vás napadne, že by ste mali do cvičebnice zaznamenať telefónne čísla vašich zákazníkov. Cvičebnica je samozrejme malá a nemôžete zaznamenať všetky telefónne čísla všetkých vašich zákazníkov.
Takže sa rozhodnete zaznamenať iba telefónne čísla svojich stálych zákazníkov. A tak máte tabuľku s dvoma stĺpcami. V ľavom stĺpci sú uvedené mená zákazníkov a v pravom stĺpci sú uvedené telefónne čísla. Týmto spôsobom existuje mapovanie medzi menami zákazníkov a telefónnymi číslami. Pravý stĺpec tabuľky možno považovať za jadrovú hash tabuľku. Mená zákazníkov sa teraz nazývajú kľúče a telefónne čísla sa nazývajú hodnoty. Upozorňujeme, že keď zákazník uskutoční prevod, budete musieť zrušiť jeho riadok a nechať ho prázdny alebo ho nahradiť novým riadnym zákazníkom. Upozorňujeme tiež, že s časom sa počet bežných zákazníkov môže zvyšovať alebo znižovať, a tak sa tabuľka môže zväčšovať alebo zmenšovať.
Ďalším príkladom mapovania je predpoklad, že v kraji existuje klub poľnohospodárov. Samozrejme, nie všetci poľnohospodári budú členmi klubu. Niektorí členovia klubu nebudú riadnymi členmi (pokiaľ ide o účasť a príspevky). Barman sa môže rozhodnúť zaznamenať mená členov a ich výber nápoja. Vyvinie tabuľku z dvoch stĺpcov. Do ľavého stĺpca píše mená členov klubu. Do pravého stĺpca napíše zodpovedajúci výber nápoja.
Vyskytol sa problém: v pravom stĺpci sú duplikáty. To znamená, že rovnaký názov nápoja sa nachádza viackrát. Inými slovami, rôzni členovia pijú rovnaký sladký nápoj alebo rovnaký alkoholický nápoj, zatiaľ čo iní členovia pijú iný sladký alebo alkoholický nápoj. Bar-man sa rozhodne tento problém vyriešiť vložením úzkeho stĺpca medzi dva stĺpce. V tomto strednom stĺpci počínajúc zhora očísluje riadky začínajúce od nuly (t.j.e. 0, 1, 2, 3, 4 atď.), klesajúci, jeden index na riadok. Týmto je jeho problém vyriešený, pretože meno člena sa teraz mapuje na index, a nie na názov nápoja. Pretože je nápoj identifikovaný indexom, meno zákazníka sa namapuje na zodpovedajúci index.
Samotný stĺpec hodnôt (nápoje) tvorí základnú hashovaciu tabuľku. V upravenej tabuľke tvorí stĺpec indexov a s nimi spojené hodnoty (s duplikátmi alebo bez nich) normálnu hashovaciu tabuľku - úplná definícia hash tabuľky je uvedená nižšie. Kľúče (prvý stĺpec) nemusia nevyhnutne tvoriť súčasť hašovacej tabuľky.
Ako ďalší príklad opäť považujte sieťový server, kde môže používateľ zo svojho klientskeho počítača pridať nejaké informácie, odstrániť niektoré informácie alebo upraviť niektoré informácie. Pre server existuje veľa používateľov. Každé používateľské meno zodpovedá heslu uloženému na serveri. Tí, ktorí udržiavajú server, môžu vidieť používateľské mená a zodpovedajúce heslo, a tak môžu poškodiť prácu používateľov.
Vlastník servera sa teda rozhodne vytvoriť funkciu, ktorá zašifruje heslo pred jeho uložením. Užívateľ sa prihlási na server so svojim normálne pochopeným heslom. Teraz je však každé heslo uložené v zašifrovanej podobe. Ak niekto uvidí šifrované heslo a pokúsi sa pomocou neho prihlásiť, nebude to fungovať, pretože po prihlásení dostane server zrozumiteľné heslo a nie zašifrované heslo.
V takom prípade je kľúčom pochopené heslo a hodnotou je šifrované heslo. Ak je šifrované heslo v stĺpci šifrovaných hesiel, potom je týmto stĺpcom základná hash tabuľka. Ak tomuto stĺpcu predchádza ďalší stĺpec s indexmi začínajúcimi od nuly, takže každé šifrované heslo je spojené s indexom, potom stĺpec indexov aj stĺpec šifrovaného hesla tvoria normálnu hash tabuľku. Kľúče nemusia byť nevyhnutne súčasťou hašovacej tabuľky.
V tomto prípade si všimnite, že každý kľúč, ktorým je pochopiteľné heslo, zodpovedá užívateľskému menu. Existuje teda meno používateľa, ktorý zodpovedá kľúču, ktorý je namapovaný na index, ktorý je spojený s hodnotou, ktorá je šifrovaným kľúčom.
Definícia hashovacej funkcie, úplná definícia hashovacej tabuľky, význam poľa a ďalšie podrobnosti sú uvedené nižšie. Aby ste mohli oceniť zvyšok tohto tutoriálu, musíte mať vedomosti o ukazovateľoch (odkazoch) a prepojených zoznamoch.
Význam hashovacej funkcie a hashovacej tabuľky
Pole
Pole je množina po sebe nasledujúcich pamäťových miest. Všetky miesta sú rovnako veľké. K hodnote na prvom mieste sa pristupuje pomocou indexu 0; hodnota v druhom umiestnení je prístupná s indexom, 1; tretia hodnota je prístupná s indexom, 2; štvrtý s indexom, 3; a tak ďalej. Pole sa nemôže bežne zväčšiť ani zmenšiť. Aby bolo možné zmeniť veľkosť (dĺžku) poľa, je potrebné vytvoriť nové pole a do nového poľa skopírovať zodpovedajúce hodnoty. Hodnoty poľa sú vždy rovnakého typu.
Funkcia hash
V softvéri je hash funkcia funkcia, ktorá prevezme kľúč a vytvorí zodpovedajúci index pre bunku poľa. Pole má pevnú veľkosť (pevnú dĺžku). Počet kľúčov je ľubovoľnej veľkosti, zvyčajne väčší ako veľkosť poľa. Index vyplývajúci z hashovacej funkcie sa nazýva hash hodnota alebo súhrn alebo hash kód alebo jednoducho hash.
Hash tabuľka
Hašovacia tabuľka je pole s hodnotami, na ktorého indexy sú namapované kľúče. Kľúče sú nepriamo mapované na hodnoty. V skutočnosti sa hovorí, že kľúče sú namapované na hodnoty, pretože každý index je spojený s hodnotou (s alebo bez duplikátov). Funkcia, ktorá robí mapovanie (t.j.e. hashing) vzťahuje kľúče na indexy poľa a nie skutočne na hodnoty, pretože v hodnotách môžu byť duplikáty. Nasledujúca schéma ilustruje hashovaciu tabuľku pre mená ľudí a ich telefónne čísla. Bunky poľa (sloty) sa nazývajú segmenty.
Všimnite si, že niektoré vedrá sú prázdne. Hašovacia tabuľka nemusí mať nevyhnutne hodnoty vo všetkých svojich vedrách. Hodnoty v segmentoch nemusia byť nevyhnutne vzostupne. Indexy, s ktorými sú spojené, sú však vzostupne. Šípky označujú mapovanie. Všimnite si, že kľúče nie sú v poli. Nemusia byť v žiadnej štruktúre. Funkcia hash vezme akýkoľvek kľúč a vymaže index pre pole. Ak v segmente nie je žiadna hodnota spojená s hašovaním indexu, môže sa do tohto segmentu vložiť nová hodnota. Logický vzťah je medzi kľúčom a indexom, a nie medzi kľúčom a hodnotou spojenou s indexom.
Hodnoty poľa, rovnako ako hodnoty v tejto hashovacej tabuľke, sú vždy rovnakého dátového typu. Hašovacia tabuľka (segmenty) môže pripojiť kľúče k hodnotám rôznych dátových typov. V tomto prípade sú hodnoty poľa všetky ukazovatele smerujúce k rôznym typom hodnôt.
Hašovacia tabuľka je pole s hašovacou funkciou. Funkcia vezme kľúč a zahaľuje zodpovedajúci index, a tak spája kľúče s hodnotami v poli. Kľúče nemusia byť súčasťou hašovacej tabuľky.
Prečo pole a neprepojený zoznam pre tabuľku hash
Pole pre hashovaciu tabuľku je možné nahradiť dátovou štruktúrou prepojeného zoznamu, ale vyskytol by sa problém. Prvý prvok prepojeného zoznamu je prirodzene v indexe 0; druhý prvok je prirodzene v indexe, 1; tretí je prirodzene v indexe, 2; a tak ďalej. Problém prepojeného zoznamu spočíva v tom, že na získanie hodnoty musí byť zoznam iterovaný, čo trvá dlho. Prístup k hodnote v poli je náhodný prístup. Len čo je index známy, hodnota sa získa bez iterácie; tento prístup je rýchlejší.
Zrážka
Hašovacia funkcia vezme kľúč a zahašuje zodpovedajúci index, aby mohla načítať priradenú hodnotu alebo vložiť novú hodnotu. Ak je účelom načítať hodnotu, zatiaľ neexistuje žiadny problém (žiadny problém). Ak je však účelom vložiť hodnotu, hašovaný index už môže mať priradenú hodnotu, a to je kolízia; novú hodnotu nemožno uviesť tam, kde už existuje. Existujú spôsoby riešenia kolízie - pozri nižšie.
Prečo dochádza ku kolízii
V príklade obchodu s potravinami vyššie sú kľúčmi mená zákazníkov a názvy nápojov hodnoty. Všimnite si, že zákazníkov je príliš veľa, zatiaľ čo pole má obmedzenú veľkosť a nemôže prijať všetkých zákazníkov. V poli sú teda uložené iba nápoje bežných zákazníkov. Ku kolízii dôjde, keď sa stane nepravidelný zákazník pravidelným. Zákazníci pre obchod tvoria veľkú sadu, zatiaľ čo počet segmentov pre zákazníkov v poli je obmedzený.
V prípade hash tabuliek sa veľmi pravdepodobne zaznamenajú hodnoty pre kľúče. Keď sa stane pravdepodobným kľúč, ktorý nebol pravdepodobný, pravdepodobne by došlo ku kolízii. V skutočnosti ku kolízii vždy dochádza pri hašovacích tabuľkách.
Základy riešenia kolízií
Dva prístupy k riešeniu kolízií sa nazývajú samostatné reťazenie a otvorené adresovanie. Teoreticky by kľúče nemali byť v dátovej štruktúre alebo by nemali byť súčasťou hašovacej tabuľky. Obidva prístupy však vyžadujú, aby stĺpec kľúča predchádzal hašovaciu tabuľku a stal sa súčasťou celkovej štruktúry. Namiesto toho, aby boli kľúče v stĺpci kľúčov, môžu byť ukazovatele na kľúče v stĺpci kľúčov.
Praktická hašovacia tabuľka obsahuje stĺpec kľúčov, ale tento stĺpec kľúčov nie je oficiálne súčasťou hašovacej tabuľky.
Buď prístup k rozlíšeniu môže mať prázdne segmenty, nie nevyhnutne na konci poľa.
Samostatné reťazenie
V samostatnom reťazení, keď dôjde ku kolízii, nová hodnota sa pridá napravo (nie nad alebo pod) od zrazenej hodnoty. Takže dve alebo tri hodnoty nakoniec majú rovnaký index. Zriedkavo viac ako tri by mali mať rovnaký index.
Môže mať viac ako jedna hodnota skutočne rovnaký index v poli? - Nie. Takže v mnohých prípadoch je prvou hodnotou indexu ukazovateľ na prepojenú dátovú štruktúru zoznamu, ktorá obsahuje jednu, dve alebo tri zrazené hodnoty. Nasledujúca schéma je príkladom hashovacej tabuľky na samostatné reťazenie zákazníkov a ich telefónnych čísel:
Prázdne vedrá sú označené písmenom x. Zvyšok slotov má ukazovatele na prepojené zoznamy. Každý prvok prepojeného zoznamu má dve dátové polia: jedno pre meno zákazníka a druhé pre telefónne číslo. Konflikt nastáva pri kľúčoch: Peter Jones a Suzan Lee. Zodpovedajúce hodnoty pozostávajú z dvoch prvkov jedného prepojeného zoznamu.
Pre konfliktné kľúče je kritérium na vloženie hodnoty rovnaké ako kritérium použité na nájdenie (a čítanie) hodnoty.
Otvorte adresovanie
Pri otvorenom adresovaní sú všetky hodnoty uložené v poli vedra. Ak dôjde ku konfliktu, nová hodnota sa vloží do prázdneho segmentu, ktorý zodpovedá príslušnej hodnote konfliktu, a to podľa určitých kritérií. Kritérium použité na vloženie hodnoty pri konflikte je rovnaké kritérium použité na vyhľadanie (hľadanie a čítanie) hodnoty.
Nasledujúci diagram ilustruje riešenie konfliktov s otvoreným adresovaním:
Hašovacia funkcia prevezme kľúča Petera Jonesa, zahašuje index 152 a uloží jeho telefónne číslo do súvisiaceho segmentu. Po nejakom čase má hašovacia funkcia rovnaký index, 152 od kľúča, Suzan Lee, kolidujúci s indexom pre Petera Jonesa. Na vyriešenie tohto problému je hodnota pre Suzan Lee uložená v segmente ďalšieho indexu 153, ktorý bol prázdny. Hašovacia funkcia hašuje index, 153 pre kľúč, Robin Hood, ale tento index sa už použil na vyriešenie konfliktu pre predchádzajúci kľúč. Takže hodnota pre Robina Hooda sa umiestni do nasledujúceho prázdneho segmentu, ktorý je hodnotou indexu 154.
Metódy riešenia konfliktov pre samostatné reťazenie a otvorené adresovanie
Samostatné reťazenie má svoje metódy riešenia konfliktov a otvorené riešenie má tiež svoje vlastné metódy riešenia konfliktov.
Metódy riešenia konfliktov samostatného reťazenia
Teraz sú stručne vysvetlené spôsoby samostatného reťazenia hašovacích tabuliek:
Samostatné reťazenie s prepojenými zoznamami
Táto metóda je vysvetlená vyššie. Každý prvok prepojeného zoznamu však nemusí nevyhnutne obsahovať kľúčové pole (napr.g. vyššie uvedené pole pre meno zákazníka).
Samostatné reťazenie s hlavičkovými bunkami
V tejto metóde je prvý prvok prepojeného zoznamu uložený vo vedre poľa. To je možné, ak je dátový typ pre pole prvkom prepojeného zoznamu.
Samostatné reťazenie s inými štruktúrami
Namiesto prepojeného zoznamu je možné použiť akúkoľvek inú dátovú štruktúru, ako je napríklad Self-Balancing Binary Search Tree, ktorý podporuje požadované operácie, pozri neskôr.
Metódy riešenia otvorených konfliktov adresovania
Metóda riešenia konfliktu pri otvorenom adresovaní sa nazýva sekvencia sondy. Teraz sú stručne vysvetlené tri známe sekvencie sondy:
Lineárne sondovanie
Pri lineárnom sondovaní sa pri konflikte hľadá najbližšie prázdne vedro pod vedrom pri konflikte. Pri lineárnom snímaní sú kľúč aj jeho hodnota uložené v rovnakom segmente.
Kvadratické sondovanie
Predpokladajme, že ku konfliktu dôjde v indexe H. Nasledujúci prázdny priestor (vedro) na indexe H + 12 sa používa; ak je už obsadený, potom ďalší prázdny v H + 22 sa používa, ak je už obsadené, potom ďalšie prázdne v H + 32 sa používa atď. Existujú rôzne varianty.
Double Hashing
Pri dvojitom hašovaní existujú dve hašovacie funkcie. Prvý vypočítava (hašuje) index. Ak dôjde ku konfliktu, druhý použije rovnaký kľúč na určenie toho, ako hlboko by sa mala hodnota vložiť. Je toho ešte viac - pozri neskôr.
Funkcia Perfect Hash
Dokonalá hashovacia funkcia je hashovacia funkcia, ktorá nemôže mať za následok kolíziu. To sa môže stať, keď je množina klávesov relatívne malá a každý kláves sa mapuje na konkrétne celé číslo v hashovacej tabuľke.
V znakovej sade ASCII je možné pomocou hašovacej funkcie mapovať veľké písmená na príslušné malé písmená. Písmená sú v pamäti počítača vyjadrené ako čísla. V znakovej sade ASCII je A 65, B 66, C 67 atd. a a je 97, b je 98, c je 99 atď. Ak chcete mapovať z bodu A na písmeno a, pridajte 32 až 65; do mapy z B do b pridajte 32 až 66; na mapovanie z C do c pridajte 32 do 67; a tak ďalej. Tu sú veľké písmená klávesy a malé písmená hodnoty. Hašovacou tabuľkou pre toto môže byť pole, ktorého hodnoty sú spojené indexy. Pamätajte, že vedrá poľa môžu byť prázdne. Vedrá v poli od 64 do 0 môžu byť teda prázdne. Funkcia hash jednoducho pridá 32 k veľkému číslu kódu, aby získala index, a teda malé písmeno. Takáto funkcia je dokonalá hashovacia funkcia.
Hašovanie od celočíselných k celočíselným indexom
Existujú rôzne spôsoby hašovania celého čísla. Jeden z nich sa nazýva metóda (funkcia) modulového delenia.
Funkcia hashovania modulovej divízie
Funkcia v počítačovom softvéri nie je matematickou funkciou. Vo výpočtovej technike (softvér) pozostáva funkcia z množiny príkazov, ktorým predchádzajú argumenty. Pre funkciu rozdelenia modulov sú kľúče celé čísla a sú mapované na indexy poľa segmentov. Sada kľúčov je veľká, takže by sa mapovali iba tie kľúče, ktoré sa pri aktivite pravdepodobne vyskytnú. Takže dochádza ku kolíziám, keď je potrebné mapovať nepravdepodobné kľúče.
Vo vyhlásení,
20/6 = 3R2
20 je dividenda, 6 je deliteľ a 3 zvyšok 2 je kvocient. Zvyšok 2 sa tiež nazýva modulo. Poznámka: je možné mať modulo 0.
Pre toto zatrieďovanie je veľkosť tabuľky zvyčajne sila 2, napr.g. 64 = 26 alebo 256 = 28, atď. Deliteľom tejto hašovacej funkcie je prvočíslo blízke veľkosti poľa. Táto funkcia vydelí kľúč deliteľom a vráti modulo. Modulo je index poľa segmentov. Priradená hodnota v segmente je hodnota podľa vášho výberu (hodnota pre kľúč).
Kľúče s premennou dĺžkou
Tu sú kľúče sady kľúčov texty rôznych dĺžok. Do pamäte možno uložiť rôzne celé čísla s rovnakým počtom bajtov (veľkosť anglického znaku je bajt). Ak majú rôzne kľúče rozdielnu veľkosť bajtu, hovorí sa o nich, že majú premenlivú dĺžku. Jedna z metód hashovania premenných dĺžok sa nazýva Radix Conversion Hashing.
Radixový konverzný hash
V znaku je každý znak v počítači číslo. V tejto metóde,
Hash kód (index) = x0ak − 1+X1ak − 2+... + xk − 2a1+Xk − 1a0
Kde (x0, x1, ..., xk − 1) sú znaky vstupného reťazca a a je radix, e.g. 29 (pozri neskôr). k je počet znakov v reťazci. Je toho ešte viac - pozri neskôr.
Kľúče a hodnoty
V páre kľúč / hodnota nemusí byť hodnotou nevyhnutne číslo alebo text. Môže to byť aj záznam. Záznam je zoznam napísaný vodorovne. V páre kľúč - hodnota môže každý kľúč skutočne odkazovať na nejaký iný text alebo číslo alebo záznam.
Asociatívne pole
Zoznam je dátová štruktúra, v ktorej sa nachádzajú položky zoznamu, a v zozname existuje skupina operácií. Každá položka zoznamu môže pozostávať z dvojice položiek. Všeobecnú hashovaciu tabuľku s jej kľúčmi možno považovať za dátovú štruktúru, ale je to skôr systém ako dátová štruktúra. Kľúče a ich zodpovedajúce hodnoty navzájom veľmi nezávisia. Nie sú navzájom veľmi prepojené.
Na druhej strane je asociatívne pole podobná vec, ale kľúče a ich hodnoty sú navzájom veľmi závislé; navzájom veľmi súvisia. Môžete mať napríklad asociatívnu škálu ovocia a ich farieb. Každé ovocie má prirodzene svoju farbu. Názov ovocia je kľúčom; farba je hodnota. Počas vkladania je každý kľúč vložený so svojou hodnotou. Pri mazaní sa vymaže každý kľúč s jeho hodnotou.
Asociatívne pole je dátová štruktúra tabuľky hash zložená z párov kľúč / hodnota, kde pre kľúče neexistuje duplikát. Hodnoty môžu mať duplikáty. V tejto situácii sú kľúče súčasťou štruktúry. To znamená, že kľúče musia byť uložené, zatiaľ čo pri všeobecnej hast tabuľke sa kľúče nemusia ukladať. Problém duplikovaných hodnôt je prirodzene riešený indexmi poľa segmentov. Nezamieňajte duplicitné hodnoty s kolíziou v indexe.
Pretože asociatívne pole je dátová štruktúra, má najmenej tieto operácie:
Asociatívne operácie s poľom
vložiť alebo pridať
Týmto sa do kolekcie vloží nový pár kľúč / hodnota a kľúč sa namapuje na jeho hodnotu.
preradiť
Táto operácia nahradí hodnotu konkrétneho kľúča novou hodnotou.
odstrániť alebo odstrániť
Týmto sa odstráni kľúč plus jeho zodpovedajúca hodnota.
vyhľadať
Táto operácia vyhľadá hodnotu konkrétneho kľúča a vráti hodnotu (bez jej odstránenia).
Záver
Dátová štruktúra tabuľky hash sa skladá z poľa a funkcie. Táto funkcia sa nazýva hash funkcia. Funkcia mapuje kľúče na hodnoty v poli prostredníctvom indexov poľa. Kľúče nemusia byť nevyhnutne súčasťou dátovej štruktúry. Sada kľúčov je zvyčajne väčšia ako uložené hodnoty. Keď dôjde ku kolízii, vyrieši sa to buď prístupom samostatného reťazenia alebo prístupom otvoreného adresovania. Asociatívne pole je špeciálnym prípadom dátovej štruktúry hash tabuľky.
