Просмотр кода страницы Кукушкино хеширование

[[Файл:Cuckoo hashing example.svg|thumb|Пример кукушкиного хеширования. Стрелки показывают альтернативное положение ключа. Новое значение, которое вставляется в ячейку A, выталкивая A в альтернативную ячейку, занимаемую ключом B, значение B переносится в альтернативное место, которое в настоящее время не занято. Вставка нового значения в ячейку H завершается неудачей — H входит в цикл (вместе с W), так что только что вставленный элемент должен быть вытолкнут.]]

'''Кукушкино хеширование''' — алгоритм разрешения [[Коллизия хеш-функции|коллизий]] значений [[хеш-функция|хеш-функций]] в [[хеш-таблица|таблице]] с [[Временная сложность алгоритма|постоянным]] временем выборки в {{не переведено 5|Лучший, худший и средний случаи|худшем случае||worst case analysis}}.

Предложено в 2001 году{{sfn|Pagh, Rodler|2001|с=121–133}}. Название отсылает к поведению некоторых видов [[Кукушковые|кукушек]], когда птенец выталкивает из гнезда яйца или других птенцов; аналогичным образом в алгоритме предусматривается возможность выталкивания старого ключа при вставке нового.

== Операции ==
Кукушкино хеширование является видом {{не переведено 5|Открытая адресация|открытой адресации||open addressing}}, в которой каждая непустая ячейка [[хеш-таблица|хеш-таблицы]] содержит [[Первичный ключ|ключ]] или пару «[[ключ — значение]]». [[Хеш-функция]] используется для определения места для каждого ключа, и его присутствие в таблице (или значение, ассоциированное с ним) может быть найдено путём проверки этой ячейки в таблице. Однако открытая адресация страдает от [[Коллизия хеш-функции|коллизий]], которые случаются, когда более одного ключа попадают в одну ячейку.
Основная идея кукушкиного хеширования заключается в разрешении коллизий путём использования двух хеш-функций вместо одной. Это обеспечивает два возможных положения в хеш-таблице для каждого ключа. В одном из обычных вариантов алгоритма хеш-таблица разбивается на две меньшие таблицы меньшего размера и каждая хеш-функция даёт индекс в одну из этих двух таблиц. Можно обеспечить также для обеих хеш-функций индексирование внутри одной таблицы.

Выборка требует просмотра всего двух мест в хеш-таблице, что требует постоянного времени в худшем случае (''см.'' [[«O» большое и «o» малое]]). Это контрастирует с многими другими алгоритмами хеш-таблиц, которые не обеспечивают постоянное время выборки в худшем случае. Удаление также может быть осуществлено очищением ячейки, содержащей ключ за постоянное время в худшем случае, что осуществляется проще, чем в других схемах, таких как [[линейное зондирование]].

Когда вставляется новый ключ и одна из двух ячеек пуста, ключ может быть помещён в эту ячейку. В случае же, когда обе ячейки заняты, необходимо переместить другие ключи в другие места (или, наоборот, на их прежние места), чтобы освободить место для нового ключа. Используется [[жадный алгоритм]] — ключ помещается в одну из возможных позиций, «выталкивая» любой ключ, который был в этой позиции. Вытолкнутый ключ затем помещается в его альтернативную позицию, снова выталкивая любой ключ, который мог там оказаться. Процесс продолжается, пока не найдётся пустая позиция. Возможен, однако, случай, когда процесс вставки заканчивается неудачей, попадая в [[бесконечный цикл]] или когда образуется слишком длинная цепочка (длиннее, чем заранее заданный порог, зависящий [[логарифм]]ически от длины таблицы). В этом случае хеш-таблица перестраивается {{не переведено 5|Алгоритм на месте|на месте||In-place algorithm}} с новыми [[хеш-функция]]ми:{{цитата|автор=Pagh & Rodler, «Cuckoo Hashing»|Нет необходимости размещения новой таблицы для повторного хеширования — мы можем просто просматривать таблицу для удаления и повторной вставки всех ключей, которые находятся не в той позиции, в которой должны были бы стоять.{{sfn|Pagh, Rodler|2001|с=121–133}} }}

== Вычислительная сложность ==
Ожидаемое время вставки постоянно{{sfn|Pagh, Rodler|2001|с=121–133}}, даже если принимать во внимание возможную необходимость перестройки таблицы, пока число ключей меньше половины ёмкости хеш-таблицы, то есть {{не переведено 5|Коэффициент нагрузки (информатика)|коэффициент загрузки||Load factor (computer science)}} меньше 50 %.

Чтобы обеспечить это, используется теория [[Случайный граф|случайных графов]] — можно образовать [[неориентированный граф]], называемый «кукушкиным графом», в котором вершинами являются ячейки хеш-таблицы, а рёбра для каждого хешируемого соединяют два возможных положения (ячейки хеш-таблицы). Тогда жадный алгоритм вставки множества значений в кукушкину хеш-таблицу успешно завершается тогда и только тогда, когда кукушкин граф для этого множества значений является [[псевдолес]]ом, графом максимум с одним циклом в каждой [[Компонента связности графа|компоненте связности]]. Любой порождённый вершинами подграф с числом рёбер, большим числа вершин, соответствует множеству ключей, для которых число слотов в хеш-таблице недостаточно. Если хеш-функция выбирается случайно, кукушкин граф будет [[Случайный граф|случайным графом]] в {{не переведено 5|Модель Эрдёша – Реньи|модели Эрдёша – Реньи||Erdős–Rényi model}}. С высокой степенью вероятности для случайного графа, в котором отношение числа рёбер к числу вершин ограничено сверху 1/2, граф является псевдолесом и алгоритм кукушкиного хеширования располагает успешно все ключи. Более того, та же теория доказывает, что ожидаемый размер [[Компонента связности графа|компонент связности]] кукушкиного графа мал, что обеспечивает постоянное ожидаемое время вставки{{sfn|Kutzelnigg|2006|с=403–406}}.

== Пример ==
Если даны следующие две хеш-функции:

: <math>h\left(k\right)=k\mod 11</math><br>
: <math>h'\left(k\right)=\left\lfloor\frac{k}{11}\right\rfloor\mod 11</math>

<div style="float:left; margin-right:1em">
{| class="wikitable"
|-
! k !! h(k) !! h'(k)
|-
| 20 || 9 || 1
|-
| 50 || 6 || 4
|-
| 53 || 9 || 4
|-
| 75 || 9 || 6
|-
| 100 || 1 || 9
|-
| 67 || 1 || 6
|-
| 105 || 6 || 9
|-
| 3 || 3 || 0
|-
| 36 || 3 || 3
|-
| 39 || 6 || 3
|}
</div>

Столбцы в следующих двух таблицах показывают состояние хеш-таблицы после вставки элементов.

<div style="float:left; margin-right:1em">
{| class="wikitable"
|-
! colspan="11" | 1. table for h(k)
|-
| || 20 || 50 || 53 || 75 || 100 || 67 || 105 || 3 || 36 || 39
|-
| 0 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 1 ||  ||  ||  ||  || 100 || 67 || 67 || 67 || 67 || 100
|-
| 2 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 3 ||  ||  ||  ||  ||  ||  ||  || 3 || 36 || 36
|-
| 4 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 5 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 6 ||  || 50 || 50 || 50 || 50 || 50 || 105 || 105 || 105 || 50
|-
| 7 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 8 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 9 || 20 || 20 || 53 || 75 || 75 || 75 || 53 || 53 || 53 || 75
|-
| 10 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|}
</div>

<div style="float:left">
{| class="wikitable"
|-
! colspan="11" | 2. table for h'(k)
|-
| || 20 || 50 || 53 || 75 || 100 || 67 || 105 || 3 || 36 || 39
|-
| 0 ||  ||  ||  ||  ||  ||  ||  ||  || 3 || 3
|-
| 1 ||  ||  || 20 || 20 || 20 || 20 || 20 || 20 || 20 || 20
|-
| 2 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 3 ||  ||  ||  ||  ||  ||  ||  ||  ||  || 39
|-
| 4 ||  ||  ||  || 53 || 53 || 53 || 50 || 50 || 50 || 53
|-
| 5 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 6 ||  ||  ||  ||  ||  ||  || 75 || 75 || 75 || 67
|-
| 7 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 8 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|-
| 9 ||  ||  ||  ||  ||  || 100 || 100 || 100 || 100 || 105
|-
| 10 ||  ||  ||  ||  ||  ||  ||  ||  ||  ||
|}
</div>
{{clear}}

=== Циклы ===
Если вы хотите вставить элемент 6, вы получите бесконечный цикл. В последней строке таблицы мы находим ту же начальную ситуацию, что и в начале.

<math>h\left(6\right)=6\mod 11=6</math><br>
<math>h'\left(6\right)=\left\lfloor\frac{6}{11}\right\rfloor\mod 11=0</math><br>
{| class="wikitable"
|-
| ключ || ! colspan="2" | table 1 || ! colspan="2" | table 2
|-
| || старое<BR>значение || новое<BR>значение || старое<BR>значение || новое<BR>значение
|-
| 6 || 50 || 6 || 53 || 50
|-
| 53 || 75 || 53 || 67 || 75
|-
| 67 || 100 || 67 || 105 || 100
|-
| 105 || 6 || 105 || 3 || 6
|-
| 3 || 36 || 3 || 39 || 36
|-
| 39 || 105 || 39 || 100 || 105
|-
| 100 || 67 || 100 || 75 || 67
|-
| 75 || 53 || 75 || 50 || 53
|-
| 50 || 39 || 50 || 36 || 39
|-
| 36 || 3 || 36 || 6 || 3
|-
| 6 || 50 || 6 || 53 || 50
|}

== Вариации ==
Изучались некоторые вариации кукушкиного хеширования, в основном с целью улучшить использование пространства путём увеличения {{не переведено 5|Коэффициент нагрузки (информатика)|коэффициента загрузки||Load factor (computer science)}}. В этих вариантах может достигаться порог загрузки больше 50 %. Некоторые из этих методов могут быть использованы для существенного уменьшения числа необходимых перестроек структуры данных.

От обобщения кукушкиного хеширования, использующего более двух хеш-функций, можно ожидать лучшего использования хеш-таблицы, жертвуя некоторой скоростью выборки и вставки. Использование трёх хеш-функций повышает коэффициент загрузки до 91 % {{sfn|Mitzenmacher|2009}}.
Другое обобщение кукушкиного хеширования, называемое ''блочным кукушкиным хешированием'', содержит более одного ключа на ячейку. Использование двух ключей на ячейку позволяет повысить загрузку выше 80 %{{sfn|Dietzfelbinger, Weidling|2007|с=47–68}}.

Ещё один изучавшийся вариант — ''кукушкино хеширование с запасом''. «Запас» — это массив ключей постоянной длины, который используется для хранения ключей, которые не могут быть успешно вставлены в главную хеш-таблицу. Эта модификация уменьшает число неудач до обратно-полиномиальной функции со степенью, которая может быть произвольно большой, путём увеличения размера запаса. Однако большой запас означает более медленный поиск ключа, которого нет в основной таблице, либо если он находится в запасе. Запас можно использовать в комбинации с более чем двумя хеш-функциями или с блоковым кукушкиным хешированием для получения как высокой степени загрузки, так и малого числа неудач вставки{{sfn|Kirsch, Mitzenmacher, Wieder|2010|с=1543–1561}}. Анализ кукушкиного хеширования с запасом распространился и на практические хеш-функции, не только случайные модели хеш-функций, используемые в теоретическом анализе хеширования{{sfn|Aumüller, Dietzfelbinger, Woelfel|2014|с= 428–456}}.

Некоторые исследователи предлагают использовать в некоторых [[Кэш процессора|кэшах процессора]] упрощенное обобщение кукушкиного хеширования, называемого [[Кэш процессора|несимметричным ассоциативным кэшем]].<ref>
[http://www.irisa.fr/caps/PROJECTS/Architecture/ «Micro-Architecture»].
</ref>

== Сравнение с аналогичными структурами ==
Есть другие алгоритмы, которые используют несколько хеш-функций, в частности [[фильтр Блума]] — эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая [[Кукушкин фильтр|кукушкиным фильтром]], использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума{{sfn|Fan, Kaminsky, Andersen|2013|с=36–40 }}.

Исследования 2006 года{{sfn|Zukowski, Heman, Boncz|2006}} показали, что кукушкино хеширование существенно быстрее [[Хеш-таблица|метода цепочек]] для малых хеш-таблиц, находящихся в [[Кэш процессора|кэше]] современных процессоров. В том же году{{sfn|Ross|2006}} разработана блочная версия кукушкиного хеширования (блок содержит более одного ключа), которая работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы исследована в 2009 году{{sfn|Askitis|2009|с=113–122}}.

== См. также ==
* {{не переведено 5|Совершенная функция хеширования|||Perfect hashing}}
* [[Линейное зондирование]]
* {{не переведено 5|Двойное хеширование|||Double hashing}}
* [[Коллизия хеш-функции]]
* [[Хеширование]]
* {{не переведено 5|Квадратичное зондирование|||Quadratic probing}}
* {{не переведено 5|Хеширование «Классики»|||Hopscotch hashing}}

== Примечания ==
{{примечания |2}}

== Литература ==
* {{книга
|автор=Rasmus Pagh, Flemming Friche Rodler
|ref=Pagh, Rodler
|часть= Cuckoo Hashing
|url= http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4189| doi = 10.1007/3-540-44676-1_10
|заглавие=Algorithms — ESA 2001
|серия=Lecture Notes in Computer Science
|том=2161
|страницы=121–133
|год=2001
|isbn=978-3-540-42493-2
}}
* {{книга
|автор=Reinhard Kutzelnigg
|ref=Kutzelnigg
|url=https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAG0133/1710.pdf
|заглавие=Fourth Colloquium on Mathematics and Computer Science
|вклад=Bipartite random graphs and cuckoo hashing
|серия=Discrete Mathematics and Theoretical Computer Science
|год=2006
|том=AG
|страницы=403–406
}}
* {{книга
|автор=M. Mitzenmacher
|ref=Mitzenmacher
|вклад=Some Open Questions Related to Cuckoo Hashing
|заглавие=Proceedings of of the 17th Annual European Symposium on Algorithms (ESA)
|год=2009
|url=http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf
|accessdate=2010-11-10 
}}
* {{статья
|автор=Martin Dietzfelbinger, Christoph Weidling
|ref=Dietzfelbinger, Weidling
|doi= 10.1016/j.tcs.2007.02.054
|выпуск=1—2
|издание =Theoret. Comput. Sci.
|mr= 2330641
|страницы= 47–68
|заглавие= Balanced allocation and dictionaries with tightly packed constant size bins
|том= 380
|год= 2007
}}
* {{статья
|автор=Adam Kirsch, Michael D. Mitzenmacher, Udi Wieder
|ref=Kirsch, Mitzenmacher, Wieder
|doi=10.1137/080728743
|выпуск= 4
|издание= SIAM J. Comput.
|mr= 2580539
|страницы= 1543–1561
|заглавие= More robust hashing: cuckoo hashing with a stash
|том= 39
|год= 2010
}}
* {{статья
|автор=Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
|ref=Aumüller, Dietzfelbinger, Woelfel
|doi= 10.1007/s00453-013-9840-x
|выпуск= 3
|издание= Algorithmica
|mr= 3247374
|страницы= 428–456
|заглавие= Explicit and efficient hash families suffice for cuckoo hashing with a stash
|том= 70
|год= 2014
}}
* {{статья
|автор=Bin Fan, Michael Kaminsky, David Andersen
|ref=Fan, Kaminsky, Andersen
|заглавие=Cuckoo Filter: Better Than Bloom
|издание=;login:
|год=2013
|том=38
|выпуск=4
|страницы=36–40
|url=http://www.cs.cmu.edu/~binfan/papers/login_cuckoofilter.pdf
|accessdate=12 June 2014
|издательство=USENIX
}}
* {{статья
|автор=Marcin Zukowski, Sandor Heman, Peter Boncz
|ref=Zukowski, Heman, Boncz
|заглавие=Architecture-Conscious Hashing
|издательство=Proceedings of the International Workshop on Data Management on New Hardware (DaMoN)
|год=2006
|url=http://www.cs.cmu.edu/~damon2006/pdf/zukowski06archconscioushashing.pdf
|accessdate=2008-10-16
}}
* {{статья
|автор=Kenneth Ross
|ref=Ross
|заглавие=Efficient Hash Probes on Modern Processors
|издательство=IBM Research Report RC24100
|год=2006 
|url=http://domino.research.ibm.com/library/cyberdig.nsf/papers/DF54E3545C82E8A585257222006FD9A2/$File/rc24100.pdf
|id=RC24100
|accessdate=2008-10-16 
}}
* {{книга
|заглавие=Fast and Compact Hash Tables for Integer Keys
|автор=Nikolas Askitis 
|ref=Askitis
|год=2009
|isbn=978-1-920682-72-9
|url=http://crpit.com/confpapers/CRPITV91Askitis.pdf
|страницы=113–122
|издание=Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009)
|том=91
}}

== Ссылки ==
* [http://www.ru.is/faculty/ulfar/CuckooHash.pdf A cool and practical alternative to traditional hash tables], U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
* [https://web.archive.org/web/20110615042618/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.
* {{книга
|автор=Moni Naor, Gil Segev, Udi Wieder
|вклад=History-Independent Cuckoo Hashing
|заглавие=International Colloquium on Automata, Languages and Programming (ICALP) |место=Reykjavik, Iceland
|год=2008
|url=http://www.wisdom.weizmann.ac.il/~naor/PAPERS/cuckoo_hi_abs.html
|accessdate=2008-07-21
}}
* [http://www.cs.princeton.edu/~mfreed/docs/cuckoo-eurosys14.pdf Algorithmic Improvements for Fast Concurrent Cuckoo Hashing], X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.

=== Примеры ===
* [https://github.com/efficient/libcuckoo Concurrent high-performance Cuckoo hashtable written in C++]
* [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++]
* [https://github.com/joacima/Cuckoo-hash-map/blob/master/CuckooHashMap.java Generic Cuckoo hashmap in Java]{{Недоступная ссылка|date=Октябрь 2018 |bot=InternetArchiveBot }}
* [http://hackage.haskell.org/packages/archive/hashtables/latest/doc/html/Data-HashTable-ST-Cuckoo.html Cuckoo hash table written in Haskell]
* [https://github.com/salviati/cuckoo Cuckoo hashing for Go]

[[Категория:Алгоритмы поиска]]
[[Категория:Хеширование]]

{{rq|checktranslate|style}}