Dokonalé hašování

Dokonalá (perfektní) hašovací funkce množiny S je taková hašovací funkce, která mapuje vzdálené elementy v množině S na množinu celých čísel tak, aby nedošlo ke kolizím klíčů. Dokonalá hašovací funkce podporuje mnoho aplikací stejných jako jiné hašovací funkce, ale bez nutnosti implementace řešení kolize. Použití dokonalé hašovací funkce je vhodné v takových případech, kdy jsou data, která chceme zmapovat, uložena v úložišti, ve kterém se často hledá a méně často se do něj zapisuje. Dokonalé hašování s sebou nese ale poměrně vysokou složitost a tím snižuje výkon aplikace. Matematickým výrazem lze dokonalou hašovací funkci vyjádřit jako úplné prosté zobrazení.

Vlastnosti a použití

Dokonalá hašovací funkce specifické množiny S může být vyhodnocena v konstantním čase a s hodnotami v malém rozsahu ji lze najít algoritmem s využitím náhodnosti v počtu operací, který odpovídá velikosti množiny S. Jakákoli dokonalá hašovací funkce vhodná pro použití s hašovací tabulkou vyžaduje nejméně takový počet bitů, který odpovídá velikosti množiny S.

Dokonalou hašovací funkci s hodnotami v omezeném rozsahu lze použít pro efektivní funkce vyhledávání tak, že klíče z množiny S (nebo jiné přidružené hodnoty) se vkládají do tabulky indexované výstupní funkcí. Použití dokonalé hašovací funkce je vhodné pro velké množiny, které jsou často kladeny dotazy a které bývají zřídka aktualizovány, protože jakákoli modifikace množiny S vede k nedokonalé hašovací funkci. Řešení, která aktualizují hašovací funkci při každé změně množiny, lze souhrnně nazvat jako dynamické dokonalé hašování. Metody dynamického dokonalého hašování jsou však relativně složité na implementaci. Jednoduchou alternativu dokonalého hašování, která také podporuje dynamické aktualizace, představuje kukaččí hašování. Další algoritmus dokonalého hašování se nazývá Cormackovo hašování, v dnešní době používaný nejčastěji při vyhledávání elementů na externích médiích (například CD nosiče).

Minimální dokonalá hašovací funkce

Minimální dokonalá hašovací funkce je taková dokonalá hašovací funkce, která mapuje n klíčů do n po sobě jdoucích n čísel - obvykle od 0 do n-1 nebo od 1 do n. Formálnějším výrazem: Nechť j a k jsou prvky konečné množiny K. F je minimální dokonalá hašovací funkce právě tehdy, když pro F(j)=F(k) platí j=k a existuje celé číslo takové, že rozsah funkce F je od a do a+|K|-1. Bylo dokázáno, že schéma minimálního dokonalého hašování vyžaduje nejméně 1.44 bitů na klíč. Nejlepší známá schémata minimálního dokonalého hašování používají přibližně 2.6 bitů na klíč.

Minimální dokonalá hašovací funkce F zachovává pořadí, pokud se klíče množiny předávají v nějakém pořadí a₁, a₂, ..., a_n a pro jakékoli klíče a_j a a_k, kde j je menší než k, platí F(a_j)<F(a_k). Minimální dokonalé hašovací funkce zachovávající pořadí vyžadují k reprezentaci nezbytně Ω(n log n) bitů.

Minimální dokonalá hašovací funkce F je monotónní, pokud zachovává lexikografické pořadí klíčů. V tomto případě, hodnota funkce odpovídá jednoduše pozici každého klíče v seřazené množině všech klíčů. Pokud klíče, které mají být zahašovány, jsou uchovány v seřazeném poli, je možné uchovávat malé množství dodatečných bitů na klíč v datové struktuře, kterou lze použít k rychlému vypočítání hašovaných hodnot.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Perfect hash function na anglické Wikipedii.

Související články

• Kryptografie (šifrování)
• Hašovací funkce
• Hašovací tabulka
• Cormackovo hašování (jedna z metod dokonalého hašování)
• Kryptografická hašovací funkce