Fonte William Stallings, pág 134
Quando um novo bloco é trazido para a memória cache, um dos blocos existentes deve ser substituído. No mapeamento direto, cada bloco é mapeado em uma única linha, o que determina o bloco a ser substituído, não havendo alternativa possível. O mapeamento associativo e o mapeamento associativo por conjunto requerem o uso de um algoritmo de substituição. Para que a velocidade de acesso à memória seja alta, esse algoritmo deve ser implementado em hardware. O algoritmo mais eficaz é, provavelmente, o baseado na política de substituir o bloco menos recentemente usado (least recently uses – LRU): o bloco a ser substituído é o que está no conjunto que não é usado há mais tempo.