user
275 lines
22 KiB
HTML
275 lines
22 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="en">
|
||
<head>
|
||
<meta charset="UTF-8" />
|
||
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
|
||
<title>Страница 7</title>
|
||
</head>
|
||
<body>
|
||
<p style="text-align: center">
|
||
<i><b>Страница 7</b></i>
|
||
</p>
|
||
<hr />
|
||
<h1 style="text-align: center">Решение проблем коллизий</h1>
|
||
<h2 style="text-align: center">
|
||
Открытая и прямая адресации [5, c. 170-179]
|
||
</h2>
|
||
<p>Оглавление:</p>
|
||
<ul>
|
||
<li><a href="#description">Описание.</a></li>
|
||
<li><a href="#linear">Линейное пробирование.</a></li>
|
||
<li><a href="#quadratic">Квадратичное пробирование.</a></li>
|
||
<li><a href="#pseudorandom">Псевдослучайное пробирование.</a></li>
|
||
<li><a href="#double">Двойное хеширование.</a></li>
|
||
</ul>
|
||
<div>
|
||
<h3 style="text-align: center"><a name="description">Описание</a></h3>
|
||
<p style="text-align: justify">
|
||
Безусловно, прямое связывание имеет свои преимущества. Основное из них
|
||
заключается в том, что общее количество значений не зависит от
|
||
количества блоков. Однако есть у таких хеш-таблиц и некоторые
|
||
недостатки. Например, если элементов в блоках накопится слишком много,
|
||
поиск нужного займет продолжительное время. Чтобы сократить временные
|
||
затраты, число блоков можно увеличить, но тогда вы рискуете получить ряд
|
||
пустых, которые потребуют места в памяти и не будут использоваться
|
||
таблицей.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Еще один способ реализации хеш-таблиц — <i>открытая адресация</i>.
|
||
В этом случае значения хранятся в массиве, а функция хеширования
|
||
представляет собой некоторые расчеты.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Хеш-таблица с <i>прямой адресацией</i> отличается от хеш-таблицы с
|
||
открытой адресацией тем, что в первом случае гарантировано должна
|
||
использоваться идеальная хеш-функция. Это обусловлено тем, что в данной
|
||
хеш-таблице должны отсутствовать коллизии, соответственно, как и методы
|
||
их разрешения. Стоит отметить, что под данное описание подходит
|
||
<i>идеальное хеширование</i> хеш-таблицы<sup>1</sup>.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
В разных видах открытой адресации используются различные функции
|
||
хеширования. Неодинакова и политика разрешения коллизий, но в общем
|
||
случае она выглядит так: для каждого значения в массиве подбирается
|
||
несколько ячеек, и если первая уже занята, алгоритм пробует использовать
|
||
вторую, затем третью и так до тех пор, пока не найдет свободную или не
|
||
придет к выводу, что таковой нет.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Серия ячеек, которую алгоритм подбирает для значения, называется пробной
|
||
последовательностью. По ее средней длине хорошо оценивать наполненность
|
||
хештаблицы. В идеале пробная последовательность должна равняться 1 или
|
||
2, большие цифры говорят о полной таблице.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Иногда политика разрешения коллизий такова, что для элемента может не
|
||
найтись свободной ячейки, даже когда она есть. Если пробная
|
||
последовательность повторяет саму себя перед тем, как проверить
|
||
очередную запись, некоторые записи могут остаться неиспользованными.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Чтобы найти элемент в хеш-таблице, алгоритм следует за пробной
|
||
последовательностью, пока не произойдет одно из трех событий.
|
||
</p>
|
||
<ol>
|
||
<li style="text-align: justify">
|
||
Если пробная последовательность сумела отыскать элемент, задача
|
||
выполнена.
|
||
</li>
|
||
<li style="text-align: justify">
|
||
Если пробная последовательность находит пустую запись в массиве,
|
||
элемента нет.
|
||
</li>
|
||
<li style="text-align: justify">
|
||
Пробная последовательность проверяет <i>M</i> записей (по размеру
|
||
массива) — и алгоритм приходит к выводу, что значение
|
||
отсутствует. Последовательность может перебрать не все элементы, но
|
||
если пройдет по всем, вы будете знать, что они точно пересмотрены или
|
||
что целевой элемент не найден. Она также может проверить в цикле одну
|
||
и ту же позицию несколько раз. В любом случае значение не должно
|
||
присутствовать, поскольку иначе оно бы добавлялось к массиву с
|
||
использованием той же пробной последовательности.
|
||
</li>
|
||
</ol>
|
||
<p style="text-align: justify">
|
||
При разумном заполнении хеш-таблицы открытая адресация работает очень
|
||
быстро. Если длина пробной последовательности равна 1 или 2, добавление
|
||
и нахождение элементов выполняются за время <i>O(1)</i>. Но если массив
|
||
из N элементов существенно переполнен, производительность снижается. В
|
||
наихудшем случае алгоритм придет к выводу, что элемента в массиве нет,
|
||
за время <i>O(N)</i>. Поиск присутствующих элементов также будет
|
||
выполняться крайне медленно.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Вы можете увеличить размер массива, чтобы уменьшить коэффициент
|
||
наполненности хеш-таблицы. Для этого создайте новый массив и рехешируйте
|
||
элементы в нем. Для каждого из них операция займет <i>O(1)</i> времени,
|
||
а общая производительность алгоритма составит <i>O(N)</i>.
|
||
</p>
|
||
</div>
|
||
<div>
|
||
<h3 style="text-align: center">
|
||
<a name="linear">Линейное пробирование</a>
|
||
</h3>
|
||
<p style="text-align: justify">
|
||
В линейном пробировании политика разрешения коллизий добавляет к каждой
|
||
ячейке постоянное число (чаще всего 1), называемое шагом по индексу,
|
||
которое генерирует пробную последовательность. При каждом очередном
|
||
добавлении берется размер массива по модулю, стало быть, при
|
||
необходимости последовательность возвращается к началу массива.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Предположим, в хеш-таблице 100 элементов, а правило хеширования звучит
|
||
следующим образом: N связано с ячейкой N mod 100. Тогда пробная
|
||
последовательность для значения 2197 проверяет ячейки 97, 98, 99, 0, 1,
|
||
2 и т. д.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
На рисунке 7.1 представлен массив из 10 записей, который уже содержит
|
||
несколько значений. Чтобы добавить в него новое значение 71, используя
|
||
линейную пробную последовательность, нужно связать его с ячейкой 71 mod
|
||
10 = 1. Но эта ячейка уже занята значением 61, поэтому алгоритм
|
||
переходит к ячейке 2, которая тоже заполнена. Следующей должна быть
|
||
ячейка 3 — она свободна, и алгоритм размещает там 71.
|
||
</p>
|
||
<div style="text-align: center">
|
||
<img src="7.1.png" width="800" />
|
||
<p style="text-align: center">
|
||
Рисунок 7.1 - линейная пробная последовательность
|
||
</p>
|
||
</div>
|
||
<p style="text-align: justify">
|
||
Преимущество данного метода — в его простоте. Если необходимо,
|
||
пробная последовательность пройдет по каждой ячейке массива и вставит
|
||
элемент в свободное место, если оно еще осталось. Но есть и
|
||
сопутствующий недостаток — так называемая
|
||
<i>первичная кластеризация</i>, которая проявляется в образовании
|
||
больших блоков смежных записей и приводит к длинным пробным
|
||
последовательностям. В результате при добавлении нового элемента и его
|
||
хешировании к какой-либо записи в кластере пробная последовательность
|
||
вынуждена пройти через весь кластер, чтобы найти свободную ячейку.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Чтобы понять, как формируются кластеры, рассмотрим пример пустой
|
||
хеш-таблицы. Предположим, в ней содержится <i>N</i> записей и существует
|
||
вероятность <i>1/N</i>, что она закончится в любой данной позиции при
|
||
добавлении случайного числа. А теперь представим, что <i>K</i> —
|
||
конечная позиция таблицы. Существует вероятность <i>1/N</i>, что новое
|
||
случайное число попадет в позицию K и линейное пробирование попытается
|
||
расположить элемент в позиции <i>K + 1</i>. Но та же вероятность
|
||
характерна и для случая, при котором новый элемент будет связан с
|
||
позицией <i>K + 1</i> напрямую. Значит, существует вероятность
|
||
<i>2/N</i>, что элемент займет конечную позицию <i>K + 1</i> и
|
||
сформируется малый кластер.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Через какое-то время таких кластеров станет много. Чем больше они будут,
|
||
тем больше вероятность того, что новый элемент добавится в конец одного
|
||
из них. В итоге более мелкие кластеры сольются в более крупные, массив
|
||
заполнится ими — и возникнут длинные пробные последовательности.
|
||
</p>
|
||
</div>
|
||
<div>
|
||
<h3 style="text-align: center">
|
||
<a name="quadratic">Квадратичное пробирование</a>
|
||
</h3>
|
||
<p style="text-align: justify">
|
||
Возникновение больших кластеров при линейном пробировании связано с тем,
|
||
что новые элементы связываются с ячейками, стоящими в конце группы, и
|
||
постепенно увеличивают ее. Предотвратить подобную ситуацию помогает
|
||
<i>квадратичное пробирование</i>. Для создания пробной
|
||
последовательности в качестве шага по индексу берется квадрат количества
|
||
ячеек. Другими словами, если в линейном пробировании существует
|
||
последовательность <i>K, K + 1, K + 2, K + 3,</i> ... то в квадратичном
|
||
варианте она будет выглядеть так:
|
||
<i>K, K + 12, K + 22, K + 32, ...</i> В этом случае, если два
|
||
элемента окажутся связанными с разными позициями в одном и том же
|
||
кластере, они не обязательно будут придерживаться одной пробной
|
||
последовательности и попадут в конец кластера.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
На рисунке 7.2 показана хеш-таблица, в начале которой есть группа из
|
||
пяти элементов. Новое значение 71 получает пробную последовательность
|
||
<i>1, 1 + 12 = 2, 1 + 22 = 5, 1 + 32 = 10</i> и не добавляется к
|
||
существующему кластеру. Значение <i>93 </i>поначалу связано с тем же
|
||
кластером, но согласно собственной пробной последовательности
|
||
<i>3, 3 + 12 = 4, 3 + 22 = 7</i> также не попадает в него.
|
||
</p>
|
||
<div style="text-align: center">
|
||
<img src="7.2.png" width="800" />
|
||
<p style="text-align: center">Рисунок 7.2 - Квадратичное пробирование</p>
|
||
</div>
|
||
<p style="text-align: justify">
|
||
Квадратичное пробирование предотвращает первичную, но не
|
||
<i>вторичную кластеризацию</i>, при которой значения, связанные с
|
||
одинаковой начальной позицией в массиве, получают одну и ту же пробную
|
||
последовательность, иногда очень длинную. В результате образуется точно
|
||
такая же группа элементов, но уже не собранных вместе, а распределенных
|
||
по всему массиву.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Еще один недостаток квадратичного пробирования связан с тем, что оно
|
||
может не найти свободную позицию, даже если в хеш-таблице их несколько.
|
||
Дело в том, что с каждым разом перемещение по массиву происходит все
|
||
дальше и дальше, и незаполненная ячейка попросту пропускается.
|
||
</p>
|
||
</div>
|
||
<div>
|
||
<h3 style="text-align: center">
|
||
<a name="pseudorandom">Псевдослучайное пробирование</a>
|
||
</h3>
|
||
<p style="text-align: justify">
|
||
Это пробирование подобно линейному, за исключением того, что шаг по
|
||
индексу формирует псевдослучайная функция изначально связанной ячейки.
|
||
Предположим, что это ячейка <i>K</i>, тогда пробная последовательность
|
||
будет выглядеть следующим образом: <i>K, K + p, K + 2p, ...</i> где p
|
||
определяется псевдослучайной функцией.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Подобно квадратичному пробированию, псевдослучайное предотвращает только
|
||
первичную кластеризацию, но страдает от вторичной: значения, связанные с
|
||
одной и той же начальной позицией, размещаются в хеш-таблице согласно
|
||
одной и той же пробной последовательности. Точно так же псевдослучайное
|
||
пробирование может пропускать некоторые неиспользуемые записи.
|
||
</p>
|
||
</div>
|
||
<div>
|
||
<h3 style="text-align: center">
|
||
<a name="double">Двойное хеширование</a>
|
||
</h3>
|
||
<p style="text-align: justify">
|
||
Чтобы избавиться от вторичной кластеризации значения, связанные с одной
|
||
и той же начальной ячейкой, должны получать разные пробные
|
||
последовательности. И здесь пригодится двойное хеширование. Оно похоже
|
||
на псевдослучайное пробирование, только шаг для индекса задается не
|
||
псевдослучайной функцией начальной ячейки, а второй функцией
|
||
хеширования.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Допустим, значения <i>A</i> и <i>B</i> связаны с позицией <i>K</i>. В
|
||
псевдослучайном пробировании шаг по индексу <i>p</i> генерируется
|
||
функцией <i>F<sub>1</sub> (K)</i>, затем оба значения используют пробную
|
||
последовательность <i>K, K + p, K + 2p, K + 3p, ...</i> В двойном
|
||
хешировании для связывания начальных значений <i>А</i> и
|
||
<i>В</i> применяется функция псевдослучайного хеширования
|
||
<i>F<sub>2</sub></i
|
||
>. В итоге при одном и том же начальном <i>K</i> образуются две пробные
|
||
последовательности с различными шагами по индексу:
|
||
<i>p<sub>A</sub> = F<sub>2</sub> (A)</i> и
|
||
<i>p<sub>B</sub> = F<sub>2</sub> (B)</i> соответственно.
|
||
</p>
|
||
<p style="text-align: justify">
|
||
Несмотря на то, что двойное хеширование хорошо справляется с первичной и
|
||
вторичной кластеризациями, оно точно так же, как и псевдослучайное
|
||
пробирование, может пропускать неиспользуемые записи.
|
||
</p>
|
||
</div>
|
||
<hr />
|
||
<p>
|
||
<sup>1</sup>Данный метод хеширования хорошо описан в книге Томаса Кормена
|
||
[2]
|
||
</p>
|
||
</body>
|
||
</html>
|