9.4.2. Способы реализации ассоциативной памяти

Для представления ассоциативной памяти используются следующие основные структуры данных:

1. неупорядоченный массив;

2. упорядоченный массив;

3. дерево сортировки — бинарное дерево, каждый узел которого содержит ключ и обладает следующим свойством: значения ключа во всех узлах левого под­дерева меньше, а во всех узлах правого поддерева больше, чем значение ключа в узле;

4. таблица расстановки (или хэш-таблица).

При использовании неупорядоченного массива алгоритмы реализации операций ассоциативной памяти очевидны:

1. операция «добавить (ключ, запись)» реализуется добавлением записи в конец массива;

2. операция «найти (ключ): запись» реализуется проверкой в цикле всех записей в массиве;

3. операция «удалить (ключ)» реализуется поиском удаляемой записи, а затем перемещением всех последующих записей на одну позицию вперед.

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

Основное внимание в этом разделе уделено алгоритмам выполнения операций с деревом сортировки.

ОТСТУПЛЕНИЕ

Таблицы расстановки являются чрезвычайно важным практическим приемом программи­рования, подробное описание которого выходит за рамки этого учебника. Вкратце основ­ная идея заключается в следующем. Подбирается специальная функция, которая называ­ется хэш-функцией, переводящая значение ключа в адрес хранения записи (адресом может быть индекс в массиве, номер кластера на диске и т. д.). Таким образом, имея ключ, с по­мощью хэш-функции сразу определяется место хранения записи и открывается доступ к ней. Хэш-функция подбирается таким образом, чтобы разным ключам соответствовали, по возможности, разные адреса из диапазона возможных адресов записей. Как правило, мощ­ность множества ключей существенно больше размера пространства адресов, которое, в свою очередь, больше количества одновременно хранимых записей. Поэтому при исполь­зовании хэширования возможны коллизии — ситуации, когда хэш-функция сопоставляет один и тот же адрес двум актуальным записям с различными ключами. Различные мето­ды хэширования отличаются друг от друга способами разрешения коллизий и приемами вычисления хэш-функций.