Verze z 4. 8. 2021, 21:27 editovat RiniXbot (diskuse \| příspěvky) Roboti 66 569 editací m →‎Jiné aplikace: nahrazení hovorového můžou → mohou dle žádosti za použití AWB ← Přejít na předchozí porovnání		Verze z 6. 8. 2021, 12:23 editovat zrušit editaci JAnDbot (diskuse \| příspěvky) Roboti 1 711 609 editací m robot: přidáno {{Autoritní data}}; kosmetické úpravy Přejít na další porovnání →
Řádek 14: Formálně jde o funkci ''h'', která převádí vstupní posloupnost [[bit]]ů (či [[Bajt\|bytů]]) na posloupnost pevné délky ''n'' bitů. Z definice plyne existence ''[[~~Kolize_~~Kolize (informatika)\|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. == Použití == Řádek 21: === Hašovací tabulka === {{Viz též\|hašovací tabulka}} Datová struktura [[hašovací tabulka]] používá hašovací funkci (nebo funkce) na transformaci klíče na index, podle kterého se do tabulky přistupuje. Požaduje se rovnoměrné rozdělení zahašovaných klíčů do rozsahu indexů. Tabulka nemusí být velikosti mocniny dvojky. Tabulka může být v některých aplikacích distribuována na víc počítačů, pak jde o [[Distribuovaná hašovací tabulka\|distribuovanou hašovací tabulku]]. Při tomto použití je důležitá rychlost výpočtu (tj. [[ časová složitost]]) funkce na rozdíl od použití v kryptografii. Často se používá [[modulární aritmetika]] a [[zbytek po dělení]] jako závěrečná operace zajistí číslo v daném rozsahu. Tabulky jsou většinou v operační paměti a v tom případě je rozsah řádově do miliard položek, tj. 32 bitů. Například funkce může vynásobit parametr nějakou hodnotou nesoudělnou s velikostí tabulky a pak spočítat zbytek ([[modulo]]). Řádek 30: === Otisk, signatura === Kontrolní otisk souboru (nebo jiných dat) jako metoda detekce chyb při přenosu nebo ukládání. V tomto případě jde o náhodné a neúmyslné chyby a příkladem metody je [[cyklický redundantní součet]] (CRC). Jiný způsob využití otisků, v tomto kontextu někdy nazývaných signatury, je pro (rychlé) filtrování dat. Pokud chceme nalézt data se stejným klíčem (nebo stejný soubor) k danému klíči ''k'', porovnáme signaturu ''k'' s (předpočítanými) signaturami dat a pokud se neshoduje, můžeme data vyloučit jako určitě nerelevantní. Při shodě máme potenciální kandidáty, které musíme otestovat podrobněji. Výhoda této metody je, že je použitelná na různá data a že signatura může být podstatně menší než data. Příklad tohoto použití jsou seznamy signatur problémových souborů u antivirů a spamových filtrů. Strukturovaná data lze před hašováním [[Serializace\|serializovat]]. Použitím delší signatury nebo více signatur standardního rozsahu 32/64 bitů lze zmenšit pravděpodobnost náhodné shody dat, pokud ta není žádoucí. Speciálně lze použít kryptografickou hašovací funkci (viz dále) nebo její úvodní část, ale tato možnost je pomalejší než jednoúčelové funkce. Pokud nevadí tato malá pravděpodobnost chyby, není nutno při shodě otisku testovat původní "surová" data a tudíž je ani předávat, resp. pamatovat si. Algoritmus [[Algoritmus Rabin-Karp\|Rabin-Karp]] pro [[Algoritmy pro vyhledávání v textu\|vyhledávání v textu]] používá postupné počítání otisků postupujícího textového okna pro zvýšení efektivity. Pojem ''signatura'' se v informatice používá i ve významu [[Datový typ#~~Typová_signatura~~Typová signatura\|typové signatury]]. === Kryptografická hašovací funkce === Řádek 49: == Jiné aplikace == Hašovací funkce se používá jako součást dalších algoritmů, které přímočaře nespadají do tří hlavních výše zmíněných skupin. [[Bloomův filtr]] používá několik funkcí jako indexů do bitové tabulky. Použití otisků dovoluje testovat přesnou shodu. Při hledání podobných dat se počítají několikrát otisky z části dat a hledá se shoda otisků a tedy shoda části dat, která se následně rozšiřuje, např. při hledání podobnosti v DNA. Jiná možnost je z hodnot otisků sestavit [[histogram]] a porovnávat tyto histogramy. V tomto případě speciálně navržené funkce mohou maskovat určité druhy chyb. Takto lze např. porovnávat dokumenty pomocí hašování trojic sousedících slov. Ignorovanou chybou může být prohození slov a to zajistíme ve funkci tak, že nebude záležet na pořadí vstupních slov a funkce bude vracet v těchto případech stejný otisk. Řádek 66: * {{MathWorld\|id=HashFunction}} * [http://www.burtleburtle.net/bob/hash/perfect.html Minimal Perfect Hashing] (anglicky) {{Autoritní data}} [[Kategorie:Matematické funkce]]

Hašovací funkce: Porovnání verzí