При заполнении таблицы могут возникать коллизии, для борьбы с которыми разработаны специальные методы, которые в основном сводятся к методам "цепочек" и "открытой адресации". Ключи, выдающие одинаковые адреса в таблице, называются ключи-синонимы.

В методе цепочек для разрешения коллизий во все записи вводятся указатели, используемые для организации списков – "цепочек переполнения". В случае возникновения коллизии при заполнении таблицы в список для требуемого адреса хеш-таблицы добавляется еще один элемент.

Хранит все элементы с данным хэшом данной таблицы. Если есть коллизия то мы добавим новый лемент в конец спска. И при поиске найдя хэш пробегаем по содержимаму.

Поиск в хеш-таблице с цепочками переполнения осуществляется следующим образом. Сначала вычисляется адрес по значению ключа. Затем осуществляется последовательный поиск в списке, связанном с вычисленным адресом. Процедура удаления из таблицы сводится к поиску элемента и его удалению из цепочки переполнения.

Метод открытой адресации состоит в том, чтобы, пользуясь каким-либо алгоритмом, обеспечивающим перебор элементов таблицы, просматривать их в поисках свободного места для новой записи.

Различают:

а) Линейное пробирование

б) Квадратичное пробирование

в) Двойное хеширование

Линейное пробирование сводится к последовательному перебору элементов таблицы с некоторым фиксированным шагом

Квадратичное пробирования отличается от линейного тем, что шаг перебора элементов нелинейно зависит от номера попытки найти свободный элемент

Интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит может быть различным для разных ключей.

Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв простое число в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до N — 1.

2.4. Алгоритмы работы с хеш-таблицами методами открытой адресации

Если ячейка уже занята, то мы помещаем содержимое хэш в следующую свободную но с другим ключём. Таким образом поиск осуществляется не толко по содержимому но и по ключу.дойдя до пустой ячейки мы паймём что нужного элемента нет.

Аналогичным образом можно было бы сформулировать алгоритмы добавления и поиска

Процедура удаления в данном случае не будет являться обратной процедуре вставки. Элементы таблицы находятся в двух состояниях: свободно и занято.

Если удалить элемент, переведя его в состояние свободно, то после такого удаления алгоритм поиска будет работать некорректно.

При использовании хеш-таблиц необходимо стараться избегать очень плотного ее заполнения. Обычно длину таблицы выбирают из расчета двукратного превышения предполагаемого максимального числа записей. В случае большой заполненности таблицы может понадобиться рехеширование. В этом случае увеличивают длину таблицы, изменяют хеш-функцию и переупорядочивают данные.

СТРУКТУРЫ ДАННЫХ

Полустатические и динамические структуры данных

Понятие динамических структур данных. Возможности, предоставляемые использованием динамических структур данных.

Полустатические структуры данных характеризуются следующими признаками:

- они имеют переменную длину и простые процедуры ее изменения;

- изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.

Если полустатическую структуру рассматривать на логическом уровне, то о ней можно сказать, что это последовательность данных, связанная отношениями линейного списка.

Физическое представление полустатических структур данных в памяти – это обычно последовательность слотов в памяти, где каждый следующий элемент расположен в следующем слоте. Физическое представление может иметь вид однонаправленного списка, где каждый следующий элемент адресуется указателем, находящимся в текущем элементе.

В противовес статическим величинам, память под которые выделяется во время компиляции и сохраняется в течение всей работы программы, существуют динамические величины. Под них память выделяется динамически во время выполнения программы.