Хеширование кукушки
![](/wiki/images/5/5b/Cuckoo.png)
Хеширование кукушки(англ. Cuckoo hashing) — один из способов борьбы с коллизиями при создании хеш-таблицы.
Алгоритм
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее
и ). Также есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций и .Выберем универсального семейства хэш-функций).
хэш-функции и (изAdd
Добавляет элемент с ключом
в хэш-таблицу- Если одна из ячеек с индексами или свободна, кладем в нее элемент.
- Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
- Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее.
- Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
- Если не зациклились, то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся.
- Иначе выбираем новые хеш-функции и перехешируем все добавленные элементы.
- Так же после добавления нужно увеличить размер таблицы в случае если она заполнена.
Remove
Удаляет элемент с ключом
из хэш-таблицы.- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.
Contains
Проверяет на наличие элемента
в хэш-таблице- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, возвращаем true.
- Иначе возвращаем false.
Зацикливание
Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент
. И обе ячейки и заняты. Элемент положили изначально в ячейку . Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент в ячейку , чтобы в ячейку мы смогли поместить какой-то (это может произойти, если в ходе перемещений элемент был перемещен в ячейку ), то произошло зацикливание.Например, зацикливание возникнет, если добавить в хэш-таблицу
элемента у которых и .Одним из способов решения проблемы зацикливания является смена хэш-функции, что было доказано Джоном Трампом[1]
Время работы алгоритма
Удаление и проверка происходят за
(что является основной особенностью данного типа хеширования), добавление в среднем происходит за . Первые два утверждения очевидны: требуется проверить всего лишь ячейки таблицы.Утверждение: |
Добавление в среднем происходит за . |
Один из способов доказательства данного утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла. |
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.
Плюсы и минусы алгоритма
Есть другие алгоритмы, которые используют несколько хеш-функций, в частности фильтр Блума, эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума[2].
Исследования, проведённые Жуковским, Хеманом и Бонзом[3], показали, что кукушкино хеширование существенно быстрее метода цепочек для малых хеш-таблиц, находящихся в кэше современных процессоров. Кеннет Росс[4] показал блочную версию кукушкиного хеширования (блок содержит более одного ключа), который работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы позднее исследовал Аскитис по сравнению с другими схемами кэширования.
Обзор Мутцемахера[5] представляет открытые проблемы, связанные с кукушкиным хешированием.
Самый большой минус—потраченная память. Чтобы гарантировать
по времени, нужно чтобы пары ключ/значение занимали не более памяти,потому что вытеснение старых элементов становится трудоемким и таблица должна быть изменена.Также, добавление каждой новой хэш функции значительно увеличивает среднюю скорость заполнения таблицы.См. также
Примечания
- ↑ 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.