Kukaččí hašování

Z Multimediaexpo.cz

Příklad kukaččího hašování. Šipky ukazují alternativní umístění pro každý klíč. Nová položka by byla vložena na pozici A tak, že A se přesune na svou alternativní pozici teď zabranou B. Proto se B přesune na svou alternativní pozici, která je teď prázdná. Vložení nového prvku na pozici H by se nepodařilo: protože H je částí cyklu (spolu v W), nový prvek bude zase přemísťován.

Kukaččí hašování (en: Cuckoo hashing) je schéma v programování pro řešení kolizí hodnot hašovací funkce v hašovací tabulce. Kukaččí hašování bylo poprvé popsáno Rasmusem Paghem a Flemmingem Friche Rodlerem v 2001.^[1] Jméno metody je odvozeno od chování některých druhů kukaček, u kterých mládě po vylíhnutí vyhodí původní vajíčka nebo mláďata z hnízda.

Teorie

Základní myšlenka je použít dvě hašovací funkce místo jedné. To poskytne dvě možné umístění v hašovací tabulce pro každý klíč. V jedné obecně užívané variantě algoritmu je hašovací tabulka rozdělena na dvě menší stejně veliké tabulky a každá hašovací funkce indexuje do jedné z nich. Když je vkládán nový klíč, použije se hladový algoritmus: nový klíč se vloží na jedno ze svých dvou možných umístění, přičemž "vykopne", tj. nahradí jiný klíč, který tam je případně umístěn. Tento nahrazovaný klíč je pak umístěn na svoje alternativní umístění, kde případně opět vykopne prvek tam síslící. Přemísťování pokračuje, dokud se nenajde volná pozice anebo metoda se zacyklí. V tom případě je hašovací tabulka přehašována na místě^[2] za použití nových hašovacích funkcí Vyhledání potřebuje skontrolovat pouze dvě pozice v hašovací tabulce, což zabere konstantní čas v nejhorším případě (viz Asymptotická složitost). Tím se liší od mnoha jiných hašovacích metod, které nemají konstantní omezení časové složitosti pro nejhorší případ vyhledávání. Dá se ukázat, že vkládání do hašovací tabulky uspěje v konstantním očekávaném čase^[1], i když zahrneme potřebu přebudování tabulky, pokud je počet klíčů menší než polovina kapacity tabulky, tj. faktor naplnění je pod 50%. ^[3]

Zobecnění a aplikace

Zobecnění kukaččího hašování, které používá víc než 2 hašovací funkce, bude efektivně využívat větší část kapacity tabulek, ale za cenu menší rychlosti vkládání a vyhledávání. Použití již tří hašovacích funkcí zvyšuje naplnění na 91%. Jiná generalizace kukaččího hašování používá víc než 1 klíč na pozici. Už použití dvou klíčů na pozici dovoluje faktor naplnění přes 80%. Jiné algoritmy, které používají víc hašovacích funkcí, zahrňují Bloomův filtr. Kukaččí hašování lze použít na implementaci datové struktury ekvivalentní Bloomovu filtru. Zjednodušená generalizace kukaččího hašování (viz CPU cache, CPU cache#Asociativita, en: skewed-associative cache) se používá v některých CPU cache.^[zdroj ?] Článek od Zukowski et al.^[4] ukázal, že kukaččí hašování je mnohem rychlejší než zřetězené hašování pro malé hašovací tabulky umístěné v cache na moderních procesorech. Kenneth Ross^[5] ukázal, že vícepoložková verze kukaččího hašování (varianty, které používají pozice s více než jednou položkou) je rychlejší než konvenční metody taky pro velké hašovací tabulky, pokud je zaplnění vysoké. Výkonnost vícepoložkové kukaččí hašovací tabulky byla zkoumána dále Askitisem,^[6], kde její chování porovnával vůči alternativním hašovacím schémám. Přehled od Mitzenmachera^[7] uvádí otevřené problémy v souvislosti s kukaččím hašováním v roce 2009.

Související články

• Perfektní hašování
• Lineární zkoušení
• Kvadratické zkoušení
• Dvojité hašování
• Hašovací kolize
• Hašovací funkce

Reference

1. ↑ ^{1,0 1,1} {{cite paper | last=Pagh | first=Rasmus | coauthors=Rodler, Flemming Friche | title=Cuckoo Hashing | date=2001 | doi=10.1.1.25.4189 | url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4189 | format=PDF, PS | accessdate=2008-10-16 }}
2. ↑ Pagh and Rodler: "There is no need to allocate new tables for the rehashing: We may simply run through the tables to delete and perform the usual insertion procedure on all keys found not to be at their intended position in the table."
3. ↑ .
4. ↑
5. ↑
6. ↑
7. ↑

• A cool and practical alternative to traditional hash tables, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
• Cuckoo Hashing, Theory and Practice (Part 1, Part 2 and Part 3), Michael Mitzenmacher, 2007.

Externí zdroje

• Cuckoo hash map written in C++
• Static cuckoo hashtable generator for C/C++
• Cuckoo hashtable written in Java
• Generic Cuckoo hashmap in Java