Kukaččí hašování

Z Multimediaexpo.cz

Nemáte oprávnění „upravit tuto stránku“. Důvod:

Můžete si prohlédnout a zkopírovat zdrojový kód této stránky:

[[Image:cuckoo.png|thumb|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í [[Hašovací kolize|kolizí]] hodnot [[hašovací funkce]] v [[Hašovací tabulka|hašovací tabulce]]. Kukaččí hašování bylo poprvé popsáno Rasmusem Paghem a Flemmingem Friche Rodlerem v 2001.<ref name="Cuckoo">{{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 }} </ref> Jméno metody je odvozeno od chování některých druhů [[kukačka| 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ý [[hašovací klíč|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 [[nekonečný_cyklus | zacyklí]]. V tom případě je hašovací tabulka přehašována [[In-place_algoritmus | na místě]]<ref>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."</ref> za použití nových [[hašovací funkce | 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%C3%A1 slo%C5%BEitost]]). 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<ref name="Cuckoo" />, 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%. <ref>{{citation|first=Reinhard|last=Kutzelnigg|url=http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/art icle/viewFile/590/1710|contribution=Bipartite random graphs and cuckoo hashing|title=Fourth Colloquium on Mathematics and Computer Science|series=Discrete Mathematics and Theoretical Computer Science|year=2006|volume=AG|pages=403–406}}.</ref> ==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á struktura|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.{{Chybí zdroj|date=February 2011}} Článek od Zukowski et al.<ref>{{cite paper | last=Zukowski | first=Marcin | coauthors=Heman, Sandor; Boncz, Peter | title=Architecture-Conscious Hashing | publisher=Proceedings of the International Workshop on Data Management on New Hardware (DaMoN) | date=2006-06 | doi= | url=http://www.cs.cmu.edu/~damon2006/pdf/zukowski06archconscioushashing.pdf | format=pdf | id= | accessdate=2008-10-16}}</ref> ukázal, že kukaččí hašování je mnohem rychlejší než [[Hašovací tabulka#Separátní řetězení|zřetězené hašování]] pro malé hašovací tabulky umístěné v [[CPU cache|cache]] na moderních procesorech. Kenneth Ross<ref>{{cite paper | last=Ross | first=Kenneth | title=Efficient Hash Probes on Modern Processors | publisher=IBM Research Report RC24100 | date=2006-11-08 |url=http://domino.research.ibm.com/library/cyberdig.nsf/papers/DF54E3545C82E8A585257222006FD9A2/$File/rc24 100.pdf | format=pdf | id=RC24100 | accessdate=2008-10-16 }}</ref> 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,<ref>{{Cite book | title=Fast and Compact Hash Tables for Integer Keys | first1=Nikolas | last1=Askitis | year=2009 | isbn=978-1-920682-72-9 | url=http://crpit.com/confpapers/CRPITV91Askitis.pdf | pages=113–122 | journal=Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) | volume=91}}</ref>, kde její chování porovnával vůči alternativním hašovacím schémám. Přehled od [[Michael Mitzenmacher|Mitzenmachera]]<ref>{{cite paper | last=Mitzenmacher | first=Michael | authorlink=Michael Mitzenmacher|title=Some Open Questions Related to Cuckoo Hashing | Proceedings of ESA 2009 | date=2009-09-09|url=http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf | format=pdf | accessdate=2010-11-10 }}</ref> 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 == <references /> * [http://www.ru.is/faculty/ulfar/CuckooHash.pdf A cool and practical alternative to traditional hash tables], U. Erlingsson, M. Manasse, F. Mcsherry, 2006. * [http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf Cuckoo Hashing for Undergraduates, 2006], R. Pagh, 2006. * [http://mybiasedcoin.blogspot.com/2007/06/cuckoo-hashing-theory-and-practice-part.html Cuckoo Hashing, Theory and Practice] (Part 1, [http://mybiasedcoin.blogspot.com/2007/06/cuckoo-hashing-theory-and-practice-part_15.html Part 2] and [http://mybiasedcoin.blogspot.com/2007/06/cuckoo-hashing-theory-and-practice-part_19.html Part 3]), Michael Mitzenmacher, 2007. * {{cite conference | last = Naor | first = Moni | coauthors = Segev, Gil; Wieder, Udi | author2-link = http://www.wisdom.weizmann.ac.il/~gils/ | title = History-Independent Cuckoo Hashing | booktitle = International Colloquium on Automata, Languages and Programming (ICALP) | place = Reykjavik, Iceland | date = 2008 | url = http://www.wisdom.weizmann.ac.il/~naor/PAPERS/cuckoo_hi_abs.html | accessdate = 2008-07-21 }} ==Externí zdroje== * [http://sourceforge.net/projects/cuckoo-cpp/ Cuckoo hash map written in C++] * [http://www.theiling.de/projects/lookuptable.html Static cuckoo hashtable generator for C/C++] * [http://lmonson.com/blog/?p=100 Cuckoo hashtable written in Java] * [http://github.com/joacima/Cuckoo-hash-map/blob/master/CuckooHashMap.java Generic Cuckoo hashmap in Java] {{Článek z Wikipedie}} [[Kategorie:Hašování|Tabulka]] [[Kategorie:Vyhledávací algoritmy]] [[Kategorie:Datové struktury]]

Návrat na stránku „Kukaččí hašování“.