https://www.512.cz/index.php?action=history&feed=atom&title=Rozptylov%C3%A9_tabulky_s_vn%C4%9Bj%C5%A1%C3%ADm_%C5%99et%C4%9Bzen%C3%ADm 2026-10-20T15:32:49Z Historie editací této stránky MediaWiki 1.17.0 https://www.512.cz/index.php?title=Rozptylov%C3%A9_tabulky_s_vn%C4%9Bj%C5%A1%C3%ADm_%C5%99et%C4%9Bzen%C3%ADm&diff=480&oldid=prev 2016-08-22T14:46:31Z

<p>Založena nová stránka: Při velkém množství možných hodnot klíče oproti množství ukládaných prvků (typicky řetězec klíčem) např. tabulka slov podle prvního písmena, není vhodn...</p> <p><b>Nová stránka</b></p><div>Při velkém množství možných hodnot klíče oproti množství ukládaných prvků (typicky řetězec klíčem)<br /> např. tabulka slov podle prvního písmena,<br /> není vhodné či možné použít tabulku s přímým adresováním.<br /> <br /> Použijeme tedy '''rozptylovou funkci''', která množinu klíčů transformuje na množinu celých čísel z menšího rozsahu, aby bylo využití pole dostatečně efektivní.<br /> Tato čísla jsou pak indexy v poli.<br /> '''Více klíčů''' se tím ale zobrazí na '''stejný index'''.<br /> Pokud pak potřebujeme uložit dva prvky se stejným indexem (tedy dojde ke kolizi), můžeme použít '''vnitřní''' nebo '''vnější řetězení'''. Ke kolizi dojde i při použití přímého adresování.<br /> <br /> Při '''vnitřním řetězení''' se kolidující prvek ukládá na jiné volné místo v tomtéž poli a ke stávajícímu je uložen index tohoto místa. Docílíme tím vetší paměťové efektivity, ale komplikuje se ukládání dalších prvku, jejichž místo jsme takto obsadili.<br /> <br /> Druhým způsobem je '''vnějším řetězení''', kdy je vyhrazeno další místo pro kolidující prvky a opět jsou ukládány odkazy. Případně lze k položkám tabulky připojit spojové seznamy a do nich ukládat všechny položky pro daný index.<br /> <br /> Ve všech případech se zvyšuje složitost, protože prohledávání seznamu má složitost O(n).</div>

81.201.58.135