LRU 原理作為操作系統課程中的一個重要部分在很多地方會被考到（比如操作系統課的考試或者一些公司的面試題）。

LRU 算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。

這個算法的出發點在于：如果某個頁面被訪問了，則它可能馬上還要訪問。反之，如果很長時間未被訪問，則它在最近一段時間也不會被訪問。

該算法的性能接近于最佳算法，但實現起來較困難。因為要找出最近最久未使用的頁面，必須為每一頁設置相關記錄項，用于記錄頁面的訪問情況，并且每訪問一次頁面都須更新該信息。這將使系統的開銷加大，所以在實際系統中往往使用該算法的近似算法。

對于考試題目而言，由于一般是卷面考試，所以我們通常需要完成的是在紙上描繪出 LRU 的置換原理，一般題目如下：

最近最久未使用算法例

假定系統為某進程分配了 3 個物理塊，進程運行時的頁面走向為 1，2，3，4，1，2，5，1，2，3，4，5，開始時 3 個物理塊均為空，計算采用 最近最久未使用頁面淘汰算法時的缺頁率 ？（10/12）

對于面試而言，可能就不僅僅是「明白概念」+「畫出示例」那么簡單了，可能還需要自己動手去實現一個 LRU 算法的小 Demo。

146.LRU緩存機制 力扣

在力扣上有這么一道題：

并且給出了提示——在 O(1) 時間復雜度內完成 get 和 put 操作。

一個比較通用的做法是通過 Hashmap + Double Linked List 來完成，圖示如下：

這樣，整個數據的操作過程如下：

實現算法代碼如下：

redis

Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an Approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.

Redis 是一個著名的鍵值對數據庫，在 Using Redis as an LRU cache 中我們知道 Redis 可以用來做為 LRU 緩存（雖然不是一個非常標準的實現，因為 Redis 可能無法選出最佳換出項），Redis 的方法是隨機取出若干個 key，然后按照訪問時間排序后，淘汰掉最不經常使用的頁面，一個較為詳盡的分析在參考資料中已經有所提及，建議有興趣的讀者參考。

參考資料

1.LRU 原理和 Redis 實現——一個今日頭條的面試題

2.LeetCode 算法題解——LRU 緩存機制

本文作者：Nova Kwok

編輯&版式：霍霍

聲明：本文歸 “力扣” 版權所有，如需轉載請聯系。