Кукушкино хеширование

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

Кукушкино хэширование — это схема в программировании для решения коллизий значений хэш-функций в таблице с постоянным временем выборки в худшем случае. Имя происходит от поведения некоторых видов кукушек, когда птенец кукушки выталкивает яйца или других птенцов из гнезда сразу после того как вылупится. Аналогичное происходит в кукушкином хэше, когда вставка нового ключа в таблицу может вытолкнуть старый ключ в другое место в таблице.

История

Кукушкино хэширование было впервые описано Расмусом Пажом и Флеммингом Фришем Родлером в 2001 .

Операции

Кукушкино хэширование является видом открытой адресации, в которой каждая непустая ячейка хэш-таблицы содержит ключ или пару ключ–значение. Хэш-функция используется для определения места для каждого ключа, и его присутствие в таблице (или значение, ассоциированное с ним) может быть найдено путём проверки этой ячейки в таблице. Однако, открытая адресация страдает от коллизий, которые случаются, когда более одного ключа попадают в одну ячейку. Основная идея кукушкиного хэширования заключается в разрешении коллизий путём использования двух хэш-функций вместо одной. Это обеспечивает два возможных положения в хэш-таблице для каждого ключа. В одном из обычных вариантов алгоритма хэш-таблица разбивается на две меньшие таблицы меньшего размера и каждая хэш-функция даёт индекс в одну из этих двух таблиц. Можно обеспечить также для обоих хэш-функций индексирование внутри одной таблицы.

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

Когда вставляется новый ключ и одна из двух ячеек пуста, ключ может быть помещён в эту ячейку. В случае же когда обе ячейки заняты, необходимо переместить другие ключи в другие места (или, наоборот, на их прежние места), чтобы освободить место для нового ключа. Используется жадный алгоритм — ключ помещается в одно из возможных позиций, «выталкивая» любой ключ, который был в этой позиции. Вытолкнутый ключ затем помещается в его альтернативную позицию, снова выталкивая любой ключ, который мог там оказаться. Процесс продолжается, пока не найдётся пустая позиция. Возможен, однако случай, когда процесс вставки заканчивается неудачей, попадая в бесконечный цикл или когда образуется слишком длинная цепочка (длиннее чем заранее заданный порог, зависящий логарифмически от длины таблицы). В этом случае хэш-таблица перестраивается на месте с новыми хэш-функциями:

Нет необходимости размещения новой таблицы для повторного хэширования — мы можем просто просматриваем таблицу для удаления и повторной вставки всех ключей, которые находятся не в той позиции, в которой должны были бы стоять. Pagh & Rodler, «Cuckoo Hashing»

Теория

Ожидаемое время вставки постоянно , даже если принимать во внимание возможную необходимость перестройки таблицы, пока число ключей меньше половины ёмкости хэш-таблицы, т.е. коэффициент загрузки меньше 50%.

Чтобы обеспечить это, используется теория случайных графов — можно образовать неориентированный граф, называемый «кукушкиным графом», в котором вершинами являются ячейки хэш-таблицы, а рёбра для каждого хэшируемого соединяют два возможных положения (ячейки хэш-таблицы). Тогда жадный алгоритм вставки множества значений в кукушкину хэш-таблицу успешно завершается тогда и только тогда, когда кукушкин граф для этого множества значений является псевдолесом, графом максимум с одним циклом в каждой компоненте связности. Любой порождённый вершинами подграф с числом рёбер, большим числа вершин, соответствует множеству ключей, для которых число слотов в хэш-таблице недостаточно. Если хэш-функция выбирается случайно, кукушкин граф будет случайным графом в модели Эрдёша – Реньи. С высокой степенью вероятности для случайного графа, в котором отношение числа рёбер к числу вершин ограничено сверху 1/2, граф является псевдолесом и алгоритм кукушкиного хэширования располагает успешно все ключи. Более того,та же теория доказывает, что ожидаемый размер компонент связности кукушкиного графа мал, что обеспечивает постоянное ожидаемое время вставки .

Пример

Пусть даны следующие две хэш-функции:

$h\left(k\right)=k\mod 11$
$h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor \mod 11$

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

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

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

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

Циклы

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

$h\left(6\right)=6\mod 11=6$
$h'\left(6\right)=\left\lfloor {\frac {6}{11}}\right\rfloor \mod 11=0$

ключ	table 1		table 2
	старое значение	новое значение	старое значение	новое значение
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

Вариации

Изучались некоторые вариации кукушкиного хэширования, в основным с целью улучшить использование пространства путём увеличения коэффициента загрузки. В этих вариантах может достигаться порог загрузки больше 50%. Некоторые из этих методов могут быть использованы для существенного уменьшения числа необходимых перестроек структуры данных.

От обобщения кукушкиного хэширования, использующего более двух хэш-функций, можно ожидать лучшего использования хэш-таблицы жертвуя некоторой скоростью выборки и вставки. Использование трёх хэш-функций повышает коэффициент загрузки до 91% . Другое обобщение кукушкиного хэширования, называемое блочным кукушкиным хэшированием содержит более одного ключа на ячейку. Использование двух ключей на ячейку позволяет повысить загрузку выше 80% .

Ещё один изучавшийся вариант — кукушкино хэширование с запасом. «Запас» — это массив ключей постоянной длины, который используется для хранения ключей, которые не могут быть успешно вставлены в главную хэш-таблицу. Эта модификация уменьшает число неудач до обратно-полиномиальной функции со степенью, которая может быть произвольно большой, путём увеличения размера запаса. Однако, большой запас означает более медленный поиск ключа, которого нет в основной талице, либо если он находится в запасе. Запас можно использовать в комбинации с более чем двумя хэш-функциями или с блоковым кукушкиным хэшированием для получения как высокой степени загрузки, так и малого числа неудач вставки . Анализ кукушкиного хэширования с запасом распространился и на практические хэш-функции, не только случайные модели хэш-функций, используемые в теоретическом анализе хэширования .

Некоторые исследователи предлагают использовать в некоторых кэшах процессора упрощенное обобщение кукушкиного хэширования, называемого несимметричным ассоциативным кэшем .

Сравнение со аналогичными структурами

Есть другие алгоритмы, которые используют несколько хэш-функций, в частности фильтр Блума, эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хэшировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако, теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума .

Исследования, проведённые Жуковским, Хеманом и Бонзом показали, что кукушкино хэширование существенно быстрее метода цепочек для малых хэш-таблиц, находящихся в кэшесовременных процессоров. Кеннет Росс показал блочную версию кукушкиного хэширования (блок содержит более одного ключа), который работает быстрее обычных методов для больших хэш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хэш-таблицы позднее исследовал Аскитис по сравнению с другими схемами кэширования.

Обзор Мутцемахера представляет открытые проблемы, связанные с кукушкиным хэшированием.

См. также

• Совершенная функция хэширования
• Линейное зондирование
• Двойное хэширование
• Коллизия хеш-функции
• Хеширование
• Квадратичное зондирование
• Хэширование «Классики»

Литература

• Rasmus Pagh, Flemming Friche Rodler. Cuckoo Hashing // Algorithms — ESA 2001. — 2001. — Т. 2161. — С. 121–133. — (Lecture Notes in Computer Science). — ISBN 978-3-540-42493-2. — doi:10.1007/3-540-44676-1_10.
• Reinhard Kutzelnigg. Fourth Colloquium on Mathematics and Computer Science. — 2006. — Т. AG. — С. 403–406. — (Discrete Mathematics and Theoretical Computer Science).
• M. Mitzenmacher. Proceedings of of the 17th Annual European Symposium on Algorithms (ESA). — 2009.
• Martin Dietzfelbinger, Christoph Weidling. Balanced allocation and dictionaries with tightly packed constant size bins // Theoret. Comput. Sci.. — 2007. — Т. 380, вып. 1-2. — С. 47–68. — doi:10.1016/j.tcs.2007.02.054.
• Adam Kirsch, Michael D. Mitzenmacher, Udi Wieder. More robust hashing: cuckoo hashing with a stash // SIAM J. Comput.. — 2010. — Т. 39, вып. 4. — С. 1543–1561. — doi:10.1137/080728743.
• Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel. Explicit and efficient hash families suffice for cuckoo hashing with a stash // Algorithmica. — 2014. — Т. 70, вып. 3. — С. 428–456. — doi:10.1007/s00453-013-9840-x.
• Bin Fan, Michael Kaminsky, David Andersen. Cuckoo Filter: Better Than Bloom // ;login:. — USENIX, 2013. — Т. 38, вып. 4. — С. 36–40.
• Marcin Zukowski, Sandor Heman, Peter Boncz. Architecture-Conscious Hashing. — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006.
• Kenneth Ross. Efficient Hash Probes on Modern Processors. — IBM Research Report RC24100, 2006.
• Nikolas Askitis. Fast and Compact Hash Tables for Integer Keys. — Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009). — 2009. — Т. 91. — С. 113–122. — ISBN 978-1-920682-72-9.

Ссылки

• 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.
• Moni Naor, Gil Segev, Udi Wieder. International Colloquium on Automata, Languages and Programming (ICALP). — Reykjavik, Iceland, 2008.
• Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.

Примеры

• Concurrent high-performance Cuckoo hashtable written in C++
• Cuckoo hash map written in C++
• Static cuckoo hashtable generator for C/C++
• Generic Cuckoo hashmap in Java
• Cuckoo hash table written in Haskell
• Cuckoo hashing for Go