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

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

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

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

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

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

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

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

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, вы получите бесконечный цикл. В последней строке таблицы мы находим ту же начальную ситуацию, что и в начале.

ключ 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 %.

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

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

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

Исследования 2006 года показали, что кукушкино хеширование существенно быстрее метода цепочек для малых хеш-таблиц, находящихся в кэше современных процессоров. В том же году разработана блочная версия кукушкиного хеширования (блок содержит более одного ключа), которая работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы исследована в 2009 году.

См. также

Линейное зондирование

Коллизия хеш-функции Хеширование

Примечания

Литература

Ссылки 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.

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

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