Hašovacia tabuľka: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
opravil som sh začiatku textu |
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 ''
[[Image:HASHTB08_sk.svg|thumb|362px|right|Malý telefónny zoznam ako
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ú
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é
:<code>vlož(kľúč, hodnota)</code>
:<code>nájdi(kľúč)</code> ktorá vráti <code>hodnotu</code>
Väčšina, ale nie všetky
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ý
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ť
Väčšina implementácií
== Bežné využitie
V [[počítačový šach|počítačovom šachu]] sa
== Voľba dobrej
Dobrá
Ideálna
Je žiadúce používať rovnakú
#Vypočíta sa všeobecná hodnota
#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
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
Prekvapivo bežným problémom, ktoý sa môže vyskytnúť pri
Počas debugovania obsluhy kolízií v
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
== Riešenie kolízií ==
Ak
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
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
V najjednoduchšej technike zreťazenej
Zreťazené
Zreťazené
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|
:[[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é
::v ktorom je interval medzi skúškami fixný pre každý záznam, ale počíta sa inou
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é
Kritický vplyv na výkon
== Otvorené adresovanie versus reťazenie ==
|