Перечисленные выше операции с таблицей предполагают, что для
однозначного доступа к ее элементам последние должны содержать один или
более признаков, отличающих их от других элементов этой таблицы. С этой
целью в логическую структуру элемента включается по крайней мере одно
поле — ключ, содержимое которого уникально для любого из элементов,
входящих в таблицу. В общем случае работа с таблицами сводится к методам
решения задачи поиска нужного элемента таблицы по заданному значению
ключа. Результат решения — получение адреса искомого элемента или
заключение о его отсутствии. Для локализации элемента таблицы необходимо
знать два адресных компонента — адрес таблицы и смещение нужного
элемента относительно начала таблицы. Адрес таблицы получить несложно,
так как он является адресом ее первого элемента. Что же касается
определения второй компоненты адреса, то для этого существует ряд
методов, рассмотрению которых и будет посвящено дальнейшее изложение.
В ряде случаев наряду с ключевым полем определяют еще одно служебное
поле — поле текущего состояния элемента, которое может принимать три
значения:
- элемент свободен — после инициализации таблицы элемент ни разу не использовался для хранения полезной информации;
- элемент используется для хранения полезной информации;
- элемент удален — после инициализации таблицы элемент хотя бы один раз использовался для хранения полезной информации, после чего был освобожден.
Целесообразность использования поля текущего состояния элемента будет видна из дальнейших рассуждений.
С точки зрения организации поиска таблицы делятся на:
- неупорядоченные;
- древовидные;
- упорядоченные;
- с вычисляемыми входами (хэш-таблицы).