Co je to asociativní pole?

Asociativní pole, také nazývané hashovací tabulkou nebo hash mapa, je podobné standardnímu poli, s výjimkou indexu pole může být řetězec místo celého celého 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 zásadním prvkem, který pomáhá efektivnímu třídění a přístupu k informacím. Jádro asociativního pole je standardní pole, které je indexováno s celými čísly, jak by to obvykle bylo. Zvláštní algoritmus s názvem A Hash Function převádí index řetězce do interegerového indexu, aby zjistil hodnotu. Jedná se o konzistentní konverzi, takže skutečný celočíselný index nemusí být nikdy uložen, ale místo toho se pokaždé vypočítá z řetězce. To, co by se normálně nazývalo index - numerické umístění prvku uvnitř pole - se nazýváklíč. Data spojená s klíčem se nazývá hodnota. To znamená, že v rámci asociativního pole je klíč spojen s hodnotou, která koreluje s indexem odkazujícím na prvek ve standardním poli ve struktuře dat.

V srdci každého asociativního pole je funkce hash. Toto je algoritmus použitý k určení numerického indexu hodnoty založené na klíči. Existuje několik typů hashovacích funkcí, některé určené k provozu na klíčích, které jsou celá čísla, a některé navržené tak, aby fungovaly na klíčích, které jsou řetězce. V případě celočíselného klíče je populární metodou rozdělit hodnotu klíče o velikost pole a zbytek divize použít, doufejme, získat jedinečnou hodnotu 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í numerické hodnoty každého znaku do řetězce a poté ji rozdělením určitým číslem,nebo pomocí pouze prvních několik znaků řetězce získáte jedinečné číslo. Existuje mnoho způsobů, jak odvodit číslo z řetězce znaků.

6 Kolize se stane, když je celé číslo indexu odvozeného 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 hodnoty. Existují různá řešení ke srážce, hlavně proto, že má vysokou pravděpodobnost, že se stane ve většině praktických aplikací.

Jedním z řešení kolize je, aby každý index hodnot byl skutečně propojeným seznamem, takže když se více než jeden klíč vyřeší na toto umístění indexu, může umístění držet více než jednu hodnotu. Tomu se nazývá Chaining a je to jednoduchý způsob, jak manipulovat s kolizí, i když také může zpomalit čas potřebný k získání informací. Další metoda řešení kolize se nazývá lineární sondy.Když dojde k kolizi, lineární sondování funguje tak, že se pohybuje po poli hodnoty, dokud není nalezen nevyužitý index. Toto řešení může pomoci udržet data rovnoměrně distribuovaná v asociativním poli, ale také může prodloužit množství času potřebného k vyhledání hodnoty.