Хеширование кукушки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Время работы алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показано 97 промежуточных версий 9 участников)
Строка 1: Строка 1:
 
[[Image:cuckoo.png|thumb|Пример хеширования кукушки. Стрелки показывают второе возможное место элементов. Если нам надо будет вставить новый элемент на место А, то мы поместим А в его вторую ячейку, занятую В, а В переместим в его вторую ячейку, которая сейчас свободна. А вот помещение нового элемента на место Н не получится: так как Н — часть цикла, добавленный элемент будет вытеснен после прохода по циклу.]]
 
[[Image:cuckoo.png|thumb|Пример хеширования кукушки. Стрелки показывают второе возможное место элементов. Если нам надо будет вставить новый элемент на место А, то мы поместим А в его вторую ячейку, занятую В, а В переместим в его вторую ячейку, которая сейчас свободна. А вот помещение нового элемента на место Н не получится: так как Н — часть цикла, добавленный элемент будет вытеснен после прохода по циклу.]]
  
−
'''Хеширование кукушки''' — один из способов борьбы с коллизиями при создании хеш-таблицы.
+
'''Хеширование кукушки'''(англ. ''Cuckoo hashing'') {{---}} один из способов [[Разрешение коллизий|борьбы с коллизиями]] при создании [[Хеш-таблица|хеш-таблицы]].
  
 
==Алгоритм==
 
==Алгоритм==
  
−
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <math>h_1(x)</math> и <math>h_2(x)</math>). Так же есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), delete(x) и exists(x).
+
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <tex>h_1(x)</tex> и <tex>h_2(x)</tex>). Также есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций <tex>add(x), remove(x)</tex> и <tex>contains(x)</tex>.
  
−
===Add===
+
Выберем <tex>2</tex> хэш-функции <tex>h_1(x)</tex> и <tex>h_2(x)</tex> (из [[Универсальное семейство хеш-функций | универсального семейства хэш-функций]]).
  
−
# Если одна из ячеек с индексами <math>h_1(x)</math> или <math>h_2(x)</math> свободна, кладем в нее элемент. Переходим к шагу 7.
+
===='''Add'''====
−
# Иначе произвольно выбираем одну из этих ячеек, вытаскиваем оттуда элемент, помещаем туда новый.
+
Добавляет элемент с ключом <tex>x</tex> в хэш-таблицу
−
# Смотрим в ячейку, на которую указывает другая хеш-функция от только что вытащенного элемента, если она свободна, помещаем его в нее. Переходим к шагу 7.
 
−
# Иначе вытаскиваем из этой ячейки элемент, кладем туда старый. Проверяем, не зациклились ли мы.
 
−
# Если не зациклились, переходим к шагу 3.
 
−
# Иначе выбираем 2 новые хеш-функции и перехешируем все добавленные элементы.
 
−
# Помечаем ячейку, в которую только что добавили элемент, как занятую.
 
  
−
===Delete===
+
# Если одна из ячеек с индексами <tex>h_1(x)</tex> или <tex>h_2(x)</tex> свободна, кладем в нее элемент.
 +
# Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
 +
# Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее.
 +
# Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
 +
# Если не зациклились, то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся.
 +
# Иначе выбираем <tex>2</tex> новые хеш-функции и перехешируем все добавленные элементы.
 +
# Также после добавления нужно увеличить размер таблицы в случае если она заполнена.
  
−
# Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>.
+
===='''Remove'''====
 +
Удаляет элемент с ключом <tex>x</tex> из хэш-таблицы.
 +
 
 +
# Смотрим ячейки с индексами <tex>h_1(x)</tex> и <tex>h_2(x)</tex>.
 
# Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.
 
# Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.
  
−
===Exists===
+
===='''Contains'''====
 +
Проверяет на наличие элемента <tex>x</tex> в хэш-таблице
  
−
# Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>.
+
# Смотрим ячейки с индексами <tex>h_1(x)</tex> и <tex>h_2(x)</tex>.
 
# Если в одной из них есть искомый элемент, возвращаем true.
 
# Если в одной из них есть искомый элемент, возвращаем true.
 
# Иначе возвращаем false.
 
# Иначе возвращаем false.
 +
 +
== Зацикливание ==
 +
 +
Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <tex>x</tex>. И обе ячейки <tex>h_1(x)</tex> и <tex>h_2(x)</tex> заняты. Элемент <tex>x</tex> положили изначально в ячейку <tex>h_i(x)</tex>. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <tex>x</tex> в ячейку <tex>h_i(x)</tex>, чтобы в ячейку <tex>h_j(x) ~(i \ne j) </tex> мы смогли поместить какой-то <tex>y</tex> (это может произойти, если в ходе перемещений элемент <tex>x</tex> был перемещен в ячейку <tex>h_j(x)</tex>), то произошло зацикливание.
 +
 +
Например, зацикливание возникнет, если добавить в хэш-таблицу <tex>3</tex> элемента <tex>x,y,z</tex> у которых <tex>h_1(x)=h_1(y)=h_1(z)</tex>  и <tex>h_2(x)=h_2(y)=h_2(z)</tex> .
 +
 +
Одним из способов решения проблемы зацикливания является смена хэш-функции, что было доказано Джоном Трампом<ref>https://eprint.iacr.org/2014/059.pdf</ref>
  
 
==Время работы алгоритма==
 
==Время работы алгоритма==
  
−
Удаление и проверка происходят за <tex>O(1)</tex> (что является основной особенностью данного типа хеширования), добавление в среднем происходит за <tex>O(1)</tex>. Первые два утверждения очевидны: требуется проверить всего лишь 2 ячейки таблицы.  
+
Удаление и проверка происходят за <tex>O(1)</tex> (что является основной особенностью данного типа хеширования), добавление в среднем происходит за <tex>O(1)</tex>. Первые два утверждения очевидны: требуется проверить всего лишь <tex>2</tex> ячейки таблицы.  
 +
 
 +
{{ Утверждение
 +
|id = Cuckoo_hashing add
 +
|statement = Добавление в среднем происходит за <tex>O(1)</tex>.
 +
|proof = Один из способов доказательства данного утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла.
 +
}}
 +
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.
 +
 
 +
==Плюсы и минусы алгоритма==
  
−
Один из способов доказательства третьего утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла.
+
Есть другие алгоритмы, которые используют несколько хеш-функций, в частности [[Фильтр Блума|фильтр Блума]], эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума<ref>''Bin Fan, Michael Kaminsky, David Andersen'' Cuckoo Filter: Better Than Bloom // ;login:. — USENIX, 2013. — Т. 38, вып. 4. — С. 36–40.</ref>.
  
−
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.
+
Исследования, проведённые Жуковским, Хеманом и Бонзом<ref>''Marcin Zukowski, Sandor Heman, Peter Boncz'' Architecture-Conscious Hashing. — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006.</ref>, показали, что кукушкино хеширование существенно быстрее метода цепочек для малых хеш-таблиц, находящихся в кэше современных процессоров. Кеннет Росс<ref>''Kenneth Ross'' Efficient Hash Probes on Modern Processors. — IBM Research Report RC24100, 2006.</ref> показал блочную версию кукушкиного хеширования (блок содержит более одного ключа), который работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы позднее исследовал Аскитис по сравнению с другими схемами хэширования.
 +
 
 +
Обзор Мутцемахера<ref>''M. Mitzenmacher.'' Proceedings of of the 17th Annual European Symposium on Algorithms (ESA). — 2009.</ref> представляет открытые проблемы, связанные с кукушкиным хешированием.
 +
 
 +
Самый большой минуc {{---}} потраченная память. Чтобы гарантировать <tex>O(n)</tex> по времени, нужно чтобы пары ключ/значение занимали не более <tex>50\%</tex> памяти, потому что вытеснение старых элементов становится трудоемким. Также, добавление каждой новой хеш-функции значительно увеличивает среднюю скорость заполнения таблицы.
 +
 
 +
==См. также==
 +
* [[Хеш-таблица]]
 +
* [[Разрешение коллизий]]
 +
* [[Идеальное хеширование]]
 +
 
 +
==Примечания==
 +
<references/>
 +
 
 +
==Источники информации==
 +
* [http://en.wikipedia.org/wiki/Cuckoo_hashing Wikipedia — Cuckoo hashing]
 +
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/hash/PaRo01.pdf Cuckoo hashing — Pagh, Rasmus; Rodler, Flemming Friche (2001) (PDF, PS)]
 +
 
 +
== Примеры ==
 +
* [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]
 +
* [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]
  
−
==Источники==
 
−
* [http://en.wikipedia.org/wiki/Cuckoo_hashing Wikipedia, the free encyclopedia]
 
−
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/hash/PaRo01.pdf Pagh, Rasmus; Rodler, Flemming Friche (2001) (PDF, PS)]
 
  
−
[[Категория:Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Хеширование]]

Текущая версия на 19:37, 4 сентября 2022

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

Хеширование кукушки(англ. Cuckoo hashing) — один из способов борьбы с коллизиями при создании хеш-таблицы.

Алгоритм

Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее [math]h_1(x)[/math] и [math]h_2(x)[/math]). Также есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций [math]add(x), remove(x)[/math] и [math]contains(x)[/math].

Выберем [math]2[/math] хэш-функции [math]h_1(x)[/math] и [math]h_2(x)[/math] (из универсального семейства хэш-функций).

Add

Добавляет элемент с ключом [math]x[/math] в хэш-таблицу

  1. Если одна из ячеек с индексами [math]h_1(x)[/math] или [math]h_2(x)[/math] свободна, кладем в нее элемент.
  2. Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
  3. Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее.
  4. Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
  5. Если не зациклились, то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся.
  6. Иначе выбираем [math]2[/math] новые хеш-функции и перехешируем все добавленные элементы.
  7. Также после добавления нужно увеличить размер таблицы в случае если она заполнена.

Remove

Удаляет элемент с ключом [math]x[/math] из хэш-таблицы.

  1. Смотрим ячейки с индексами [math]h_1(x)[/math] и [math]h_2(x)[/math].
  2. Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.

Contains

Проверяет на наличие элемента [math]x[/math] в хэш-таблице

  1. Смотрим ячейки с индексами [math]h_1(x)[/math] и [math]h_2(x)[/math].
  2. Если в одной из них есть искомый элемент, возвращаем true.
  3. Иначе возвращаем false.

Зацикливание

Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент [math]x[/math]. И обе ячейки [math]h_1(x)[/math] и [math]h_2(x)[/math] заняты. Элемент [math]x[/math] положили изначально в ячейку [math]h_i(x)[/math]. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент [math]x[/math] в ячейку [math]h_i(x)[/math], чтобы в ячейку [math]h_j(x) ~(i \ne j) [/math] мы смогли поместить какой-то [math]y[/math] (это может произойти, если в ходе перемещений элемент [math]x[/math] был перемещен в ячейку [math]h_j(x)[/math]), то произошло зацикливание.

Например, зацикливание возникнет, если добавить в хэш-таблицу [math]3[/math] элемента [math]x,y,z[/math] у которых [math]h_1(x)=h_1(y)=h_1(z)[/math] и [math]h_2(x)=h_2(y)=h_2(z)[/math] .

Одним из способов решения проблемы зацикливания является смена хэш-функции, что было доказано Джоном Трампом[1]

Время работы алгоритма

Удаление и проверка происходят за [math]O(1)[/math] (что является основной особенностью данного типа хеширования), добавление в среднем происходит за [math]O(1)[/math]. Первые два утверждения очевидны: требуется проверить всего лишь [math]2[/math] ячейки таблицы.

Утверждение:
Добавление в среднем происходит за [math]O(1)[/math].
[math]\triangleright[/math]
Один из способов доказательства данного утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла.
[math]\triangleleft[/math]

Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.

Плюсы и минусы алгоритма

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

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

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

Самый большой минуc — потраченная память. Чтобы гарантировать [math]O(n)[/math] по времени, нужно чтобы пары ключ/значение занимали не более [math]50\%[/math] памяти, потому что вытеснение старых элементов становится трудоемким. Также, добавление каждой новой хеш-функции значительно увеличивает среднюю скорость заполнения таблицы.

См. также

Примечания

  1. ↑ https://eprint.iacr.org/2014/059.pdf
  2. ↑ Bin Fan, Michael Kaminsky, David Andersen Cuckoo Filter: Better Than Bloom // ;login:. — USENIX, 2013. — Т. 38, вып. 4. — С. 36–40.
  3. ↑ Marcin Zukowski, Sandor Heman, Peter Boncz Architecture-Conscious Hashing. — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006.
  4. ↑ Kenneth Ross Efficient Hash Probes on Modern Processors. — IBM Research Report RC24100, 2006.
  5. ↑ M. Mitzenmacher. Proceedings of of the 17th Annual European Symposium on Algorithms (ESA). — 2009.

Источники информации

Примеры

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Хеширование_кукушки&oldid=85631»