Rozptylové tabulky s vnějším řetězením

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é či možné použít tabulku s přímým adresováním.

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í. Tato čísla jsou pak indexy v poli. Více klíčů se tím ale zobrazí na stejný index. 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í.

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.

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.

Ve všech případech se zvyšuje složitost, protože prohledávání seznamu má složitost O(n).