9.4.1. Ассоциативная память

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

Пример

Ассоциативная память используется во многих областях жизни.

1. Толковый словарь или энциклопедия: записью является словарная статья, а ключом — заголовок словарной статьи (обычно его выделяют жирным шриф­том).

2. Адресная книга: ключом является имя абонента, а записью — адресная инфор­мация (телефон(ы), почтовый адрес и т. д.).

3. Банковские счета: ключом является номер счета, а записью — финансовая информация (которая может быть очень сложной).

Таким образом, ассоциативная память должна поддерживать по меньшей мере три основные операции:

- добавить (ключ, запись);

- найти (ключ): запись;

- удалить (ключ).

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

ЗАМЕЧАНИЕ

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