streamalism.org

1. Úvod

V tomto tutoriále uvažujeme o hashovacích technikách používaných v rôznych dátových štruktúrach, ktoré poskytujú neustály časový prístup k ich prvkom.

Podrobnejšie rozoberáme tzv skladacia technika a stručne sa oboznámte s technikami stredného štvorca a kombinovania.

2. Prehľad

Keď vyberáme dátové štruktúry na ukladanie objektov, jedným z aspektov je, či k nim potrebujeme rýchly prístup.

Balík nástrojov Java nám ponúka pomerne veľa dátových štruktúr na ukladanie našich objektov. Ďalšie informácie o údajových štruktúrach nájdete na našej kompilačnej stránke Java Collections, ktorá obsahuje príručky k niekoľkým z nich.

Ako vieme, niektoré z týchto dátových štruktúr nám umožňujú získavať ich prvky v konštantnom čase, nezávisle od počtu prvkov, ktoré obsahujú.

Najjednoduchšie je pravdepodobne pole. V skutočnosti pristupujeme k prvkom v poli podľa ich indexu. Prístupový čas samozrejme nezávisí od veľkosti poľa. V skutočnosti v zákulisí veľa dátových štruktúr veľmi využíva polia.

Problém je v tom, že indexy polí musia byť číselné, pričom často uprednostňujeme manipuláciu s týmito dátovými štruktúrami s objektmi.

S cieľom vyriešiť tento problém sa veľa dátových štruktúr pokúša priradiť objektom číselnú hodnotu, ktorá môže slúžiť ako index poľa. Túto hodnotu nazývame a hash hodnota alebo jednoducho a hash.

3. Hašovanie

Hašovanie je transformácia objektu na číselnú hodnotu. Funkcie, ktoré vykonávajú tieto transformácie, sa nazývajú hašovacie funkcie.

Z dôvodu jednoduchosti zvážime hašovacie funkcie, ktoré transformujú reťazce na indexy polí, to znamená na celé čísla z rozsahu [0, N] s konečnou N.

Prirodzene, hašovacia funkcia sa aplikuje na širokú škálu reťazcov. Preto sú jej „globálne“ vlastnosti dôležité.

Bohužiaľ nie je možné, aby hash funkcia vždy transformovala rôzne reťazce na rôzne čísla.

Celkom ľahko sa presvedčíme, že počet reťazcov je v akomkoľvek rozsahu oveľa väčší ako počet celých čísel [0, N]. Preto je nevyhnutné, že existuje pár nerovnakých reťazcov, pre ktoré hash funkcia produkuje rovnaké hodnoty. Tento jav sa nazýva Zrážka.

Nebudeme sa ponárať do technických detailov za hashovacími funkciami, ale je zrejmé, že dobrá hashovacia funkcia by sa mala pokúsiť rovnomerne mapovať reťazce, na ktorých je definovaná, do čísel.

Ďalšou zjavnou požiadavkou je, že dobrá hash funkcia by mala byť rýchla. Ak výpočet hashovej hodnoty trvá príliš dlho, potom nemôžeme rýchlo získať prístup k prvkom.

V tomto tutoriáli považujeme jeden z techniky, ktoré sa snažia dosiahnuť jednotné mapovanie pri rýchlom udržiavaní.

4. Technika skladania

Naším cieľom je nájsť funkciu, ktorá transformuje reťazce na indexy polí. Na ilustráciu predstavíme, že chceme, aby toto pole malo kapacitu pre 105 prvkov, a použijeme reťazec Jazyk Java ako príklad.

4.1. Popis

Začnime konverziou znakov reťazca na čísla. ASCII je dobrým kandidátom na túto operáciu:

Teraz zoradíme čísla, ktoré sme práve získali, do skupín nejakej veľkosti. Všeobecne vyberáme hodnotu veľkosti skupiny na základe veľkosti nášho poľa, ktoré je 105. Pretože čísla, do ktorých sme transformovali znaky, obsahujú dve až tri číslice, bez straty všeobecnosti, môžeme veľkosť skupiny nastaviť na dva:

Ďalším krokom je zreťazenie čísel v každej skupine, akoby išlo o reťazce, a nájdenie ich súčtu:

Teraz musíme urobiť posledný krok. Skontrolujme, či je to číslo 348933 môže slúžiť ako index nášho poľa veľkosti 105. Prirodzene, presahuje maximálnu povolenú hodnotu 99999. Tento problém môžeme ľahko prekonať použitím modulo operátora, aby sme našli konečný výsledok:

348933 % 10000 = 48933

4.2. Záverečné poznámky

Vidíme, že algoritmus neobsahuje žiadne časovo náročné operácie, a preto je dosť rýchly. Každý znak vstupného reťazca prispieva k konečnému výsledku. Táto skutočnosť rozhodne pomáha znižovať kolízie, ale nie úplne sa im vyhnúť.

Napríklad, ak sme chceli preskočiť skladanie a použiť operátor modulo priamo na vstupný reťazec transformovaný ASCII (ignorujeme problém s pretečením)

749711897321089711010311797103101 % 100000 = 3101

potom by takáto hashovacia funkcia vyprodukovala rovnakú hodnotu pre všetky reťazce, ktoré majú rovnaké posledné dva znaky ako náš vstupný reťazec: age, sVek, large, a tak ďalej.

Z popisu algoritmu ľahko vidíme, že nie je zbavený kolízií. Napríklad algoritmus vytvára rovnakú hodnotu hash pre Jazyk Java a jazyk vaJa struny.

5. Ďalšie techniky

Technika skladania je pomerne častá, ale nie jediná. Niekedy binning alebo stredný štvorec užitočné môžu byť aj techniky.

Ilustrujeme ich myšlienku tým, že nepoužívame reťazce, ale čísla (predpokladajme, že sme reťazce už nejako transformovali na čísla). Nebudeme diskutovať o ich výhodách a slabostiach, ale po preštudovaní algoritmov si môžete vytvoriť názor.

5.1. Technika binovania

Predpokladajme, že máme 100 celých čísel a chceme, aby ich naša hashová funkcia mapovala do poľa 10 prvkov. Potom môžeme tých 100 celých čísel usporiadať do desiatich skupín tak, že prvých desať celých čísel skončí v prvom priečinku, ďalších desať celých čísel skončí v druhom priečinku atď .:

5.2. Technika stredného štvorca

Tento algoritmus navrhol John von Neumann a umožňuje nám generovať pseudonáhodné čísla vychádzajúce z daného čísla.

Poďme si to ilustrovať na konkrétnom príklade. Predpokladajme, že máme štvorciferné číslo 1111. Podľa algoritmu to zaoblíme, čím dostaneme 1234321‬. Teraz extrahujeme štyri číslice zo stredu, napríklad 2343. Algoritmus nám umožňuje opakovať tento proces, kým nie sme spokojní s výsledkom.

6. Záver

V tomto tutoriáli sme zvážili niekoľko hashovacích techník. Podrobne sme opísali techniku ​​skladania a bleskovo sme opísali, ako je možné dosiahnuť binning a mid-square.

Ako vždy, zodpovedajúce útržky kódu nájdeme v našom úložisku GitHub.