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

Материал из Викиконспекты
Перейти к: навигация, поиск
(При хешировании цепочками)
(При хешировании цепочками)
Строка 6: Строка 6:
 
===При хешировании цепочками===
 
===При хешировании цепочками===
  
При использовании [[Разрешение коллизий|хеширования цепочками]] , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <tex>\mathrm{add(x)}</tex>, <tex>\mathrm{contains(x)}</tex> и <tex>\mathrm{remove(x)}</tex> работают за <tex>O(l)</tex>, где <tex>l</tex> {{---}} длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex>.
+
При использовании [[Разрешение коллизий*Разрешение коллизий с помощью цепочек|хеширования цепочками]] , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <tex>\mathrm{add(x)}</tex>, <tex>\mathrm{contains(x)}</tex> и <tex>\mathrm{remove(x)}</tex> работают за <tex>O(l)</tex>, где <tex>l</tex> {{---}} длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex>.
  
 
Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено <tex dpi = "150">\frac{4n}{3}</tex> элементов, где <tex>n</tex> {{---}} размер хеш-таблицы, создадим новую хеш-таблицу размера <tex>2n</tex>, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения <tex>[0..2n-1]</tex>.
 
Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено <tex dpi = "150">\frac{4n}{3}</tex> элементов, где <tex>n</tex> {{---}} размер хеш-таблицы, создадим новую хеш-таблицу размера <tex>2n</tex>, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения <tex>[0..2n-1]</tex>.

Версия 00:42, 28 мая 2015

При добавлении в хеш-таблицу большого количества элементов могут возникнуть ухудшения в ее работе. Обработка любого вызова будет занимать больше времени из-за увеличения размеров цепочек при хешировании на списках или кластеризации при хешировании с открытой адресацией, также, при хешировании с открытой адресацией может произойти переполнение таблицы. Для избежания таких ситуаций используется выбор новой хеш-функции и (или) хеш-таблица большего размера. Этот процесс называется перехеширование (rehashing).


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

При хешировании цепочками

При использовании хеширования цепочками , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции [math]\mathrm{add(x)}[/math], [math]\mathrm{contains(x)}[/math] и [math]\mathrm{remove(x)}[/math] работают за [math]O(l)[/math], где [math]l[/math] — длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции [math]O(1)[/math].

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

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

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

При хеширования с открытой адресацией

При использовании хеширования с открытой адресацией , операции [math]\mathrm{add}(x)[/math], [math]\mathrm{contains}(x)[/math] и [math]\mathrm{remove(x)}[/math] в худшем случае работают за [math]O(k)[/math], где [math]k[/math] — количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.

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

Источники

  • Амортизационный анализ
  • Хеширование
  • Открытое и закрытое хеширование
  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
  • Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г.— ISBN 0-201-89685-0