替換策略（replacement policy）

你的小桌滿了，一本新書非放上來不可——所以桌上某本書得還回書架。你會放棄哪一本？你大概會還那本最久沒翻開的，賭你近期不會再需要它。替換策略正是這條規則：當快取的某組滿了、而未命中時必須帶進一條新列，策略就決定要淘汰哪一條既有列來騰位。

在組相聯快取裡，缺少的區塊可佔用它那組 n 個路中的任一個；若 n 個都已滿，就得選一個淘汰。黃金標準的啟發式是 LRU（最近最少使用）：淘汰最久沒被存取的那一條列，直接押注時間區域性（最近用過很可能再被用到，所以最久沒用的最安全可丟）。真正的 LRU 在路數多時追蹤成本很高，所以真實硬體用近似：偽 LRU（一小棵位元樹，粗略排序各路）、近期未用、甚至隨機替換——後者出人意料地具競爭力、幾乎不需硬體，又避免病態的最壞情況。直接映射快取根本不需策略——只有一個可能的家，選擇被強制決定。

替換之所以重要，是因為錯誤的淘汰把你即將需要的列丟掉，使本可命中的變成未命中。但誠實地說，它是二階槓桿：好策略與平庸策略之間的差距，通常遠小於你程式碼中好區域性與壞區域性之間、或快取容量太小與足夠之間的差距。還有一個令人謙卑的理論事實——可證明最佳的策略（Belady 的：淘汰下次使用最遙遠的那條列）需要知道未來，所以無法實作；它只能當作無法企及的基準，用來衡量真實策略。