57 lines
3.9 KiB
HTML
57 lines
3.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>Страница 6</title>
|
||
|
|
</head>
|
||
|
|
<body>
|
||
|
|
<p style="text-align: center">
|
||
|
|
<i><b>Страница 6</b></i>
|
||
|
|
</p>
|
||
|
|
<hr />
|
||
|
|
<h1 style="text-align: center">Решение проблем коллизий</h1>
|
||
|
|
<h2 style="text-align: center">Метод цепочек или прямое связывание [5, c. 170-171]</h2>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
В хеш таблице с прямым связыванием (рис 6.1) значения ключей (бункеры)
|
||
|
|
хранятся в специальных наборах записей, называемых <i>блоками.</i> Каждый
|
||
|
|
из них является вершиной связного списка, в котором находятся привязанные
|
||
|
|
к блоку элементы.
|
||
|
|
</p>
|
||
|
|
<div style="text-align: center">
|
||
|
|
<img src="6.1.png" height="350" />
|
||
|
|
<p style="text-align: center">Рисунок 6.1 - хеш-таблица с прямым связыванием</p>
|
||
|
|
</div>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Поиск элементов в хеш-таблице пройдёт быстрее, если связанные списки будут
|
||
|
|
содержать ключи в отсортированном порядке. В этом случае алгоритм сделает
|
||
|
|
вывод, что ключа нет, если дойдёт до значения больше ключевого и не станет
|
||
|
|
просматривать список до конца. Теоретически время его работы составит
|
||
|
|
<i>O(N/B)</i>, но на практике оно будет немного меньше.
|
||
|
|
</p>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Чтобы найти нужный элемент, программе необходимо хешировать ключ и
|
||
|
|
определить, в каком из блоков он может содержаться, а затем двигаться по
|
||
|
|
связному списку до тех пор, пока не будет достигнут его конец или не
|
||
|
|
обнаружится искомое. Если вы доберётесь до конца списка, значит,
|
||
|
|
запрашиваемого элемента в хеш-таблице нет. Как и в случае с добавлением
|
||
|
|
элемента, предстоит выполнить <i>O(N/B)</i> шагов.
|
||
|
|
</p>
|
||
|
|
<p style="text-align: justify">
|
||
|
|
Хеш-таблица с прямым связыванием может расширяться и сжиматься<sup>1</sup>
|
||
|
|
по мере необходимости, поэтому вам не нужно специально изменять её размер.
|
||
|
|
Однако если связные списки станут слишком длинными, поиск и удаление
|
||
|
|
элементов займут много времени. В этом случае вам понадобится увеличить
|
||
|
|
таблицу, чтобы создать больше блоков. Поскольку при рехешировании таблицы
|
||
|
|
не надо проводить поиск дубликатов до конца связного списка в каждом
|
||
|
|
блоке, полностью справиться с операцией можно за время <i>O(N)</i>.
|
||
|
|
</p>
|
||
|
|
<hr />
|
||
|
|
<p>
|
||
|
|
<sup>1</sup>Удаление элементов в данном методическом материале
|
||
|
|
рассматриваться не будет
|
||
|
|
</p>
|
||
|
|
</body>
|
||
|
|
</html>
|