Перехеширование — различия между версиями
(→При закрытом хешировании) |
м (rollbackEdits.php mass rollback) |
||
(не показано 35 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
− | При добавлении в хеш-таблицу большого количества элементов могут возникнуть ухудшения в ее работе. Обработка любого вызова будет занимать больше времени из-за увеличения размеров цепочек при | + | При добавлении в хеш-таблицу большого количества элементов могут возникнуть ухудшения в ее работе. Обработка любого вызова будет занимать больше времени из-за увеличения размеров цепочек при хешировании на списках или кластеризации при хешировании с открытой адресацией, также, при хешировании с открытой адресацией может произойти переполнение таблицы. Для избежания таких ситуаций используется выбор новой хеш-функции и (или) хеш-таблица большего размера. Этот процесс называется '''перехеширование''' (''rehashing''). |
+ | |||
+ | |||
==Перехеширование при разных типах хеширования== | ==Перехеширование при разных типах хеширования== | ||
− | |||
− | |||
− | + | ===При хешировании цепочками=== | |
− | + | При использовании [[Разрешение коллизий|хеширования цепочками]] , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <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{2n}{3}</tex> операций <tex>\mathrm{add(x)}</tex>, так как изначально в массиве находится <tex dpi = "150">\frac{2n}{3}</tex> элементов (или <tex>0</tex> в начале работы), а перехеширование происходит при наличии <tex dpi = "150">\frac{4n}{3}</tex> элементов. | |
− | |||
− | Будем проводить перехеширование при заполнении таблицы на <tex dpi = "150">\frac{n}{2}</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(n)</tex> операций на обход таблицы, <tex>O(n)\cdot A</tex> элементарных операций на добавление элементов, где <tex>A</tex> - стоимость операции <tex> | + | Для проведения перехеширования необходимо произвести <tex dpi = "150">\frac{4n}{3}</tex> операций <tex>\mathrm{add}(x)</tex>, средняя стоимость которых составляет <tex>O(1)</tex> , потратить <tex dpi = "150">\frac{4n}{3}</tex> операций на проход хеш-таблицы, и <tex dpi = "150">\frac{4n}{3}</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>\mathrm{add}(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>. |
+ | |||
+ | ===При хешировании с открытой адресацией=== | ||
+ | При использовании [[Разрешение коллизий|хеширования цепочками]] , операции <tex>\mathrm{add}(x)</tex>, <tex>\mathrm{contains}(x)</tex> и <tex>\mathrm{remove(x)}</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> {{---}} количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы. | ||
+ | |||
+ | Будем проводить перехеширование при заполнении таблицы на <tex dpi = "150">\frac{n}{2}</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(n)</tex> операций на обход таблицы, <tex>O(n)\cdot A</tex> элементарных операций на добавление элементов, где <tex>A</tex> {{---}} стоимость операции <tex>\mathrm{add(x)}</tex>, и <tex>O(n)</tex> операций на удаление таблицы. Так как <tex>A \geqslant 1</tex>, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции <tex>\mathrm{add(x)}</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций. | ||
==См. также== | ==См. также== | ||
Строка 20: | Строка 24: | ||
* [[Открытое и закрытое хеширование]] | * [[Открытое и закрытое хеширование]] | ||
− | ==Источники== | + | ==Источники информации== |
− | * ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' | + | * ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.) |
+ | * Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0 | ||
+ | <references/> | ||
+ | |||
[[Категория: Дискретная математика и алгоритмы ]] | [[Категория: Дискретная математика и алгоритмы ]] | ||
[[Категория: Амортизационный анализ]] | [[Категория: Амортизационный анализ]] | ||
[[Категория: Хеширование]] | [[Категория: Хеширование]] |
Текущая версия на 19:12, 4 сентября 2022
При добавлении в хеш-таблицу большого количества элементов могут возникнуть ухудшения в ее работе. Обработка любого вызова будет занимать больше времени из-за увеличения размеров цепочек при хешировании на списках или кластеризации при хешировании с открытой адресацией, также, при хешировании с открытой адресацией может произойти переполнение таблицы. Для избежания таких ситуаций используется выбор новой хеш-функции и (или) хеш-таблица большего размера. Этот процесс называется перехеширование (rehashing).
Перехеширование при разных типах хеширования
При хешировании цепочками
При использовании хеширования цепочками , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции , и работают за , где — длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции .
Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено
элементов, где — размер хеш-таблицы, создадим новую хеш-таблицу размера , и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения .Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования было произведено не менее
операций , так как изначально в массиве находится элементов (или в начале работы), а перехеширование происходит при наличии элементов.Для проведения перехеширования необходимо произвести
операций , средняя стоимость которых составляет , потратить операций на проход хеш-таблицы, и операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции на , то есть на , операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна .При хешировании с открытой адресацией
При использовании хеширования цепочками , операции , и в худшем случае работают за , где — количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.
Будем проводить перехеширование при заполнении таблицы на
, увеличивая размер таблицы в раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить операций на обход таблицы, элементарных операций на добавление элементов, где — стоимость операции , и операций на удаление таблицы. Так как , и между последовательными перехешированиями производится добавлений, то можно предоплатить перехеширование, увеличив стоимость операции на , и не изменив стоимость остальных операций.См. также
Источники информации
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
- Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г.— ISBN 0-201-89685-0