Кукушкино хеширование: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Луговкин (обсуждение | вклад) |
РобоСтася (обсуждение | вклад) |
||
(не показано 20 промежуточных версий 14 участников) | |||
Строка 1: | Строка 1: | ||
[[Файл: |
[[Файл:Cuckoo hashing example.svg|thumb|Пример кукушкиного хеширования. Стрелки показывают альтернативное положение ключа. Новое значение, которое вставляется в ячейку A, выталкивая A в альтернативную ячейку, занимаемую ключом B, значение B переносится в альтернативное место, которое в настоящее время не занято. Вставка нового значения в ячейку H завершается неудачей — H входит в цикл (вместе с W), так что только что вставленный элемент должен быть вытолкнут.]] |
||
'''Кукушкино |
'''Кукушкино хеширование''' — алгоритм разрешения [[Коллизия хеш-функции|коллизий]] значений [[хеш-функция|хеш-функций]] в [[хеш-таблица|таблице]] с [[Временная сложность алгоритма|постоянным]] временем выборки в {{не переведено 5|Лучший, худший и средний случаи|худшем случае||worst case analysis}}. |
||
Предложено в 2001 году{{sfn|Pagh, Rodler|2001|с=121–133}}. Название отсылает к поведению некоторых видов [[Кукушковые|кукушек]], когда птенец выталкивает из гнезда яйца или других птенцов; аналогичным образом в алгоритме предусматривается возможность выталкивания старого ключа при вставке нового. |
|||
== История == |
|||
Кукушкино хэширование было впервые описано Расмусом Пажом и Флеммингом Фришем Родлером в 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}}, даже если принимать во внимание возможную необходимость перестройки таблицы, пока число ключей меньше половины ёмкости хеш-таблицы, то есть [[Хеш-таблица|коэффициент загрузки]] меньше 50 %. |
||
Чтобы обеспечить это, используется теория [[Случайный граф|случайных графов]] |
Чтобы обеспечить это, используется теория [[Случайный граф|случайных графов]] — можно образовать [[неориентированный граф]], называемый «кукушкиным графом», в котором вершинами являются ячейки хеш-таблицы, а рёбра для каждого хешируемого соединяют два возможных положения (ячейки хеш-таблицы). Тогда жадный алгоритм вставки множества значений в кукушкину хеш-таблицу успешно завершается тогда и только тогда, когда кукушкин граф для этого множества значений является [[псевдолес]]ом, графом максимум с одним циклом в каждой [[Компонента связности графа|компоненте связности]]. Любой порождённый вершинами подграф с числом рёбер, большим числа вершин, соответствует множеству ключей, для которых число слотов в хеш-таблице недостаточно. Если хеш-функция выбирается случайно, кукушкин граф будет [[Случайный граф|случайным графом]] в [[Модель Эрдёша — Реньи|модели Эрдёша – Реньи]]. С высокой степенью вероятности для случайного графа, в котором отношение числа рёбер к числу вершин ограничено сверху 1/2, граф является псевдолесом и алгоритм кукушкиного хеширования располагает успешно все ключи. Более того, та же теория доказывает, что ожидаемый размер [[Компонента связности графа|компонент связности]] кукушкиного графа мал, что обеспечивает постоянное ожидаемое время вставки{{sfn|Kutzelnigg|2006|с=403–406}}. |
||
== Пример == |
== Пример == |
||
Если даны следующие две хеш-функции: |
|||
<math>h\left(k\right)=k\mod 11</math |
: <math>h\left(k\right)=k\mod 11</math> |
||
<math>h'\left(k\right)=\left\lfloor\frac{k}{11}\right\rfloor\mod 11</math> |
: <math>h'\left(k\right)=\left\lfloor\frac{k}{11}\right\rfloor\mod 11</math> |
||
<div style="float:left; margin-right:1em"> |
<div style="float:left; margin-right:1em"> |
||
Строка 52: | Строка 51: | ||
</div> |
</div> |
||
Столбцы в следующих двух таблицах показывают состояние |
Столбцы в следующих двух таблицах показывают состояние хеш-таблицы после вставки элементов. |
||
<div style="float:left; margin-right:1em"> |
<div style="float:left; margin-right:1em"> |
||
Строка 61: | Строка 60: | ||
| || 20 || 50 || 53 || 75 || 100 || 67 || 105 || 3 || 36 || 39 |
| || 20 || 50 || 53 || 75 || 100 || 67 || 105 || 3 || 36 || 39 |
||
|- |
|- |
||
| 0 || || || || || || || || || || |
| 0 || || || || || || || || || || |
||
|- |
|- |
||
| 1 || || || || || 100 || 67 || 67 || 67 || 67 || 100 |
| 1 || || || || || 100 || 67 || 67 || 67 || 67 || 100 |
||
|- |
|- |
||
| 2 || || || || || || || || || || |
| 2 || || || || || || || || || || |
||
|- |
|- |
||
| 3 || || || || || || || || 3 || 36 || 36 |
| 3 || || || || || || || || 3 || 36 || 36 |
||
|- |
|- |
||
| 4 || || || || || || || || || || |
| 4 || || || || || || || || || || |
||
|- |
|- |
||
| 5 || || || || || || || || || || |
| 5 || || || || || || || || || || |
||
|- |
|- |
||
| 6 || || 50 || 50 || 50 || 50 || 50 || 105 || 105 || 105 || 50 |
| 6 || || 50 || 50 || 50 || 50 || 50 || 105 || 105 || 105 || 50 |
||
|- |
|- |
||
| 7 || || || || || || || || || || |
| 7 || || || || || || || || || || |
||
|- |
|- |
||
| 8 || || || || || || || || || || |
| 8 || || || || || || || || || || |
||
|- |
|- |
||
| 9 || 20 || 20 || 53 || 75 || 75 || 75 || 53 || 53 || 53 || 75 |
| 9 || 20 || 20 || 53 || 75 || 75 || 75 || 53 || 53 || 53 || 75 |
||
|- |
|- |
||
| 10 || || || || || || || || || || |
| 10 || || || || || || || || || || |
||
|} |
|} |
||
</div> |
</div> |
||
Строка 96: | Строка 95: | ||
| 1 || || || 20 || 20 || 20 || 20 || 20 || 20 || 20 || 20 |
| 1 || || || 20 || 20 || 20 || 20 || 20 || 20 || 20 || 20 |
||
|- |
|- |
||
| 2 || || || || || || || || || || |
| 2 || || || || || || || || || || |
||
|- |
|- |
||
| 3 || || || || || || || || || || 39 |
| 3 || || || || || || || || || || 39 |
||
Строка 102: | Строка 101: | ||
| 4 || || || || 53 || 53 || 53 || 50 || 50 || 50 || 53 |
| 4 || || || || 53 || 53 || 53 || 50 || 50 || 50 || 53 |
||
|- |
|- |
||
| 5 || || || || || || || || || || |
| 5 || || || || || || || || || || |
||
|- |
|- |
||
| 6 || || || || || || || 75 || 75 || 75 || 67 |
| 6 || || || || || || || 75 || 75 || 75 || 67 |
||
|- |
|- |
||
| 7 || || || || || || || || || || |
| 7 || || || || || || || || || || |
||
|- |
|- |
||
| 8 || || || || || || || || || || |
| 8 || || || || || || || || || || |
||
|- |
|- |
||
| 9 || || || || || || 100 || 100 || 100 || 100 || 105 |
| 9 || || || || || || 100 || 100 || 100 || 100 || 105 |
||
|- |
|- |
||
| 10 || || || || || || || || || || |
| 10 || || || || || || || || || || |
||
|} |
|} |
||
</div> |
</div> |
||
Строка 118: | Строка 117: | ||
=== Циклы === |
=== Циклы === |
||
Если вы хотите вставить элемент 6, вы получите бесконечный цикл. В последней строке таблицы мы находим ту же начальную ситуацию |
Если вы хотите вставить элемент 6, вы получите бесконечный цикл. В последней строке таблицы мы находим ту же начальную ситуацию, что и в начале. |
||
<math>h\left(6\right)=6\mod 11=6</math><br |
<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 |
<math>h'\left(6\right)=\left\lfloor\frac{6}{11}\right\rfloor\mod 11=0</math><br> |
||
{| class="wikitable" |
{| class="wikitable" |
||
|- |
|- |
||
Строка 152: | Строка 151: | ||
== Вариации == |
== Вариации == |
||
Изучались некоторые вариации кукушкиного |
Изучались некоторые вариации кукушкиного хеширования, в основном с целью улучшить использование пространства путём увеличения {{не переведено 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»] {{Wayback|url=http://www.irisa.fr/caps/PROJECTS/Architecture/ |date=20191229113203 }}.</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}}. |
||
Обзор Мутцемахера {{sfn|Mitzenmacher|2009}} представляет открытые проблемы, связанные с кукушкиным хэшированием. |
|||
== См. также == |
== См. также == |
||
* {{не переведено 5|Совершенная функция |
* {{не переведено 5|Совершенная функция хеширования|||Perfect hashing}} |
||
* |
* [[Линейное зондирование]] |
||
* {{не переведено 5|Двойное |
* {{не переведено 5|Двойное хеширование|||Double hashing}} |
||
* [[Коллизия хеш-функции]] |
* [[Коллизия хеш-функции]] |
||
* [[Хеширование]] |
* [[Хеширование]] |
||
* {{не переведено 5|Квадратичное зондирование|||Quadratic probing}} |
* {{не переведено 5|Квадратичное зондирование|||Quadratic probing}} |
||
* {{не переведено 5| |
* {{не переведено 5|Хеширование «Классики»|||Hopscotch hashing}} |
||
== Примечания == |
== Примечания == |
||
Строка 219: | Строка 214: | ||
|ref=Dietzfelbinger, Weidling |
|ref=Dietzfelbinger, Weidling |
||
|doi= 10.1016/j.tcs.2007.02.054 |
|doi= 10.1016/j.tcs.2007.02.054 |
||
|выпуск= |
|выпуск=1—2 |
||
|издание =Theoret. Comput. Sci. |
|издание =Theoret. Comput. Sci. |
||
|mr= 2330641 |
|mr= 2330641 |
||
Строка 261: | Строка 256: | ||
|страницы=36–40 |
|страницы=36–40 |
||
|url=http://www.cs.cmu.edu/~binfan/papers/login_cuckoofilter.pdf |
|url=http://www.cs.cmu.edu/~binfan/papers/login_cuckoofilter.pdf |
||
|accessdate= |
|accessdate=2014-06-12 |
||
|издательство=USENIX |
|издательство=USENIX |
||
}} |
}} |
||
Строка 297: | Строка 292: | ||
== Ссылки == |
== Ссылки == |
||
* [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.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. |
* [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. |
* [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. |
||
* {{книга |
* {{книга |
||
Строка 313: | Строка 308: | ||
* [http://sourceforge.net/projects/cuckoo-cpp/ Cuckoo hash map 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++] |
* [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] |
* [https://github.com/joacima/Cuckoo-hash-map/blob/master/CuckooHashMap.java Generic Cuckoo hashmap in Java]{{Недоступная ссылка|date=2018-10|bot=InternetArchiveBot }} |
||
* [http://hackage.haskell.org/packages/archive/hashtables/latest/doc/html/Data-HashTable-ST-Cuckoo.html Cuckoo hash table written in Haskell] |
* [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] |
* [https://github.com/salviati/cuckoo Cuckoo hashing for Go] |
||
⚫ | |||
{{изолированная статья}} |
|||
[[Категория:Алгоритмы поиска]] |
[[Категория:Алгоритмы поиска]] |
||
[[Категория:Хеширование]] |
[[Категория:Хеширование]] |
||
⚫ |
Текущая версия от 02:05, 25 июля 2024
Кукушкино хеширование — алгоритм разрешения коллизий значений хеш-функций в таблице с постоянным временем выборки в худшем случае[англ.].
Предложено в 2001 году[1]. Название отсылает к поведению некоторых видов кукушек, когда птенец выталкивает из гнезда яйца или других птенцов; аналогичным образом в алгоритме предусматривается возможность выталкивания старого ключа при вставке нового.
Операции
[править | править код]Кукушкино хеширование является видом открытой адресации[англ.], в которой каждая непустая ячейка хеш-таблицы содержит ключ или пару «ключ — значение». Хеш-функция используется для определения места для каждого ключа, и его присутствие в таблице (или значение, ассоциированное с ним) может быть найдено путём проверки этой ячейки в таблице. Однако открытая адресация страдает от коллизий, которые случаются, когда более одного ключа попадают в одну ячейку. Основная идея кукушкиного хеширования заключается в разрешении коллизий путём использования двух хеш-функций вместо одной. Это обеспечивает два возможных положения в хеш-таблице для каждого ключа. В одном из обычных вариантов алгоритма хеш-таблица разбивается на две меньшие таблицы меньшего размера и каждая хеш-функция даёт индекс в одну из этих двух таблиц. Можно обеспечить также для обеих хеш-функций индексирование внутри одной таблицы.
Выборка требует просмотра всего двух мест в хеш-таблице, что требует постоянного времени в худшем случае (см. «O» большое и «o» малое). Это контрастирует с многими другими алгоритмами хеш-таблиц, которые не обеспечивают постоянное время выборки в худшем случае. Удаление также может быть осуществлено очищением ячейки, содержащей ключ за постоянное время в худшем случае, что осуществляется проще, чем в других схемах, таких как линейное зондирование.
Когда вставляется новый ключ и одна из двух ячеек пуста, ключ может быть помещён в эту ячейку. В случае же, когда обе ячейки заняты, необходимо переместить другие ключи в другие места (или, наоборот, на их прежние места), чтобы освободить место для нового ключа. Используется жадный алгоритм — ключ помещается в одну из возможных позиций, «выталкивая» любой ключ, который был в этой позиции. Вытолкнутый ключ затем помещается в его альтернативную позицию, снова выталкивая любой ключ, который мог там оказаться. Процесс продолжается, пока не найдётся пустая позиция. Возможен, однако, случай, когда процесс вставки заканчивается неудачей, попадая в бесконечный цикл или когда образуется слишком длинная цепочка (длиннее, чем заранее заданный порог, зависящий логарифмически от длины таблицы). В этом случае хеш-таблица перестраивается на месте[англ.] с новыми хеш-функциями:
Нет необходимости размещения новой таблицы для повторного хеширования — мы можем просто просматривать таблицу для удаления и повторной вставки всех ключей, которые находятся не в той позиции, в которой должны были бы стоять.[1]Pagh & Rodler, «Cuckoo Hashing»
Вычислительная сложность
[править | править код]Ожидаемое время вставки постоянно[1], даже если принимать во внимание возможную необходимость перестройки таблицы, пока число ключей меньше половины ёмкости хеш-таблицы, то есть коэффициент загрузки меньше 50 %.
Чтобы обеспечить это, используется теория случайных графов — можно образовать неориентированный граф, называемый «кукушкиным графом», в котором вершинами являются ячейки хеш-таблицы, а рёбра для каждого хешируемого соединяют два возможных положения (ячейки хеш-таблицы). Тогда жадный алгоритм вставки множества значений в кукушкину хеш-таблицу успешно завершается тогда и только тогда, когда кукушкин граф для этого множества значений является псевдолесом, графом максимум с одним циклом в каждой компоненте связности. Любой порождённый вершинами подграф с числом рёбер, большим числа вершин, соответствует множеству ключей, для которых число слотов в хеш-таблице недостаточно. Если хеш-функция выбирается случайно, кукушкин граф будет случайным графом в модели Эрдёша – Реньи. С высокой степенью вероятности для случайного графа, в котором отношение числа рёбер к числу вершин ограничено сверху 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 |
Вариации
[править | править код]Изучались некоторые вариации кукушкиного хеширования, в основном с целью улучшить использование пространства путём увеличения коэффициента загрузки[англ.]. В этих вариантах может достигаться порог загрузки больше 50 %. Некоторые из этих методов могут быть использованы для существенного уменьшения числа необходимых перестроек структуры данных.
От обобщения кукушкиного хеширования, использующего более двух хеш-функций, можно ожидать лучшего использования хеш-таблицы, жертвуя некоторой скоростью выборки и вставки. Использование трёх хеш-функций повышает коэффициент загрузки до 91 % [3]. Другое обобщение кукушкиного хеширования, называемое блочным кукушкиным хешированием, содержит более одного ключа на ячейку. Использование двух ключей на ячейку позволяет повысить загрузку выше 80 %[4].
Ещё один изучавшийся вариант — кукушкино хеширование с запасом. «Запас» — это массив ключей постоянной длины, который используется для хранения ключей, которые не могут быть успешно вставлены в главную хеш-таблицу. Эта модификация уменьшает число неудач до обратно-полиномиальной функции со степенью, которая может быть произвольно большой, путём увеличения размера запаса. Однако большой запас означает более медленный поиск ключа, которого нет в основной таблице, либо если он находится в запасе. Запас можно использовать в комбинации с более чем двумя хеш-функциями или с блоковым кукушкиным хешированием для получения как высокой степени загрузки, так и малого числа неудач вставки[5]. Анализ кукушкиного хеширования с запасом распространился и на практические хеш-функции, не только случайные модели хеш-функций, используемые в теоретическом анализе хеширования[6].
Некоторые исследователи предлагают использовать в некоторых кэшах процессора упрощенное обобщение кукушкиного хеширования, называемого несимметричным ассоциативным кэшем.[7]
Сравнение с аналогичными структурами
[править | править код]Есть другие алгоритмы, которые используют несколько хеш-функций, в частности фильтр Блума — эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума[8].
Исследования 2006 года[9] показали, что кукушкино хеширование существенно быстрее метода цепочек для малых хеш-таблиц, находящихся в кэше современных процессоров. В том же году[10] разработана блочная версия кукушкиного хеширования (блок содержит более одного ключа), которая работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы исследована в 2009 году[11].
См. также
[править | править код]- Совершенная функция хеширования[англ.]
- Линейное зондирование
- Двойное хеширование[англ.]
- Коллизия хеш-функции
- Хеширование
- Квадратичное зондирование[англ.]
- Хеширование «Классики»[англ.]
Примечания
[править | править код]- ↑ 1 2 3 Pagh, Rodler, 2001, с. 121–133.
- ↑ Kutzelnigg, 2006, с. 403–406.
- ↑ Mitzenmacher, 2009.
- ↑ Dietzfelbinger, Weidling, 2007, с. 47–68.
- ↑ Kirsch, Mitzenmacher, Wieder, 2010, с. 1543–1561.
- ↑ Aumüller, Dietzfelbinger, Woelfel, 2014, с. 428–456.
- ↑ «Micro-Architecture» Архивная копия от 29 декабря 2019 на Wayback Machine.
- ↑ Fan, Kaminsky, Andersen, 2013, с. 36–40.
- ↑ Zukowski, Heman, Boncz, 2006.
- ↑ Ross, 2006.
- ↑ Askitis, 2009, с. 113–122.
Литература
[править | править код]- 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
Для улучшения этой статьи желательно:
|