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

Материал из Викиконспекты
Перейти к: навигация, поиск
(При закрытом типе)
Строка 6: Строка 6:
 
==Перехеширование при разных типах хеширования==
 
==Перехеширование при разных типах хеширования==
 
===При открытом типе===
 
===При открытом типе===
При использовании открытого[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D0%B8_%D0%B7%D0%B0%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.9E.D1.82.D0.BA.D1.80.D1.8B.D1.82.D0.BE.D0.B5_.D1.85.D0.B5.D1.88.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5] метода, элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <tex>Add(x)</tex>, <tex>Exists(x)</tex> и <tex>Delete(x)</tex> работают за <tex>O(l)</tex>, где <tex>l</tex> - длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex>.
+
При использовании [[Открытое и закрытое хеширование#Открытое хеширование|открытого]] метода, элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <tex>Add(x)</tex>, <tex>Exists(x)</tex> и <tex>Delete(x)</tex> работают за <tex>O(l)</tex>, где <tex>l</tex> - длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex>.
  
 
Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено <tex>\frac{4}{3}n</tex> элементов, где <tex>n</tex> - размер хеш-таблицы, создадим новую хеш-таблицу размера <tex>2n</tex>, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения <tex>[0..2n-1]</tex> (в функциях, использующих остаток от деления на длину таблицы, достаточно брать остаток от деления на <tex>2n</tex>).  
 
Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено <tex>\frac{4}{3}n</tex> элементов, где <tex>n</tex> - размер хеш-таблицы, создадим новую хеш-таблицу размера <tex>2n</tex>, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения <tex>[0..2n-1]</tex> (в функциях, использующих остаток от деления на длину таблицы, достаточно брать остаток от деления на <tex>2n</tex>).  
Строка 15: Строка 15:
  
 
===При закрытом типе===
 
===При закрытом типе===
При использовании хеширования с открытой адресацией, или закрытого[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D0%B8_%D0%B7%D0%B0%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.97.D0.B0.D0.BA.D1.80.D1.8B.D1.82.D0.BE.D0.B5_.D1.85.D0.B5.D1.88.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5] хеширования, операции <tex>Add(x)</tex>, <tex>Exists(x)</tex> и <tex>Delete(x)</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> - количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.
+
При использовании хеширования с открытой адресацией, или [[Открытое и закрытое хеширование#Закрытое хеширование|закрытого]] хеширования, операции <tex>Add(x)</tex>, <tex>Exists(x)</tex> и <tex>Delete(x)</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> - количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.
  
 
Будем проводить перехеширование при заполнении таблицы на <tex>\frac{1}{2}n</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(n)</tex> операций на обход таблицы, <tex>O(n)</tex> операций добавления, и <tex>O(n)</tex> операций на удаление таблицы. Так как операция добавления имеет не меньшую стоимость, чем элементарная операция, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции <tex>Add(x)</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций.
 
Будем проводить перехеширование при заполнении таблицы на <tex>\frac{1}{2}n</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(n)</tex> операций на обход таблицы, <tex>O(n)</tex> операций добавления, и <tex>O(n)</tex> операций на удаление таблицы. Так как операция добавления имеет не меньшую стоимость, чем элементарная операция, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции <tex>Add(x)</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций.

Версия 01:55, 11 июня 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].

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

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

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

См. также

Источники

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