Hašovací funkce

Z Multimediaexpo.cz

Hašovací funkce je matematická funkce (resp. algoritmus) pro převod vstupních dat do (relativně) malého čísla. Výstup hašovací funkce se označuje výtah, miniatura, otisk, fingerprint či hash (česky též někdy jako haš). Hašovací funkce se většinou používají k rychlejšímu prohledávání tabulky nebo pro porovnávání dat – například pro hledání položek v databázi, odhalování duplicitních nebo podobných záznamů ve velkém souboru, hledání podobných úseků DNA sekvencí apod.

Obsah

Vlastnosti

Mezi hlavní vlastnosti této funkce patří:

  1. jakékoliv množství vstupních dat poskytuje stejně dlouhý výstup (otisk),
  2. malou změnou vstupních dat dosáhneme velkou změnu na výstupu (tj. výsledný otisk se od původního zásadně na první pohled liší),
  3. z hashe je prakticky nemožné rekonstruhovat původní text zprávy,
  4. v praxi je vysoce nepravděpodobné, že dvěma různým zprávám odpovídá stejný hash, jinými slovy pomocí hashe lze v praxi identifikovat právě jednu zprávu (ověřit její správnost).

Popis

Formálně jde o funkci h, která převádí vstupní posloupnost bitů (či bytů) na posloupnost pevné délky n bitů. Z definice plyne existence kolizí, to znamená dvojic vstupních dat (x,y), x ≠ y, takových, že h(x) = h(y), tj. dvojice různých vstupních dat může mít stejný otisk. Kolize jsou nežádoucí, ale v principu se jim nelze vyhnout, protože počet možných různých vstupních zpráv je větší než počet možných různých otisků. Vhodnou volbou funkce lze snížit pravděpodobnost, že nastane kolize pro podobná data. Cílem je tedy dosáhnout co nejvyšší pravděpodobnosti, že dvě zprávy se stejným otiskem jsou stejné.

Perfektní hašování

Perfektní (dokonalé) hašování (perfect hashing) je specifická varianta hašování. Předpokládejme, že máme množinu klíčů S. Potom můžeme najít takovou hašovací funkci, která pro danou množinu nebude mít ani jednu kolizi. Perfektní hašování se dělí na statické a dynamické, podle toho, zda se množina S v době existence perfektní hašovací funkce mění.

Související články

Externí odkazy

Citováno z „http://ww.multimediaexpo.cz/mmecz/index.php/Ha%C5%A1ovac%C3%AD_funkce“