Хеширование кукушки — различия между версиями
(Новая страница: «'''Хеширование кукушки''' — один из способов борьбы с коллизиями при создании хеш-таблицы. =…») |
|||
| Строка 2: | Строка 2: | ||
==Алгоритм== | ==Алгоритм== | ||
| + | |||
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <math>h_1(x)</math> и <math>h_2(x)</math>). Так же есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), delete(x) и exists(x). | Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <math>h_1(x)</math> и <math>h_2(x)</math>). Так же есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), delete(x) и exists(x). | ||
| + | |||
===Add=== | ===Add=== | ||
| + | |||
# Если одна из ячеек с индексами <math>h_1(x)</math> или <math>h_2(x)</math> свободна, кладем в нее элемент. Переходим к шагу 7. | # Если одна из ячеек с индексами <math>h_1(x)</math> или <math>h_2(x)</math> свободна, кладем в нее элемент. Переходим к шагу 7. | ||
# Иначе произвольно выбираем одну из этих ячеек, вытаскиваем оттуда элемент, помещаем туда новый. | # Иначе произвольно выбираем одну из этих ячеек, вытаскиваем оттуда элемент, помещаем туда новый. | ||
| Строка 11: | Строка 14: | ||
# Иначе выбираем 2 новые хеш-функции и перехешируем все добавленные элементы. | # Иначе выбираем 2 новые хеш-функции и перехешируем все добавленные элементы. | ||
# Помечаем ячейку, в которую только что добавили элемент, как занятую. | # Помечаем ячейку, в которую только что добавили элемент, как занятую. | ||
| + | |||
===Delete=== | ===Delete=== | ||
| + | |||
# Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>. | # Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>. | ||
# Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную. | # Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную. | ||
| + | |||
===Exists=== | ===Exists=== | ||
| + | |||
# Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>. | # Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>. | ||
# Если в одной из них есть искомый элемент, возвращаем true. | # Если в одной из них есть искомый элемент, возвращаем true. | ||
# Иначе возвращаем false. | # Иначе возвращаем false. | ||
| + | |||
| + | ==Время работы алгоритма== | ||
| + | |||
| + | Удаление и проверка происходят за О(1) (что является основной особенностью данного типа хеширования), добавление в среднем происходит за О(1). Первые два утверждения очевидны: требуется проверить всего лишь 2 ячейки таблицы. | ||
| + | |||
| + | Один из способов доказательства третьего утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла. | ||
| + | |||
| + | Таким образом хеширование кукушки является одним из самых быстрых способов хеширования. | ||
Версия 03:01, 17 мая 2011
Хеширование кукушки — один из способов борьбы с коллизиями при создании хеш-таблицы.
Алгоритм
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее и ). Так же есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), delete(x) и exists(x).
Add
- Если одна из ячеек с индексами или свободна, кладем в нее элемент. Переходим к шагу 7.
- Иначе произвольно выбираем одну из этих ячеек, вытаскиваем оттуда элемент, помещаем туда новый.
- Смотрим в ячейку, на которую указывает другая хеш-функция от только что вытащенного элемента, если она свободна, помещаем его в нее. Переходим к шагу 7.
- Иначе вытаскиваем из этой ячейки элемент, кладем туда старый. Проверяем, не зациклились ли мы.
- Если не зациклились, переходим к шагу 3.
- Иначе выбираем 2 новые хеш-функции и перехешируем все добавленные элементы.
- Помечаем ячейку, в которую только что добавили элемент, как занятую.
Delete
- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.
Exists
- Смотрим ячейки с индексами и .
- Если в одной из них есть искомый элемент, возвращаем true.
- Иначе возвращаем false.
Время работы алгоритма
Удаление и проверка происходят за О(1) (что является основной особенностью данного типа хеширования), добавление в среднем происходит за О(1). Первые два утверждения очевидны: требуется проверить всего лишь 2 ячейки таблицы.
Один из способов доказательства третьего утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла.
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.
