Jenkinsovy hashovací funkce | |
---|---|
Poprvé zveřejněno | 1997 |
Typ | hashovací funkce |
Jenkinsovy hašovací funkce jsou skupinou univerzálních hašovacích funkcí pro klíče s proměnnou délkou vyvinuté Bobem Jenkinsem. Funkce mohou být také použity jako kontrolní součet pro detekci náhodného poškození dat nebo pro detekci identických záznamů v databázi . Popis funkce byl poprvé zveřejněn v roce 1997.
Výše uvedený funkční text je převzat z webové stránky Boba Jenkinse a je rozšířenou verzí publikovanou autorem v časopise Dr. Dobbs' Journal.
uint32_t jenkins_one_at_a_time_hash ( nepodepsaný znak * klíč , size_t len ) { uint32_t hash , i ; for ( hash = i = 0 ; i < len ; ++ i ) { hash += klíč [ i ]; hash += ( hash << 10 ); hash ^= ( hash >> 6 ); } hash += ( hash << 3 ); hash ^= ( hash >> 11 ); hash += ( hash << 15 ); vrátit hash ; }Obrázek vpravo ukazuje lavinový efekt funkce.
Každý z 24 řádků odpovídá jednomu bitu ve 3bajtovém klíči na vstupu a každý z 32 sloupců odpovídá bitu ve výstupním hash. Barvy označují, jak dobře vstupní bit ovlivňuje daný výstupní bit: zelený čtverec označuje dobré míchání, žlutý čtverec označuje malé míchání a červený značí žádné míchání. Jak je vidět z obrázku, pouze několik bitů v posledním bajtu vstupního klíče je volně smícháno s několika bity výsledku.
Funkce lookup2 byla přechodnou verzí funkce one-at-a-time.
Funkce lookup3 rozděluje vstup na bloky po 12 bajtech (96 bitů). [1] Toto chování může být vhodnější, když je rychlost důležitější než jednoduchost. Mějte na paměti, že nárůst výkonu u této varianty hash je pravděpodobný pouze u velkých klíčů a že zvýšená složitost implementace může naopak způsobit zpomalení výkonu. Například kvůli skutečnosti, že kompilátor nemusí být schopen nahradit funkci inline.
Hashovací funkce | |
---|---|
obecný účel | |
Kryptografický | |
Funkce generování klíčů | |
Kontrolní číslo ( srovnání ) | |
Hashe |
|