Hashovací funkce

Definice

Hashovací funkce je matematická funkce, která na vstupu přijímá libovolně dlouhý binární řetězec a na výstupu vrátí binární řetězec o pevně definované délce n. n ∈ ℕ

$$h: M → \{0,1\}^n$$

Za hodnotou M na vstupu funkce, tzv. zprávu dosazujeme konečně dlouhou posloupnost bitů, která může být reprezentací čísel nebo znaků. Hash se nazývá výstup takovéto funkce, také se jí říká haš, heš či otisk (anglicky hash, digest nebo fingerprint). Vypočítat hash k-bitového vstupního řetězce je možné v čase O(k). Stejný vstup musí vždy poskytnou totožný výstup. Hashováním pak nazýváme proces generování tohoto otisku. Výpočet inverze této funkce většinou není žádoucí.

 

Pokud jste zde hledali druh kanabinoidních drog nejspíše tu nenajdete, to co jste hledali. Hashovací funkce jsou nesmírně užitečné funkce a spektrum jejich využití je opravdu široké. V tomto textu si představíme pouze společné vlastnoti hashovacích funkcí. Nejběžněji se setkáte s následujícícími druhy:

 

U funkcí bychom měli definovat definiční obor a obor hodnot. Protože je prostor domény teoreticky nekonečný, je větší než prostor na který se zobrazuje. V důsledku toho musí existovat řetězce, které se mapují na stejný výstupní řetězec.

 

Ukázka


Aplikace

  • Hash se používá k určení toho, zda jsou dva objekty rovny.
  • Hash se používá především k porovnávání dat bez nutnosti znát data samotná. vyhledávání duplicitních záznamů.
  • Bezpečném ukládání hesel
  • Porovnávání velkých souborů
  • geometrické hašování (rozdělení prostorudo sítě buněk).
  • Integrita dat

Datové struktury: - hašovací tabulky - merkle tree

Aplikace v bezpečnosti Hledání podobných úseků DNA sekvencí v bioinformatice

Související