Хеширование кукушки — различия между версиями
Watson (обсуждение | вклад) (→Источники) |
Watson (обсуждение | вклад) (→Источники) |
||
Строка 50: | Строка 50: | ||
[[Категория: Дискретная математика и алгоритмы ]] | [[Категория: Дискретная математика и алгоритмы ]] | ||
− | [[Категория: Цепные коды ]] | + | [[Категория:Цепные коды]] |
Версия 21:31, 23 апреля 2012
![](/wiki/images/5/5b/Cuckoo.png)
Пример хеширования кукушки. Стрелки показывают второе возможное место элементов. Если нам надо будет вставить новый элемент на место А, то мы поместим А в его вторую ячейку, занятую В, а В переместим в его вторую ячейку, которая сейчас свободна. А вот помещение нового элемента на место Н не получится: так как Н — часть цикла, добавленный элемент будет вытеснен после прохода по циклу.
Хеширование кукушки — один из способов борьбы с коллизиями при создании хеш-таблицы.
Алгоритм
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее
и . Так же есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), delete(x) и exists(x).Add — добавляет элемент с ключом
в хэш-таблицу- Если одна из ячеек с индексами или свободна, кладем в нее элемент. Переходим к шагу 7.
- Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
- Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. Переходим к шагу 7.
- Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
- Если не зациклились, переходим к шагу 3.
- Иначе выбираем 2 новые хеш-функции и перехешируем все добавленные элементы.
- Помечаем ячейку, в которую только что добавили элемент, как занятую.
Delete — удаляет элемент с ключом
из хэш-таблицы.- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.
Exists — проверяет на наличие элемента
в хэш-таблице- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, возвращаем true.
- Иначе возвращаем false.
Зацикливание
Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент
. И обе ячейки и заняты. Пусть, для определенности, элемент положили в ячейку . Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент в ячейку то значит произошло зацикливание.Например зацикливание возникнет если добавить в хэш-таблицу 3 элемента
у которых = = и = = равны.Время работы алгоритма
Удаление и проверка происходят за
(что является основной особенностью данного типа хеширования), добавление в среднем происходит за . Первые два утверждения очевидны: требуется проверить всего лишь 2 ячейки таблицы.Утверждение: |
Добавление в среднем происходит за . |
Один из способов доказательства данного утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла. |
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.