Kukaččí hašování

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. 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íč. +more 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. +more Tento nahrazovaný klíč je pak umístěn na svoje alternativní umístění, kde případně opět vykopne prvek tam sídlící. Přemísťování pokračuje, dokud se nenajde volná pozice anebo se metoda zacyklí. V tom případě je hašovací tabulka přehašována na místě za použití nových hašovacích funkcí.

Vyhledání potřebuje zkontrolovat 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, 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%.

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%. +more 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í, zahrnují Bloomův filtr. Kukaččí hašování lze použít na implementaci datové struktury ekvivalentní Bloomovu filtru. +more Zjednodušená generalizace kukaččího hašování (viz CPU cache, Asociativita, en: skewed-associative cache) se používá v některých CPU cache.

Článek od Zukowski et al. 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. +more Kenneth Ross ukázal, že více polož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íce položkové kukaččí hašovací tabulky byla zkoumána dále Askitisem, kde její chování porovnával vůči alternativním hašovacím schématům.

Přehled od Mitzenmachera 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

[url=http://www. ru. +moreis/faculty/ulfar/CuckooHash. pdf]A cool and practical alternative to traditional hash tables[/url] , U. Erlingsson, M. Manasse, F. Mcsherry, 2006. * [url=https://web. archive. org/web/20110615042618/http://www. it-c. dk/people/pagh/papers/cuckoo-undergrad. pdf]Cuckoo Hashing for Undergraduates, 2006[/url], R. Pagh, 2006. * [url=http://mybiasedcoin. blogspot. com/2007/06/cuckoo-hashing-theory-and-practice-part. html]Cuckoo Hashing, Theory and Practice[/url] (Part 1, [url=http://mybiasedcoin. blogspot. com/2007/06/cuckoo-hashing-theory-and-practice-part_15. html]Part 2[/url] and [url=http://mybiasedcoin. blogspot. com/2007/06/cuckoo-hashing-theory-and-practice-part_19. html]Part 3[/url]), Michael Mitzenmacher, 2007.

Externí odkazy

[url=http://sourceforge. net/projects/cuckoo-cpp/]Cuckoo hash map written in C++[/url] * [url=http://www. +moretheiling. de/projects/lookuptable. html]Static cuckoo hashtable generator for C/C++[/url] * [url=https://web. archive. org/web/20140416181902/http://lmonson. com/blog/. p=100]Cuckoo hashtable written in Java[/url] * [url=http://github. com/joacima/Cuckoo-hash-map/blob/master/CuckooHashMap. java]Generic Cuckoo hashmap in Java[/url].

Tabulka Kategorie:Vyhledávací algoritmy Kategorie:Datové struktury