http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=92.113.116.181&* 2026-07-15T01:31:13Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D0%B5%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5&diff=61914 2017-09-18T05:16:43Z

<p>92.113.116.181: /* При хеширования с открытой адресацией */</p> <hr /> <div>При добавлении в хеш-таблицу большого количества элементов могут возникнуть ухудшения в ее работе. Обработка любого вызова будет занимать больше времени из-за увеличения размеров цепочек при хешировании на списках или кластеризации при хешировании с открытой адресацией, также, при хешировании с открытой адресацией может произойти переполнение таблицы. Для избежания таких ситуаций используется выбор новой хеш-функции и (или) хеш-таблица большего размера. Этот процесс называется '''перехеширование''' (''rehashing'').<br /> <br /> <br /> ==Перехеширование при разных типах хеширования==<br /> <br /> ===При хешировании цепочками===<br /> <br /> При использовании [[Разрешение коллизий|хеширования цепочками]] , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции &lt;tex&gt;\mathrm{add(x)}&lt;/tex&gt;, &lt;tex&gt;\mathrm{contains(x)}&lt;/tex&gt; и &lt;tex&gt;\mathrm{remove(x)}&lt;/tex&gt; работают за &lt;tex&gt;O(l)&lt;/tex&gt;, где &lt;tex&gt;l&lt;/tex&gt; {{---}} длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции &lt;tex&gt;O(1)&lt;/tex&gt;.<br /> <br /> Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено &lt;tex dpi = &quot;150&quot;&gt;\frac{4n}{3}&lt;/tex&gt; элементов, где &lt;tex&gt;n&lt;/tex&gt; {{---}} размер хеш-таблицы, создадим новую хеш-таблицу размера &lt;tex&gt;2n&lt;/tex&gt;, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения &lt;tex&gt;[0..2n-1]&lt;/tex&gt;.<br /> <br /> Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования было произведено не менее &lt;tex dpi = &quot;150&quot;&gt;\frac{2n}{3}&lt;/tex&gt; операций &lt;tex&gt;\mathrm{add(x)}&lt;/tex&gt;, так как изначально в массиве находится &lt;tex dpi = &quot;150&quot;&gt;\frac{2n}{3}&lt;/tex&gt; элементов (или &lt;tex&gt;0&lt;/tex&gt; в начале работы), а перехеширование происходит при наличии &lt;tex dpi = &quot;150&quot;&gt;\frac{4n}{3}&lt;/tex&gt; элементов. <br /> <br /> Для проведения перехеширования необходимо произвести &lt;tex dpi = &quot;150&quot;&gt;\frac{4n}{3}&lt;/tex&gt; операций &lt;tex&gt;\mathrm{add}(x)&lt;/tex&gt;, средняя стоимость которых составляет &lt;tex&gt;O(1)&lt;/tex&gt; , потратить &lt;tex dpi = &quot;150&quot;&gt;\frac{4n}{3}&lt;/tex&gt; операций на проход хеш-таблицы, и &lt;tex dpi = &quot;150&quot;&gt;\frac{4n}{3}&lt;/tex&gt; операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции &lt;tex&gt;\mathrm{add}(x)&lt;/tex&gt; на &lt;tex&gt;6&lt;/tex&gt;, то есть на &lt;tex&gt;O(1)&lt;/tex&gt;, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна &lt;tex&gt;O(1)&lt;/tex&gt;.<br /> <br /> ===При хешировании с открытой адресацией===<br /> При использовании [[Разрешение коллизий|хеширования цепочками]] , операции &lt;tex&gt;\mathrm{add}(x)&lt;/tex&gt;, &lt;tex&gt;\mathrm{contains}(x)&lt;/tex&gt; и &lt;tex&gt;\mathrm{remove(x)}&lt;/tex&gt; в худшем случае работают за &lt;tex&gt;O(k)&lt;/tex&gt;, где &lt;tex&gt;k&lt;/tex&gt; {{---}} количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.<br /> <br /> Будем проводить перехеширование при заполнении таблицы на &lt;tex dpi = &quot;150&quot;&gt;\frac{n}{2}&lt;/tex&gt;, увеличивая размер таблицы в &lt;tex&gt;2&lt;/tex&gt; раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить &lt;tex&gt;O(n)&lt;/tex&gt; операций на обход таблицы, &lt;tex&gt;O(n)\cdot A&lt;/tex&gt; элементарных операций на добавление элементов, где &lt;tex&gt;A&lt;/tex&gt; {{---}} стоимость операции &lt;tex&gt;\mathrm{add(x)}&lt;/tex&gt;, и &lt;tex&gt;O(n)&lt;/tex&gt; операций на удаление таблицы. Так как &lt;tex&gt;A \geqslant 1&lt;/tex&gt;, и между последовательными перехешированиями производится &lt;tex&gt;O(n)&lt;/tex&gt; добавлений, то можно предоплатить перехеширование, увеличив стоимость операции &lt;tex&gt;\mathrm{add(x)}&lt;/tex&gt; на &lt;tex&gt;O(1)&lt;/tex&gt;, и не изменив стоимость остальных операций.<br /> <br /> ==См. также==<br /> * [[Амортизационный анализ]]<br /> * [[Хеширование]]<br /> * [[Открытое и закрытое хеширование]]<br /> <br /> ==Источники информации==<br /> * ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом &quot;Вильямс&quot;, 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)<br /> * Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0<br /> &lt;references/&gt;<br /> <br /> <br /> [[Категория: Дискретная математика и алгоритмы ]]<br /> [[Категория: Амортизационный анализ]]<br /> [[Категория: Хеширование]]</div>

92.113.116.181