TheoryHTML/Pages/openAddressing.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">
        Еще один способ реализации хеш-таблиц &mdash; <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> записей (по размеру
          массива) &mdash; и алгоритм приходит к выводу, что значение
          отсутствует. Последовательность может перебрать не все элементы, но
          если пройдет по всем, вы будете знать, что они точно пересмотрены или
          что целевой элемент не найден. Она также может проверить в цикле одну
          и ту же позицию несколько раз. В любом случае значение не должно
          присутствовать, поскольку иначе оно бы добавлялось к массиву с
          использованием той же пробной последовательности.
        </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 &mdash; она свободна, и алгоритм размещает там 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">
        Преимущество данного метода &mdash; в его простоте. Если необходимо,
        пробная последовательность пройдет по каждой ячейке массива и вставит
        элемент в свободное место, если оно еще осталось. Но есть и
        сопутствующий недостаток &mdash; так называемая
        <i>первичная кластеризация</i>, которая проявляется в образовании
        больших блоков смежных записей и приводит к длинным пробным
        последовательностям. В результате при добавлении нового элемента и его
        хешировании к какой-либо записи в кластере пробная последовательность
        вынуждена пройти через весь кластер, чтобы найти свободную ячейку.
      </p>
      <p style="text-align: justify">
        Чтобы понять, как формируются кластеры, рассмотрим пример пустой
        хеш-таблицы. Предположим, в ней содержится <i>N</i> записей и существует
        вероятность <i>1/N</i>, что она закончится в любой данной позиции при
        добавлении случайного числа. А теперь представим, что <i>K</i> &mdash;
        конечная позиция таблицы. Существует вероятность <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">
        Через какое-то время таких кластеров станет много. Чем больше они будут,
        тем больше вероятность того, что новый элемент добавится в конец одного
        из них. В итоге более мелкие кластеры сольются в более крупные, массив
        заполнится ими &mdash; и возникнут длинные пробные последовательности.
      </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> В этом случае,&nbsp;если два
        элемента окажутся связанными с разными позициями в одном и том же
        кластере, они не обязательно будут придерживаться одной пробной
        последовательности и попадут в конец кластера.
      </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>