Hašovacia tabuľka: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
Bez shrnutí editace |
preklep |
||
Riadok 65:
[[Image:HASHTB32_sk.svg|thumb|362px|right|Kolízia hašu vyriešená reťazením.]]
V najjednoduchšej technike zreťazenej hašovacej tabuľky každé miesto v poli odkazuje na [[zreťazený zoznam]] vložených záznamov, pre ktoré haš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
Zreťazené haš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é haš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á haš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.
|