В практическом программировании для организации хранения данных и доступа к ним часто используется механизм, который обычно называют ассоциативной памятью. При использовании ассоциативной памяти данные делятся на порции (называемые записями), и с каждой записью ассоциируется ключ. Ключ — это значение из некоторого вполне упорядоченного множества (т.е. для любых двух ключей однозначно можно определить одно из отношений: «больше», «меньше» или «равно»). Записи могут иметь произвольную природу и различные размеры. Доступ к данным осуществляется по значению ключа, который обычно выбирается простым, компактным и удобным для работы.
Примеры использования ассоциативной памяти:
1. Толковый словарь или энциклопедия: записью является словарная статья, а ключом — заголовок словарной статьи (обычно его выделяют жирным шрифтом).
2. Адресная книга: ключом является имя абонента, а записью — адресная информация (телефон, почтовый адрес и т. д.).
3. Банковские счета: ключом является номер счета, а записью — финансовая информация (которая может быть очень сложной).
Таким образом, ассоциативная память должна поддерживать, по меньшей мере, три основные операции:
1. добавить (ключ, запись);
2. найти (ключ): запись;
3. удалить (ключ).
Эффективность каждой операции зависит от структуры данных, используемой для представления ассоциативной памяти. Для представления ассоциативной памяти используются следующие основные структуры данных:
1. неупорядоченный массив;
2. упорядоченный массив;
3. дерево сортировки — бинарное дерево, каждый узел которого содержит ключ и обладает следующим свойством: значения ключа во всех узлах левого поддерева меньше, а во всех узлах правого поддерева больше, чем значение ключа.
Бинарное дерево можно сделать деревом сортировки, если произвести обход бинарного дерева по внутреннему порядку.
При использовании неупорядоченного массива алгоритмы реализации операций ассоциативной памяти очевидны:
1. операция «добавить (ключ, запись)» реализуется добавлением записи в конец массива;
2. операция «найти (ключ): запись» реализуется проверкой в цикле всех записей в массиве;
3. операция «удалить (ключ)?» реализуется поиском удаляемой записи, а затем перемещением всех последующих записей на одну позицию вперед.