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

preklep
No edit summary
(preklep)
[[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 potrebn0potrebné preh2ad8vanieprehľadávanie zoznamu a odstránenie.
 
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.
48

úprav