121 lines
6.9 KiB
HTML
121 lines
6.9 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>Страница 5</title>
|
||
|
|
</head>
|
||
|
|
<body>
|
||
|
|
<p style="text-align: center">
|
||
|
|
<i><b>Страница 5</b></i>
|
||
|
|
</p>
|
||
|
|
<hr />
|
||
|
|
<h1 style="text-align: center">Хеш-таблица</h1>
|
||
|
|
<h2 style="text-align: center">Свойства хеш-таблицы</h2>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Хеш-таблицы являются одним из способов хранения данных при помощи
|
||
|
|
ассоциативного массива [<a
|
||
|
|
href="https://ru.wikipedia.org/wiki/Ассоциативный_массив"
|
||
|
|
target="_blank"
|
||
|
|
>12</a
|
||
|
|
>].
|
||
|
|
</p>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Хеш-таблицы решают несколько главных проблем при оперировании с данными:
|
||
|
|
</p>
|
||
|
|
<ul>
|
||
|
|
<li style="text-align: justify">
|
||
|
|
<i
|
||
|
|
>Создание отношения (связи) между ключом и абсолютно любым
|
||
|
|
значением.</i
|
||
|
|
>
|
||
|
|
</li>
|
||
|
|
<li style="text-align: justify"><i>Решение проблем коллизий.</i></li>
|
||
|
|
</ul>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Для большего понимания материала требуется ознакомиться с новыми терминами
|
||
|
|
хеш-таблицы:
|
||
|
|
</p>
|
||
|
|
<dl>
|
||
|
|
<dt><i>Ключ или сообщение</i></dt>
|
||
|
|
<dd>использующийся хеш-таблицей произвольный элемент из области определения хеш-функции.</dd>
|
||
|
|
<dt><i>Бункер или корзина</i></dt>
|
||
|
|
<dd>произвольный элемент, который хранит данные хеш-таблицы.</dd>
|
||
|
|
<dt><i>Коэффициент заполнения</i></dt>
|
||
|
|
<dd>
|
||
|
|
отношение количества заполненных бункеров на количество возможных ключей.
|
||
|
|
</dd>
|
||
|
|
</dl>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Исходя из определений, бункер - это условная единица хранимой информации в
|
||
|
|
хеш-таблице (ассоциативном массиве данных).
|
||
|
|
</p>
|
||
|
|
<p>
|
||
|
|
<i
|
||
|
|
><span style="text-align: justify"
|
||
|
|
>Решение первой проблемы. </span
|
||
|
|
></i
|
||
|
|
>Хеш-функции в хеш-таблице, нужны по причине получения хеша в процессе
|
||
|
|
хеширования ключа, однако хеш - значение абстрактное, так как невозможно
|
||
|
|
создать такой алгоритм, который бы выдавал хеш, как набор данных,
|
||
|
|
используемый в процессе работы программы или это очень сложно.<br />
|
||
|
|
Для большего понимания нужно вспомнить пример о <span
|
||
|
|
style="text-align: justify"
|
||
|
|
>"продавце в маленьком магазинчике", где "помощница"
|
||
|
|
абстрагирует понятие хеш-функции, которая выдавала для каждого товара
|
||
|
|
конкретную цену, что возможно, но трудозатратно.</span
|
||
|
|
><br />
|
||
|
|
<span style="text-align: justify"
|
||
|
|
>Для этого требуется хеш-функция, где хеш является универсальным
|
||
|
|
идентификатором конкретного бункера, в котором располагается необходимый
|
||
|
|
пользователю набор данных.</span
|
||
|
|
>
|
||
|
|
</p>
|
||
|
|
<p>
|
||
|
|
Томас Кормен говорит в книге [2, c.288], что цель хеш-функции состоит в
|
||
|
|
том, чтобы уменьшить рабочий диапазон индексов массива - размер массива
|
||
|
|
может быть равен соотносительно намного меньшему значению, чем мощность
|
||
|
|
множества всех существующих значений ключей, которые могут потенциально
|
||
|
|
использоваться в процессе работы программы.
|
||
|
|
</p>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
<span style="text-align: justify"
|
||
|
|
>Из этого можно выделить несколько особенностей хеш-таблиц:</span
|
||
|
|
>
|
||
|
|
</p>
|
||
|
|
<ul>
|
||
|
|
<li style="text-align: justify">
|
||
|
|
Каждый бункер имеет в качестве уникального идентификатора
|
||
|
|
хеш-значение
|
||
|
|
</li>
|
||
|
|
<li style="text-align: justify">
|
||
|
|
Каждый ключ гарантированно имеет связь только с одним бункером.
|
||
|
|
</li>
|
||
|
|
<li style="text-align: justify">
|
||
|
|
Количество бункеров относительно количества ключей сильно ограниченно.
|
||
|
|
</li>
|
||
|
|
<li style="text-align: justify">
|
||
|
|
От хеш-функции зависит коэффициент заполнения.
|
||
|
|
</li>
|
||
|
|
<li style="text-align: justify">
|
||
|
|
По принципу Дирихле коллизия неизбежна в ситуации, когда количество ключей больше, чем количество бункеров.
|
||
|
|
</li>
|
||
|
|
</ul>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
<i>Решение второй проблемы</i>. Хеш-таблицы используют в качестве
|
||
|
|
алгоритма поиска элемента контейнера (бункера) хеш-функцию, которая по
|
||
|
|
принципу Дирихле гарантированно создаст коллизии в ситуации, когда
|
||
|
|
количество ключей больше, чем количество бункеров, а обычно так бывает
|
||
|
|
всегда.
|
||
|
|
</p>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Хеш-таблицы решают данную проблему двумя способами:
|
||
|
|
</p>
|
||
|
|
<ul>
|
||
|
|
<li style="text-align: justify">Метод цепочек или прямым связыванием.</li>
|
||
|
|
<li style="text-align: justify">Открытой адресацией.</li>
|
||
|
|
</ul>
|
||
|
|
</body>
|
||
|
|
</html>
|