Hašovací tabulka
From Wikipedia, the free encyclopedia
Hašovací tabulka (popřípadě hashovací tabulka nebo hešovací tabulka) je vyhledávací datová struktura, která asociuje hašovací klíče s odpovídajícími hodnotami. Hodnota klíče je spočtena z obsahu položky pomocí nějaké hašovací funkce. Obvykle požadujeme nebo se alespoň snažíme, aby výpočet funkce byl rychlý, vypočítané klíče byly náhodné a rovnoměrně rozdělené mezi indexy tabulky a aby podobné hodnoty měly vzdálené klíče.[zdroj?!]
Využití je např. pro rychlé vyhledávání položky v poli nebo v jiném homogenním datovém typu. Pomocí hašovací funkce přiřazujeme hodnotě klíče index (ukazatel) do homogenní datové struktury. Při zápisu obsahu položky zapíšeme položku na odpovídající místo. Pokud je obsazeno, pak pomocí vhodného algoritmu přiřadíme pro položku další volný index. Při vyhledávání položky spočteme s pomocí klíče index hledané položky. Pokud již bylo odpovídající místo přepsáno položkou s jiným klíčem, opět podle stejného algoritmu prohledáváme další položky. Při správně zvolené velikosti (počtu položek) homogenní datové struktury a vhodně zvolené hašovací funkci má tento algoritmus složitost v průměrném (tj. očekávaném) případě shora omezenou na O(1).