Jenkinsova hashovací funkce

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. února 2019; kontroly vyžadují 3 úpravy .
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.

Hashovací funkce

jeden po druhém

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.

lookup2

Funkce lookup2 byla přechodnou verzí funkce one-at-a-time.

lookup3

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.

Odkazy

  1. Bob Jenkins, zdrojový kód lookup3.c . Od 16. dubna 2009.