Для кэш со случайным отображением используется так называемый

полный ассоциативный поиск, при котором сравнение выполняется не

последовательно с каждой записью кэш, а параллельно со всеми его записями (рис.1.11). Признак, по которому выполняется сравнение, называется тегом (tag). В данном случае тегом является адрес данных в оперативной памяти. Электронная реализация такой схемы приводит к удорожанию памяти, причем стоимость существенно возрастает с увеличением объема запоминающего устройства. Поэтому полностью ассоциативная кэш-память используется в тех случаях, когда для обеспечения высокого процента попадания достаточно небольшого объема памяти.

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

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

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