Изменения
Новая страница: «При любом виде хеширования возникают коллизии. В случае открытого хеширования большое ко…»
При любом виде хеширования возникают коллизии. В случае открытого хеширования большое количество коллизий приведет к большой длине цепочек, при закрытом или двойном хешировании - к переполнению массива.
==Перехеширование при разных типах хеширования==
===При открытом типе===
При использовании [[Открытое и закрытое хеширование|открытого]] метода, элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <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{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>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{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>.
===При закрытом типе===
