Hašovací tabulka

Z Wikipedie, otevřené encyklopedie

Malý telefonní seznam jako hašovací tabulka
Malý telefonní seznam jako hašovací tabulka

Hašovací tabulka je datová struktura, která asociuje hašovací klíče s odpovídajícími hodnotami. Hodnota klíče je spočtena z obsahu položky podle takového pravidla (viz hašovací funkce), aby klíč byl co nejjednoznačněji určen, tj. aby pravděpodobnost přiřazení stejného klíče dvěma a více rozdílným položkám byla co nejnižší a aby rozptyl hodnot klíčů pro dvě obsahově blízké položky byl co nejvyšší.

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 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 vhodné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 zdola omezenou na O(1).

[editovat] Podívejte se také na

Perfektní hašovaní (Cormack)