Кукушкино хеширование — это схема в программировании для решения коллизий значений хеш-функций в таблице с постоянным временем выборки в худшем случае[en]. Имя происходит от поведения некоторых видов кукушек, когда птенец кукушки выталкивает яйца или других птенцов из гнезда сразу после того, как вылупится. Аналогичное происходит в кукушкином хеше, когда вставка нового ключа в таблицу может вытолкнуть старый ключ в другое место в таблице.
Кукушкино хеширование было впервые описано Расмусом Пажом и Флеммингом Фришем Родлером в 2001[1].
Кукушкино хеширование является видом открытой адресации[en], в которой каждая непустая ячейка хеш-таблицы содержит ключ или пару ключ–значение[en]. Хеш-функция используется для определения места для каждого ключа, и его присутствие в таблице (или значение, ассоциированное с ним) может быть найдено путём проверки этой ячейки в таблице. Однако открытая адресация страдает от коллизий, которые случаются, когда более одного ключа попадают в одну ячейку. Основная идея кукушкиного хеширования заключается в разрешении коллизий путём использования двух хеш-функций вместо одной. Это обеспечивает два возможных положения в хеш-таблице для каждого ключа. В одном из обычных вариантов алгоритма хеш-таблица разбивается на две меньшие таблицы меньшего размера и каждая хеш-функция даёт индекс в одну из этих двух таблиц. Можно обеспечить также для обеих хеш-функций индексирование внутри одной таблицы.
Выборка требует просмотра всего двух мест в хеш-таблице, что требует постоянного времени в худшем случае (см. «O» большое и «o» малое). Это контрастирует с многими другими алгоритмами хеш-таблиц, которые не обеспечивают постоянное время выборки в худшем случае. Удаление также может быть осуществлено очищением ячейки, содержащей ключ за постоянное время в худшем случае, что осуществляется проще, чем в других схемах, таких как линейное зондирование.
Когда вставляется новый ключ и одна из двух ячеек пуста, ключ может быть помещён в эту ячейку. В случае же, когда обе ячейки заняты, необходимо переместить другие ключи в другие места (или, наоборот, на их прежние места), чтобы освободить место для нового ключа. Используется жадный алгоритм — ключ помещается в одну из возможных позиций, «выталкивая» любой ключ, который был в этой позиции. Вытолкнутый ключ затем помещается в его альтернативную позицию, снова выталкивая любой ключ, который мог там оказаться. Процесс продолжается, пока не найдётся пустая позиция. Возможен, однако, случай, когда процесс вставки заканчивается неудачей, попадая в бесконечный цикл или когда образуется слишком длинная цепочка (длиннее, чем заранее заданный порог, зависящий логарифмически от длины таблицы). В этом случае хеш-таблица перестраивается на месте[en] с новыми хеш-функциями:
Нет необходимости размещения новой таблицы для повторного хеширования — мы можем просто просматривать таблицу для удаления и повторной вставки всех ключей, которые находятся не в той позиции, в которой должны были бы стоять.[1] Pagh & Rodler, «Cuckoo Hashing» |
Ожидаемое время вставки постоянно[1], даже если принимать во внимание возможную необходимость перестройки таблицы, пока число ключей меньше половины ёмкости хеш-таблицы, т.е. коэффициент загрузки[en] меньше 50 %.
Чтобы обеспечить это, используется теория случайных графов — можно образовать неориентированный граф, называемый «кукушкиным графом», в котором вершинами являются ячейки хеш-таблицы, а рёбра для каждого хешируемого соединяют два возможных положения (ячейки хеш-таблицы). Тогда жадный алгоритм вставки множества значений в кукушкину хеш-таблицу успешно завершается тогда и только тогда, когда кукушкин граф для этого множества значений является псевдолесом, графом максимум с одним циклом в каждой компоненте связности. Любой порождённый вершинами подграф с числом рёбер, большим числа вершин, соответствует множеству ключей, для которых число слотов в хеш-таблице недостаточно. Если хеш-функция выбирается случайно, кукушкин граф будет случайным графом в модели Эрдёша – Реньи[en]. С высокой степенью вероятности для случайного графа, в котором отношение числа рёбер к числу вершин ограничено сверху 1/2, граф является псевдолесом и алгоритм кукушкиного хеширования располагает успешно все ключи. Более того, та же теория доказывает, что ожидаемый размер компонент связности кукушкиного графа мал, что обеспечивает постоянное ожидаемое время вставки[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 |
Изучались некоторые вариации кукушкиного хеширования, в основном с целью улучшить использование пространства путём увеличения коэффициента загрузки[en]. В этих вариантах может достигаться порог загрузки больше 50 %. Некоторые из этих методов могут быть использованы для существенного уменьшения числа необходимых перестроек структуры данных.
От обобщения кукушкиного хеширования, использующего более двух хеш-функций, можно ожидать лучшего использования хеш-таблицы, жертвуя некоторой скоростью выборки и вставки. Использование трёх хеш-функций повышает коэффициент загрузки до 91 % [3]. Другое обобщение кукушкиного хеширования, называемое блочным кукушкиным хешированием, содержит более одного ключа на ячейку. Использование двух ключей на ячейку позволяет повысить загрузку выше 80 %[4].
Ещё один изучавшийся вариант — кукушкино хеширование с запасом. «Запас» — это массив ключей постоянной длины, который используется для хранения ключей, которые не могут быть успешно вставлены в главную хеш-таблицу. Эта модификация уменьшает число неудач до обратно-полиномиальной функции со степенью, которая может быть произвольно большой, путём увеличения размера запаса. Однако большой запас означает более медленный поиск ключа, которого нет в основной талице, либо если он находится в запасе. Запас можно использовать в комбинации с более чем двумя хеш-функциями или с блоковым кукушкиным хешированием для получения как высокой степени загрузки, так и малого числа неудач вставки[5]. Анализ кукушкиного хеширования с запасом распространился и на практические хеш-функции, не только случайные модели хеш-функций, используемые в теоретическом анализе хеширования[6].
Некоторые исследователи предлагают использовать в некоторых кэшах процессора упрощенное обобщение кукушкиного хеширования, называемого несимметричным ассоциативным кэшем.[7]
Есть другие алгоритмы, которые используют несколько хеш-функций, в частности фильтр Блума, эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума[8].
Исследования, проведённые Жуковским, Хеманом и Бонзом[9], показали, что кукушкино хеширование существенно быстрее метода цепочек для малых хеш-таблиц, находящихся в кэше современных процессоров. Кеннет Росс[10] показал блочную версию кукушкиного хеширования (блок содержит более одного ключа), который работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы позднее исследовал Аскитис[11] по сравнению с другими схемами кэширования.
Обзор Мутцемахера[3] представляет открытые проблемы, связанные с кукушкиным хешированием.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .