Хеширование кукушки — различия между версиями
Rybak (обсуждение | вклад) (→Зацикливание) |
м (rollbackEdits.php mass rollback) |
||
(не показано 45 промежуточных версий 8 участников) | |||
Строка 1: | Строка 1: | ||
[[Image:cuckoo.png|thumb|Пример хеширования кукушки. Стрелки показывают второе возможное место элементов. Если нам надо будет вставить новый элемент на место А, то мы поместим А в его вторую ячейку, занятую В, а В переместим в его вторую ячейку, которая сейчас свободна. А вот помещение нового элемента на место Н не получится: так как Н — часть цикла, добавленный элемент будет вытеснен после прохода по циклу.]] | [[Image:cuckoo.png|thumb|Пример хеширования кукушки. Стрелки показывают второе возможное место элементов. Если нам надо будет вставить новый элемент на место А, то мы поместим А в его вторую ячейку, занятую В, а В переместим в его вторую ячейку, которая сейчас свободна. А вот помещение нового элемента на место Н не получится: так как Н — часть цикла, добавленный элемент будет вытеснен после прохода по циклу.]] | ||
− | '''Хеширование кукушки''' | + | '''Хеширование кукушки'''(англ. ''Cuckoo hashing'') {{---}} один из способов [[Разрешение коллизий|борьбы с коллизиями]] при создании [[Хеш-таблица|хеш-таблицы]]. |
==Алгоритм== | ==Алгоритм== | ||
− | Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <tex>h_1(x)</tex> и <tex>h_2(x)</tex>. | + | Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <tex>h_1(x)</tex> и <tex>h_2(x)</tex>). Также есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций <tex>add(x), remove(x)</tex> и <tex>contains(x)</tex>. |
− | + | Выберем <tex>2</tex> хэш-функции <tex>h_1(x)</tex> и <tex>h_2(x)</tex> (из [[Универсальное семейство хеш-функций | универсального семейства хэш-функций]]). | |
− | # Если одна из ячеек с индексами <tex>h_1(x)</tex> или <tex>h_2(x)</tex> свободна, кладем в нее элемент | + | ===='''Add'''==== |
+ | Добавляет элемент с ключом <tex>x</tex> в хэш-таблицу | ||
+ | |||
+ | # Если одна из ячеек с индексами <tex>h_1(x)</tex> или <tex>h_2(x)</tex> свободна, кладем в нее элемент. | ||
# Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый. | # Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый. | ||
− | # Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее | + | # Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. |
# Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы. | # Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы. | ||
− | # Если не зациклились, | + | # Если не зациклились, то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся. |
− | # Иначе выбираем 2 новые хеш-функции | + | # Иначе выбираем <tex>2</tex> новые хеш-функции и перехешируем все добавленные элементы. |
− | # | + | # Также после добавления нужно увеличить размер таблицы в случае если она заполнена. |
− | |||
− | ''' | + | ===='''Remove'''==== |
+ | Удаляет элемент с ключом <tex>x</tex> из хэш-таблицы. | ||
# Смотрим ячейки с индексами <tex>h_1(x)</tex> и <tex>h_2(x)</tex>. | # Смотрим ячейки с индексами <tex>h_1(x)</tex> и <tex>h_2(x)</tex>. | ||
# Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную. | # Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную. | ||
− | ''' | + | ===='''Contains'''==== |
+ | Проверяет на наличие элемента <tex>x</tex> в хэш-таблице | ||
# Смотрим ячейки с индексами <tex>h_1(x)</tex> и <tex>h_2(x)</tex>. | # Смотрим ячейки с индексами <tex>h_1(x)</tex> и <tex>h_2(x)</tex>. | ||
Строка 31: | Строка 35: | ||
== Зацикливание == | == Зацикливание == | ||
− | Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <tex>x</tex>. И обе ячейки <tex>h_1(x)</tex> и <tex>h_2(x)</tex> заняты. | + | Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <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> ячейки таблицы. |
{{ Утверждение | {{ Утверждение | ||
Строка 45: | Строка 51: | ||
}} | }} | ||
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования. | Таким образом хеширование кукушки является одним из самых быстрых способов хеширования. | ||
+ | |||
+ | ==Плюсы и минусы алгоритма== | ||
+ | |||
+ | Есть другие алгоритмы, которые используют несколько хеш-функций, в частности [[Фильтр Блума|фильтр Блума]], эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума<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://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)] | * [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] | ||
+ | |||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Хеширование]] | [[Категория: Хеширование]] |
Текущая версия на 19:37, 4 сентября 2022
![](/wiki/images/5/5b/Cuckoo.png)
Хеширование кукушки(англ. Cuckoo hashing) — один из способов борьбы с коллизиями при создании хеш-таблицы.
Содержание
Алгоритм
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее
и ). Также есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций и .Выберем универсального семейства хэш-функций).
хэш-функции и (изAdd
Добавляет элемент с ключом
в хэш-таблицу- Если одна из ячеек с индексами или свободна, кладем в нее элемент.
- Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
- Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее.
- Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
- Если не зациклились, то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся.
- Иначе выбираем новые хеш-функции и перехешируем все добавленные элементы.
- Также после добавления нужно увеличить размер таблицы в случае если она заполнена.
Remove
Удаляет элемент с ключом
из хэш-таблицы.- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.
Contains
Проверяет на наличие элемента
в хэш-таблице- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, возвращаем true.
- Иначе возвращаем false.
Зацикливание
Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент
. И обе ячейки и заняты. Элемент положили изначально в ячейку . Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент в ячейку , чтобы в ячейку мы смогли поместить какой-то (это может произойти, если в ходе перемещений элемент был перемещен в ячейку ), то произошло зацикливание.Например, зацикливание возникнет, если добавить в хэш-таблицу
элемента у которых и .Одним из способов решения проблемы зацикливания является смена хэш-функции, что было доказано Джоном Трампом[1]
Время работы алгоритма
Удаление и проверка происходят за
(что является основной особенностью данного типа хеширования), добавление в среднем происходит за . Первые два утверждения очевидны: требуется проверить всего лишь ячейки таблицы.Утверждение: |
Добавление в среднем происходит за . |
Один из способов доказательства данного утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла. |
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.
Плюсы и минусы алгоритма
Есть другие алгоритмы, которые используют несколько хеш-функций, в частности фильтр Блума, эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума[2].
Исследования, проведённые Жуковским, Хеманом и Бонзом[3], показали, что кукушкино хеширование существенно быстрее метода цепочек для малых хеш-таблиц, находящихся в кэше современных процессоров. Кеннет Росс[4] показал блочную версию кукушкиного хеширования (блок содержит более одного ключа), который работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы позднее исследовал Аскитис по сравнению с другими схемами хэширования.
Обзор Мутцемахера[5] представляет открытые проблемы, связанные с кукушкиным хешированием.
Самый большой минуc — потраченная память. Чтобы гарантировать
по времени, нужно чтобы пары ключ/значение занимали не более памяти, потому что вытеснение старых элементов становится трудоемким. Также, добавление каждой новой хеш-функции значительно увеличивает среднюю скорость заполнения таблицы.См. также
Примечания
- ↑ https://eprint.iacr.org/2014/059.pdf
- ↑ 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.
- ↑ M. Mitzenmacher. Proceedings of of the 17th Annual European Symposium on Algorithms (ESA). — 2009.