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

Skočit na navigaci Skočit na vyhledávání
Pridaných 56 bajtov ,  pred 16 rokmi
opravil som sh začiatku textu
Bez shrnutí editace
(opravil som sh začiatku textu)
{{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 [[hashovaciahašovacia funkcia|hashovacouhašovacou funkciou]] na ''hash'', číslo, ktoré tabuľka používa na nájdenie požadovanej hodnoty.
 
[[Image:HASHTB08_sk.svg|thumb|362px|right|Malý telefónny zoznam ako hashovacia tabuľka.]]
 
HashovacieHašovacie tabuľky sa často používajú na implementáciu [[asociatívne pole|asociatívnych polí]], [[množina (informatika)|množín]] a [[cacherýchla vyrovnávacia pamäť|rýchlych vyrovnávacích]] pamätí (cache). Rovnako ako [[pole (údajová štruktúra)|polia]], hashovaciehaš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ú hashovacie tabuľky najužitočnejšie pre uloženie veľkého množstva údajov.
 
HashovacieHaš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 omnohooveľ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 hashovaciehašovacie tabuľky, ale udržiavajú si neustále utriedenú štruktúru položiek. Pozri [[porovnanie hashovacíchhašovacích tabuliek a samovyvažovacích binárnych vyhľadávacích stromov]].
 
== Prehľad ==
Väčšina, ale nie všetky hashovacie 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 [[hashovaciahašovacia funkcia|hashovacejhašovacej funkcie]] pre použité kľúče (pozri nižšie).
 
HashovacieHašovacie tabuľky používajú pole, ktoré sa tiež niekedy mätúco nazýva ''hashovaciahašovacia tabuľka''. Každý element poľa môže obsahovať jeden pár kľúč-hodnota nazývaný ''záznam''.
 
Pretože počet platných kľúčov je zvyčajne oeľaoveľ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 [[hashovaciahaš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, je možnémožno dokázať (?Dirichletovym princípom), že dva alebo viac potenciálnych kľúčov budú mať rovnaký hash; toto sa nazýva ''kolízia''. HasovaciaHaš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 [[HashovaciaHaš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 hashovacímihaš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ť hashovaciu tabuľku. Zväčšenie tabuľky ([[Hashovacia 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í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 hashovacej tabuľky (hoci sú perzistentné v zmysle uloženia na disku). Niektoré implementácie hashovací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 hashovacie tabuľky kvôli zvýšenému času na indexáciu.
131 809

úprav

Navigačné menu