Hašovacia tabuľka: Rozdiel medzi revíziami

Smazaný obsah Přidaný obsah
Bronto (diskusia | príspevky)
opravil som sh začiatku textu
Maros (diskusia | príspevky)
Bez shrnutí editace
Riadok 1:
{{preklad}} [[:en:hash table]]
{{pracuje sa (2)}}
'''Hašovacia tabuľka''' alebo '''hašovacia mapa''' alebo '''tabuľka výpočtu adresy transformáciou (kľúča)''' je v [[informatika|informatike]] [[údajová štruktúra]], ktorá asociuje ''kľúče'' s ''hodnotami''. Primárna efektívne podporovaná operácia je ''vyhľadávanie'': pri zadaní kľúča (napr. meno osoby) nájsť zodpovedajúcu hodnotu (napr. telefónne číslo tejto osoby). Pracuje vďaka transformácii kľúča [[hašovacia funkcia|hašovacou funkciou]] na ''hashhaš'', číslo, ktoré tabuľka používa na nájdenie požadovanej hodnoty.
 
[[Image:HASHTB08_sk.svg|thumb|362px|right|Malý telefónny zoznam ako hashovaciahašovacia tabuľka.]]
 
Hašovacie tabuľky sa často používajú na implementáciu [[asociatívne pole|asociatívnych polí]], [[množina (informatika)|množín]] a [[rýchla vyrovnávacia pamäť|rýchlych vyrovnávacích]] pamätí (cache). Rovnako ako [[pole (údajová štruktúra)|polia]], hašovacie tabuľky poskytujú vyhľadávanie s konštantným časom [[Notácia veľké O|O]](1) v priemernom prípade, nezávisle na počte položiek v tabuľke. Avšak zriedkavý najhorší prípad môže byť až O(''n''). V porovnaní s inými údajovými štruktúrami asociatívnych polí sú hashovaciehašovacie tabuľky najužitočnejšie pre uloženie veľkého množstva údajov.
 
Hašovacie tabuľky ukladajú údaje na pseudonáhodných miestach, preto prístup k údajom utriedeným spôsobom je veľmi časovo náročná operácia. Iné údajové štruktúry ako [[samovyvažovací binárny vyhľadávací strom|samovyvažovací binárny vyhľadávacie stromy]] sú vo všeobecnosti oveľa pomalšie (keďže zložitosť vyhľadávania majú O(log ''n'')) a sú skôr zložitejšie na implementáciu ako hašovacie tabuľky, ale udržiavajú si neustále utriedenú štruktúru položiek. Pozri [[porovnanie hašovacích tabuliek a samovyvažovacích binárnych vyhľadávacích stromov]].
 
== Prehľad ==
Základné operácie, ktoré hashovaciehašovacie tabuľky vo všeobecnosti podporujú sú:
:<code>vlož(kľúč, hodnota)</code>
:<code>nájdi(kľúč)</code> ktorá vráti <code>hodnotu</code>
Väčšina, ale nie všetky hashovaciehašovacie tabuľky podporujú <code>zmaž(kľúč)</code>. Môžu existovať aj iné služby ako iterovanie tabuľkou, zväčšenie tabuky, vyprázdnenie tabuľky. Niektoré tabuľky umožňujú uloženie viacerých hodnôt pod rovnakým kľúčom.
 
Kľúčom môže byť v podstate čokoľvek -- číslo, reťazec, objekt; niektoré tabuľky ukladajú dokonca aj odkaz na hodnotu. Jedinou požiadavkou je existencia [[hašovacia funkcia|hašovacej funkcie]] pre použité kľúče (pozri nižšie).
Riadok 21:
Pretože počet platných kľúčov je zvyčajne oveľa väčší ako rozsah platných indexov do poľa, je potrebný spôsob konverzie každého kľúča na platný index. Toto vykonáva [[hašovacia funkcia]], čo je funkcia, ktorá berie ako argument kľúč a vracia index do poľa. Indexovaný element poľa by zasa mal obsahovať záznam asociovaný s daným kľúčom.
 
Avšak preto, že existuje viac potenciálnych kľúčov ako indexov do poľa, možno dokázať (?Dirichletovym princípom), že dva alebo viac potenciálnych kľúčov budú mať rovnaký hashhaš; toto sa nazýva ''kolízia''. Hašovacia funkcia by mala byť navrhnutá tak, aby minimalizovala množstvo kolízií pre akýkoľvek vrátený index.
 
Keďže v jednom elemente poľa je možné uložiť iba jednu položku, musí byť použitá stratégia [[Hašovacia tabuľka#Riešenie kolízií|riešenia kolízií]]. Napríklad sa kolízny záznam uloží do nasledujúceho voľného elementu alebo môžu elementy poľa ukladať [[spojový zoznam]] záznamov.
 
Hoci sa nejaké kolízie vyskytnú, s dobrými hašovacími funkciami a tabuľkou plnou asi na 80 %, budú kolízie relatívne zriedkavé a výkon veľmi dobrý, keďže priemerne sa vykoná veľmi málo porovnaní. Avšak ak sa tabuľka príliš zaplní, výkon bude nízky a bude potrebné zväčšiť hashovaciuhašovaciu tabuľku. Zväčšenie tabuľky ([[HashovaciaHašovacia tabuľka#Zmena veľkosti tabuľky|Zmena veľkosti tabuľky]]) znamená, že sa budú musieť znova pridať všetky záznamy.
 
Väčšina implementácií hashovacíchhašovacích tabuliek nie sú [[perzistentná údajová štruktúra|perzistentnými údajovými štruktúrami]] v zmysle, že neexistuje spôsob ako ich aktualizovať a zároveň si udržať prístup k predchádzajúcej kópii hashovacejhašovacej tabuľky (hoci sú perzistentné v zmysle uloženia na disku). Niektoré implementácie hashovacíchhašovacích tabuliek ako tie, ktoré používajú [[VList]], sú perzistentné, ale v praxi sa zriedkavo používajú a nie sú také výkonné ako narmálne hashovaciehašovacie tabuľky kvôli zvýšenému času na indexáciu.
 
== Bežné využitie hashovacíchhašovacích tabuliek ==
HashovacieHašovacie tabuľky sa bežne využívajú pre [[tabuľka symbolov|tabuľky symbolov]], [[Rýchla vyrovnávacia pamäť|rýchle vyrovnávacie pamäte]] a [[množina (informatika)|množiny]].
 
HashovacieHašovacie tabuľky nie sú vo všeobecnosti [[perzistentná údajová štruktúra|perzistentnými údajovými štruktúrami]] v tom zmysle, že neexistuje jednoduchý a vzhľadom na úložný priestor efektívny spôsob, ako aktualizovať hashovaciuhašovaciu tabuľku a zároveň si si udržať prístup k jej predchádzajúcej kópii. Je to však možné implementovaním [[VList]]u, čím sa stane perzistentnou, ale nepriaznivo to ovplyvní výkon. hashovaciehašovacie tabuľky môžu byť „perzistentné“ v inom zmysle - môžu byť uložené na disku. Databázové indexy bežne používajú diskové údajové štruktúry založené na hashovacíchhašovacích tabuľkách.
 
V [[počítačový šach|počítačovom šachu]] sa hashovaciahašovacia tabuľka bežne používa na implementáciu [[transpozičná tabuľka|transpozičnej tabuľky]].
 
== Voľba dobrej hashovacejhašovacej funkcie ==
Dobrá hashovaciahašovacia funkcia má zásadný vplyv na výkon hashovacejhašovacej tabuľky. Kolízie hashushašus sa vo všeobecnosti riešia určitou formou [[lineárne vyhľadávanie|lineárneho vyhľadávania]], takže ak hashovaciahašovacia funkcia zvykne vracať podobné hodnoty, výsledkom bude pomalé vyhľadávanie.
 
Ideálna hashovaciahašovacia funkcia by pri každej zmene jednotlivého bitu kľúča (vrátane rozšírenia a skrátenia kľúča) zmenila polovicu bitov hashuhašu a táto zmena by bola nezávislá na zmenách spôsobených inými bitmi kľúča. Pretože môže byť ťažké navrhnúť dobrú hashovaciuhašovaciu funkciu, alebo ju výpočtovo náročné vykonávať, boli do veľkej miery skúmané stratégie riešenia kolízií, ktoré zmierňujú dopad slabého hashovaciehohašovacieho výkonu. Avšak žiadna z nich nie je taká efektívna ako využitie dobrej hashovacejhašovacej funkcie.
 
Je žiadúce používať rovnakú hashovaciuhašovaciu funkciu pre polia akejkoľvek mysliteľnej veľkosti. Aby sme to dosiahli, index do poľa hashovacejhašovacej tabuľky sa vo všeobecnosti počíta v dvoch krokoch:
#Vypočíta sa všeobecná hodnota hashuhašu, ktorá zaplní veľkosť strojového celého čísla
#Táto hodnota sa redukuje na platný index poľa nájdením jeho [[modulo|modula]] s ohľadom na veľkosť poľa.
Veľkosti poľa hashovacejhašovacej tabuľky sa niekedy volia tak, aby boli [[prvočíslo|prvočíslami]]. Robí sa to, aby sme sa vyhli výskytu spoločných deliteľov hashuhašu a veľkosti tabuľky, ktoré by boli príčinou kolízií po operácii modulo. Ale ani prvočíselná veľkosť tabuľky nie je náhradou za dobrú hashovaciuhašovaciu funkciu.
 
Bežnou alternatívou k prvočíselným veľkostiam je použitie veľkosti, ktorá je [[mocnina čísla dva|mocninou čísla dva]] a dosahovať operáciu modulo maskovaním bitov. Maskovanie bitov býva výpočtovo významne rýchlejšie ako operácia delenia. V každom prípade je dobrý nápad zariadiť, aby všeobecná hodnota hashuhašu bola zostavená pomocou prvočísel, ktoré nezdieľajú spoločných deliteľov (napr. ako [[:en:coprime]]) s dĺžkou tabuľky.
 
Prekvapivo bežným problémom, ktoý sa môže vyskytnúť pri hashovaníhašovaní je ''klastrovanie''. Klastrovanie sa vyskytuje, keď štruktúra hashovacejhašovacej funkcie spôsobuje, že bežne používané kľúče padajú blízko vedľa seba alebo dokonca po sebe do hashovacejhašovacej tabuľky. To môže spôsobiť významné zníženie výkonu ako sa tabuľka plní a používajú sa isté stratégie riešenia kolízií ako lineárne reťazenie.
 
Počas debugovania obsluhy kolízií v hashovacejhašovacej tabuľke je niekedy užitočné použiť hashovacuhašovacu funkciu, ktorá vždy vracia konštantnú hodnotu, napr. 1, ktorá spôsobí kolíziu po takmer každom vložení.
 
V prostrediach, kde sa záškodník môže pokúšať spomaliť algoritmus tým, že zadáva nepriaznivý vstup, býva dobrým riešením [[univerzálne hashovaniehašovanie]], schéma, kde náhodne volíme hashovaciuhašovaciu funkciu na začiatku algoritmu. Pretože záškodník nebude vedieť, akú hashovaciuhašovaciu funkciu používame, nebude vedieť určiť, ktorý vstup je nepriaznivý.
 
== Riešenie kolízií ==
Ak hashovaciahašovacia funkcia vráti pre dva rôzne kľúče rovnaký index, zodpovedajúce záznamy nemožno uložiť na to isté miesto. Keďže je už obsadené, musíme nájsť iné miesto pre uloženie záznamu a zabezpečiť, aby sme ho našli, keď ho neskôr vyhľadáme.
 
Pre predstavu dobrej stratégie riešenia kolízií si predstavte nasledovný výsledok odvodený použitím [[narodeninový paradox|narodeninového paradoxu]]. Aj za predpokladu, že naša hashovaciahašovacia funkcia vracia indexy [[rovnomerné rozdelenie (diskrétne)|rovnomerne rozložené]] v poli aj pre pole s 1 milónom záznamov, existuje 95% pravdepodobnosť aspoň jednej kolízie predtým, ako bude obsahovať 2500 záznamov.
 
Existuje niekoľko techník riešenia kolízií, ale najpoužívanejšími sú ''reťazenie'' a ''otvorené adresovanie''.
Riadok 63:
=== Reťazenie ===
 
[[Image:HASHTB32_sk.svg|thumb|362px|right|Kolízia hashuhašu vyriešená reťazením.]]
 
V najjednoduchšej technike zreťazenej hashovacejhašovacej tabuľky každé miesto v poli odkazuje na [[zreťazený zoznam]] vložených záznamov, pre ktoré hashovaniehašovanie kľúča koliduje na rovnakú hodnotu. Pre vloženie je potrebné nájsť správne miesto a pridať ho na jeden koniec; pre mazanie je potrebn0 preh2ad8vanie zoznamu a odstránenie.
 
Zreťazené hashovaciehašovacie tabuľky majú výhodu v porovnaní s tabuľkami s otvorenou adresáciou, že operácia odstránenia je jednoduchá a zmenu veľkosti tabľky je možné odkladať oveľa dlhšie, pretože výkon sa znižuje oveľa elegantnejšie aj ak je miesto obsadené. Vlastne mnohé zreťazené hashovaciehašovacie tabuľky nepotrebujú zmenu veľkosti vôbec, pretože degradácia výkonu je lineárna so zaplňovaním tabuľky. Napríklad zreťazená hashovaciahašovacia tabuľka obsahujúca dvojnásobok odporúčanej dátovej kapacity by bola priemerne iba asi dvakrát pomalšia ako rovnaká tabuľka s odporúčanou kapacitou.
 
Zreťazené hashovaciehašovacie tabuľky dedia nevýhody spojových zoznamov. Ak sa ukladajú malé záznamy, režijné náklady spojového zoznamu môžu byť významné. Ďalšou nevýhodou je, že prechádzanie spojovým zoznamom má nízky [[lokalita referencie|cache výkon]].
 
Namiesto zoznamov je možné pre reťazenie použíť alternatívne údajové štruktúry. Napríklad použitím [[samovyvažovací binárny vyhľadávací strom|samovyvažovacieho stromu]]je možné znížiť teoretický čas najhoršieho prípadu z O(''n'') na O(log ''n''). Ale preto, že každý zoznam by mal byť krátky, tento prístup zvyčajne nevedie k zvýšeniu výkonu, iba ak by bola tabuľka navrhnutá na fungovanie pri plnej kapacite alebo vykazovala nazvyčajne vysoké množsto kolízií. Je tiež možné použiť [[dynamické pole|dynamické polia]] pre zníženie režijných nákladov a zvýšenie výkonnosti cache pri malých záznamoch.
Riadok 77:
== Otvorené adresovanie ==
 
[[Image:HASHTB12_sk.svg|thumb|362px|right|HashHaš collision resolved by linear probing (interval=1).]]
 
HashovacieHašovacie tabuľky s otvoreným adresovaním môžu ukladať záznamy priamo v poli. Kolízia hashuhašu sa rieši ''skúšaním'' - prehľadávaním alternatívnych miest v poli (''skúšacia sekvencia''), pokým sa buď nenájde cieľový záznam alebo voľné miesto, čo indikuje, že sa v tabuľke dený kľúč nenachádza. Medzi známe skúšacie sekvencie patria:
:[[lineárne hľadanie]]
::v ktorom je interval medzi skúškami fixný -- často 1,
:[[kvadratické skúšanie]]
::v ktorom interval medzi skúškami rastie lineárne (takže indexy sú opísané kvadratickou funkciou),
:[[dvojité hashovaniehašovanie]]
::v ktorom je interval medzi skúškami fixný pre každý záznam, ale počíta sa inou hashovacouhašovacou funkciou
 
Hlavné rozdiely medzi týmito metódami sú, že lineárne hľadanie má najlepší cache výkon ale je najcitlivejšie na klastrovanie, kým dvojité hashovaniehašovanie má nízky cache výkon ale nevykazuje v podstate žiadne klastrovanie; kvadratické hashovaniehašovanie spadá v oboch oblastiach dostredu. Dvojité hashovaniehašovanie tiež môže vyžadovať viac výpočtov ako iné formy hashovaniahašovania.
 
Kritický vplyv na výkon hashovacejhašovacej tabuľky s otvoreným adresovaním má ''koeficient zaťaženia''; pomer miest v poli, ktoré sa používajú. Ako sa zaťaženie zvyšuje k 100 %, stúpa dramaticky aj počet súšok, ktoré môžu byť potrebné na nájdenie alebo vloženie daného kľúča. Keď sa tabuľka zaplní, skúšacie algoritmy dokonca nemusia skončiť. Aj s dobrou hashovacouhašovacou funkciou je koeficient zaťaženia zvyčajne obmedzený na 80 %. Nevhodná hashovaciahašovacia funkcia môže vykazovať názky výkon aj pri nízkych zaťaženiach tým, že spôsobuje výrazné klastrovanie. Čo sposobuje, že hashovaciehašovacie funkcie klastrujú nie je dobre známe a je ľahké neúmyselne napísať hashovaciuhašovaciu funkciu, ktorá spôsobuje ťažké klastrovanie.
 
== Otvorené adresovanie versus reťazenie ==