Co je asociativní pole?

Asociativní pole, také nazývané hashova tabulka nebo hashova mapa, je podobné standardnímu poli s tím rozdílem, že index pole může být řetězec namísto celého čísla. V mnoha databázových aplikacích a v jiných programech, které se zabývají velkým množstvím dat, je asociativní pole důležitým prvkem, který pomáhá efektivně třídit a přistupovat k informacím. Jádrem asociativního pole je standardní pole, které je indexováno pomocí celých čísel, jak by tomu bylo normálně. Speciální algoritmus nazývaný hashovací funkce převede řetězcový index na celočíselný index a najde hodnotu. Jedná se o konzistentní převod, takže skutečný celočíselný index se nikdy nemusí ukládat, ale místo toho se vypočítává z řetězce podle potřeby pokaždé.

Terminologie použitá při odkazu na asociativní pole se může mírně lišit od terminologie používané při mluvení o normálním poli. To, co by se normálně nazývalo indexem - číselné umístění prvku uvnitř pole - se nazývá klíč. Data spojená s klíčem se nazývají hodnota. To znamená, že v asociativním poli je klíč spojen s hodnotou, která koreluje s indexem odkazujícím na prvek ve standardním poli ve struktuře dat.

Srdcem každé asociativní soustavy je hašovací funkce. Toto je algoritmus používaný k určení číselného indexu hodnoty na základě klíče. Existuje několik typů hash funkcí, některé určené pro práci s klávesami, které jsou celá čísla, a jiné určené pro práci s klávesami, které jsou řetězce. V případě celočíselného klíče je oblíbenou metodou rozdělit hodnotu klíče velikostí pole a použít zbytek divize k získání, doufejme, jedinečné hodnoty indexu.

Funkce hash může být mnohem složitější pro klíče, které jsou řetězce. Některé metody zahrnují přidání číselné hodnoty každého znaku v řetězci a poté jeho rozdělení nějakým číslem, nebo použití pouze prvních několika znaků řetězce k získání jedinečného čísla. Existuje mnoho způsobů, jak odvodit číslo z řetězce znaků.

Při řešení velkého množství párů klíč-hodnota v asociativním poli se jeden problém, který může nastat, nazývá kolize. Kolize nastane, když je celočíselný index odvozený z klíče identický s celočíselným indexem jiného klíče. Tyto dva klíče pak efektivně ukazují na stejný index v poli hodnot. Kolize má různá řešení, hlavně proto, že má vysokou pravděpodobnost, že se stane ve většině praktických aplikací.

Jedním z řešení kolize je mít každý index hodnot ve skutečnosti propojený seznam, takže když se více než jeden klíč přeřadí na toto umístění indexu, umístění může obsahovat více než jednu hodnotu. Tomu se říká řetězení a jedná se o jednoduchý způsob řešení kolize, i když to také může zpomalit čas potřebný k získání informací. Jiná metoda řešení kolize se nazývá lineární sondování. Když dojde ke kolizi, lineární sondování pracuje pohybem v poli hodnot, dokud není nalezen nepoužitý index. Toto řešení může pomoci udržet data rovnoměrně distribuovaná v asociativním poli, ale také může zvýšit dobu potřebnou k vyhledání hodnoty.