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

Материал из Викиконспекты
Перейти к: навигация, поиск
(При открытом типе)
Строка 13: Строка 13:
 
Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования было произведено не менее <tex>\frac{2}{3}n</tex> операций <tex>Add(x)</tex>, так как изначально в массиве находится <tex>\frac{2}{3}n</tex> элементов (или <tex>0</tex> в начале работы), а перехеширование происходит при наличии <tex>\frac{4}{3}n</tex> элементов.  
 
Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования было произведено не менее <tex>\frac{2}{3}n</tex> операций <tex>Add(x)</tex>, так как изначально в массиве находится <tex>\frac{2}{3}n</tex> элементов (или <tex>0</tex> в начале работы), а перехеширование происходит при наличии <tex>\frac{4}{3}n</tex> элементов.  
  
Для проведения перехеширования необходимо произвести <tex>\frac{4}{3}n</tex> операций <tex>Add(x)</tex>, средняя стоимость которых составляет <tex>O(1)</tex> (Анализ открытого хеширования см. Т.Корман, второе издание, стр. 288), потратить <tex>\frac{4}{3}n</tex> операций на проход хеш-таблицы, и <tex>\frac{4}{3}n</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>Add(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>.
+
Для проведения перехеширования необходимо произвести <tex>\frac{4}{3}n</tex> операций <tex>Add(x)</tex>, средняя стоимость которых составляет <tex>O(1)</tex> ''(Анализ открытого хеширования см. Т.Корман, второе издание, стр. 288)'', потратить <tex>\frac{4}{3}n</tex> операций на проход хеш-таблицы, и <tex>\frac{4}{3}n</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>Add(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>.
 +
 
 
===При закрытом типе===
 
===При закрытом типе===
  

Версия 19:14, 10 июня 2011

При любом виде хеширования возникают коллизии. В случае открытого хеширования большое количество коллизий приведет к большой длине цепочек, при закрытом или двойном хешировании - к переполнению массива.


Определение:
Перехеширование - процесс перехода к новой хеш-функции и (или) хеш-таблице для избежания переполнения таблицы или уменьшения времени работы операций с хеш-таблицей.


Перехеширование при разных типах хеширования

При открытом типе

При использовании открытого метода, элементы с одинаковым результатом хеш-функции помещают в список. Так как операции [math]Add(x)[/math], [math]Exists(x)[/math] и [math]Delete(x)[/math] работают за [math]O(l)[/math], где [math]l[/math] - длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции [math]O(1)[/math].

Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено [math]\frac{4}{3}n[/math] элементов, где [math]n[/math] - размер хеш-таблицы, создадим новую хеш-таблицу размера [math]2n[/math], и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения [math][0..2n-1][/math] (в функциях, использующих остаток от деления на длину таблицы, достаточно брать остаток от деления на [math]2n[/math]).

Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования было произведено не менее [math]\frac{2}{3}n[/math] операций [math]Add(x)[/math], так как изначально в массиве находится [math]\frac{2}{3}n[/math] элементов (или [math]0[/math] в начале работы), а перехеширование происходит при наличии [math]\frac{4}{3}n[/math] элементов.

Для проведения перехеширования необходимо произвести [math]\frac{4}{3}n[/math] операций [math]Add(x)[/math], средняя стоимость которых составляет [math]O(1)[/math] (Анализ открытого хеширования см. Т.Корман, второе издание, стр. 288), потратить [math]\frac{4}{3}n[/math] операций на проход хеш-таблицы, и [math]\frac{4}{3}n[/math] операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции [math]Add(x)[/math] на [math]6[/math], то есть на [math]O(1)[/math], операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна [math]O(1)[/math].

При закрытом типе

См. также

Источники

  • Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ, 2-е изд