Изменения

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

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

'''Add''' — добавляет элемент с ключом Выберем <tex>2</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> свободна, кладем в нее элемент. Переходим к шагу 7.

# Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. Переходим к шагу 7.

# Если не зациклились, переходим к шагу 3то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся.# Иначе выбираем <tex>2 </tex> новые хеш-функции и перехешируем все добавленные элементы.# Помечаем ячейку, Также после добавления нужно увеличить размер таблицы в которую только что добавили элемент, как занятуюслучае если она заполнена.

===='''DeleteRemove''' — удаляет ====Удаляет элемент с ключом <tex>x</tex> из хэш-таблицы.

===='''ExistsContains''' — проверяет ====Проверяет на наличие элемента <tex>x</tex> в хэш-таблице

==Зацикливание== Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <tex>x</tex>. И обе ячейки <tex>h_1(x)</tex> и <tex>h_2(x)</tex> заняты. Пусть, для определенности, элемент Элемент <tex>x</tex> положили изначально в ячейку <tex>h_1h_i(x)</tex>. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <tex>x</tex> в ячейку <tex>h_1h_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> .

Например зацикливание возникнет если добавить в Одним из способов решения проблемы зацикливания является смена хэш-таблицу 3 элемента <tex>x,yфункции,z</tex> у которых что было доказано Джоном Трампом<texref>h_1(x)<https:/tex> = <tex>h_1(y)</tex> =<tex>h_1(z)<eprint.iacr.org/tex> и <tex>h_2(x)<2014/tex> = <tex>h_2(y)059.pdf</tex> = <texref>h_2(z)</tex> равны.

Удаление и проверка происходят за <tex>O(1)</tex> (что является основной особенностью данного типа хеширования), добавление в среднем происходит за <tex>O(1)</tex>. Первые два утверждения очевидны: требуется проверить всего лишь <tex>2 </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, the free encyclopedia— 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] 

[[Категория:Дискретная математика Алгоритмы и алгоритмыструктуры данных]][[Категория: Хеширование]]