Хеширование кукушки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники)
(Источники)
Строка 52: Строка 52:
 
==Источники==
 
==Источники==
 
* [http://en.wikipedia.org/wiki/Cuckoo_hashing Wikipedia — Cuckoo hashing]
 
* [http://en.wikipedia.org/wiki/Cuckoo_hashing Wikipedia — Cuckoo hashing]
* Cuckoo hashing — [http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/hash/PaRo01.pdf 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)]
  
 
[[Категория: Дискретная математика и алгоритмы ]]
 
[[Категория: Дискретная математика и алгоритмы ]]
  
 
[[Категория: Хеширование]]
 
[[Категория: Хеширование]]

Версия 20:39, 24 апреля 2012

Пример хеширования кукушки. Стрелки показывают второе возможное место элементов. Если нам надо будет вставить новый элемент на место А, то мы поместим А в его вторую ячейку, занятую В, а В переместим в его вторую ячейку, которая сейчас свободна. А вот помещение нового элемента на место Н не получится: так как Н — часть цикла, добавленный элемент будет вытеснен после прохода по циклу.

Хеширование кукушки — один из способов борьбы с коллизиями при создании хеш-таблицы.

Алгоритм

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

Add — добавляет элемент с ключом [math]x[/math] в хэш-таблицу

  1. Если одна из ячеек с индексами [math]h_1(x)[/math] или [math]h_2(x)[/math] свободна, кладем в нее элемент. Переходим к шагу 7.
  2. Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
  3. Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. Переходим к шагу 7.
  4. Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
  5. Если не зациклились, переходим к шагу 3.
  6. Иначе выбираем 2 новые хеш-функции(из универсального семейства хэш-функций) и перехешируем все добавленные элементы.
  7. Помечаем ячейку, в которую только что добавили элемент, как занятую.
  8. Если хэш-таблица заполнена увеличиваем её размер.

Delete — удаляет элемент с ключом [math]x[/math] из хэш-таблицы.

  1. Смотрим ячейки с индексами [math]h_1(x)[/math] и [math]h_2(x)[/math].
  2. Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.

Exists — проверяет на наличие элемента [math]x[/math] в хэш-таблице

  1. Смотрим ячейки с индексами [math]h_1(x)[/math] и [math]h_2(x)[/math].
  2. Если в одной из них есть искомый элемент, возвращаем true.
  3. Иначе возвращаем false.

Зацикливание

Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент [math]x[/math]. И обе ячейки [math]h_1(x)[/math] и [math]h_2(x)[/math] заняты. Пусть, для определенности, элемент [math]x[/math] положили в ячейку [math]h_1(x)[/math]. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент [math]x[/math] в ячейку [math]h_1(x)[/math] то значит произошло зацикливание.

Например зацикливание возникнет если добавить в хэш-таблицу 3 элемента [math]x,y,z[/math] у которых [math]h_1(x)[/math] = [math]h_1(y)[/math] =[math]h_1(z)[/math] и [math]h_2(x)[/math] = [math]h_2(y)[/math] = [math]h_2(z)[/math] равны.

Время работы алгоритма

Удаление и проверка происходят за [math]O(1)[/math] (что является основной особенностью данного типа хеширования), добавление в среднем происходит за [math]O(1)[/math]. Первые два утверждения очевидны: требуется проверить всего лишь 2 ячейки таблицы.

Утверждение:
Добавление в среднем происходит за [math]O(1)[/math].
[math]\triangleright[/math]
Один из способов доказательства данного утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла.
[math]\triangleleft[/math]

Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.

См. также

Источники