LRU（Least Recently Used）緩存算法的實現
LRU就是Least Recently Used，即最近最少使用，是一種常用的頁面置換算法，將最近長時間未使用的頁面淘汰，其實也很簡單，就是要將不受歡迎的頁面及時淘汰，不讓它占著茅坑不拉shit，浪費資源。
LRU是一種常見的頁面置換算法，在計算中，所有的文件操作都要放在內存中進行，然而計算機內存大小是固定的，所以我們不可能把所有的文件都加載到內存，因此我們需要制定一種策略對加入到內存中的文件進項選擇。
常見的頁面置換算法有如下幾種：
- LRU 最近最久未使用
- FIFO 先進先出置換算法 類似隊列
- OPT 最佳置換算法 (理想中存在的)
- NRU Clock置換算法
- LFU 最少使用置換算法
- PBA 頁面緩沖算法
LRU原理
LRU的設計原理就是，當數據在最近一段時間經常被訪問，那么它在以后也會經常被訪問。這就意味著，如果經常訪問的數據，我們需要然其能夠快速命中，而不常訪問的數據，我們在容量超出限制內，要將其淘汰。
其核心就是利用棧，進行操作，其中主要有兩項操作，get和put
get
get時，若棧中有值則將該值的key提到棧頂，沒有時則返回null
put
棧未滿時，若棧中有要put的key，則更新此key對應的value，并將該鍵值提到棧頂，若無要put的key，直接入棧
棧滿時，若棧中有要put的key，則更新此key對應的value，并將該鍵值提到棧頂;若棧中沒有put的key 時，去掉棧底元素，將put的值入到棧頂
解法：維護一個數組，提供 get 和 put 方法，并且限定 max 數量。
使用時，get 可以標記某個元素是最新使用的，提升它去第一項。put 可以加入某個key-value，但需要判斷是否已經到最大限制 max
若未到能直接往數組第一項里插入 若到了最大限制 max，則需要淘汰數據尾端一個元素。
- LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
- cache.put(1, 1);
- cache.put(2, 2);
- cache.get(1); // 返回 1
- cache.put(3, 3); // 該操作會使得密鑰 2 作廢
- cache.get(2); // 返回 -1 (未找到)
- cache.put(4, 4); // 該操作會使得密鑰 1 作廢
- cache.get(1); // 返回 -1 (未找到)
- cache.get(3); // 返回 3
- cache.get(4); // 返回 4
LRU 算法設計
分析上面的操作過程，要讓 put 和 get 方法的時間復雜度為 O(1)，我們可以總結出 cache 這個數據結構必要的條件：查找快，插入快，刪除快，有順序之分。
因為顯然 cache 必須有順序之分，以區分最近使用的和久未使用的數據;而且我們要在 cache 中查找鍵是否已存在;如果容量滿了要刪除最后一個數據;每次訪問還要把數據插入到隊頭。
那么，什么數據結構同時符合上述條件呢?哈希表查找快，但是數據無固定順序;鏈表有順序之分，插入刪除快，但是查找慢。所以結合一下，形成一種新的數據結構：哈希鏈表。
LRU 緩存算法的核心數據結構就是哈希鏈表，雙向鏈表和哈希表的結合體。這個數據結構長這樣：
js 實現
- 具體代碼 一般的解法，通過維護一個數組，數組項存放了 key-value 鍵值對對象，每次需要遍歷去尋找 key 值所在的數組下標操作。
已經通過 leetCode 146 的檢測。執行用時 : 720 ms。內存消耗 : 58.5 MB。
- function LRUCache(capacity) {
- this.capacity = capacity; // 最大限制
- this.cache = [];
- };
- /**
- * @param {number} key
- * @return {number}
- */
- LRUCache.prototype.get = function (key) {
- let index = this.cache.findIndex((item) => item.key === key);
- if (index === -1) {
- return -1;
- }
- // 刪除此元素后插入到數組第一項
- let value = this.cache[index].value;
- this.cache.splice(index, 1);
- this.cache.unshift({
- key,
- value,
- });
- return value;
- };
- /**
- * @param {number} key
- * @param {number} value
- * @return {void}
- */
- LRUCache.prototype.put = function (key, value) {
- let index = this.cache.findIndex((item) => item.key === key);
- // 想要插入的數據已經存在了，那么直接提升它就可以
- if (index > -1) {
- this.cache.splice(index, 1);
- } else if (this.cache.length >= this.capacity) {
- // 若已經到達最大限制，先淘汰一個最久沒有使用的
- this.cache.pop();
- }
- this.cache.unshift({ key, value });
- };
上面的做法其實有變種，可以通過一個對象來存鍵值對，一個數組來存放鍵的順序。
- 進階要求O(1)
時間復雜度 O(1)，那就不能數組遍歷去查找 key 值。可以用 ES6 的 Map 來解了，因為 Map 既能保持鍵值對，還能記住插入順序。
- function LRUCache(capacity) {
- this.cache = new Map();
- this.capacity = capacity; // 最大限制
- };
- LRUCache.prototype.get = function (key) {
- if (this.cache.has(key)) {
- // 存在即更新
- let temp = this.cache.get(key);
- this.cache.delete(key);
- this.cache.set(key, temp);
- return temp;
- }
- return -1;
- };
- LRUCache.prototype.put = function (key, value) {
- if (this.cache.has(key)) {
- // 存在即更新（刪除后加入）
- this.cache.delete(key);
- } else if (this.cache.size >= this.capacity) {
- // 不存在即加入
- // 緩存超過最大值，則移除最近沒有使用的
- this.cache.delete(this.cache.keys().next().value);
- }
- this.cache.set(key, value);
- };
