我的LeetCode：https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 146. LRU緩存機制題目運用你所掌握的數據結構，設計和 ...

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 146. LRU緩存機制

題目

運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 緩存機制。它應該支持以下操作：獲取數據 get 和寫入數據 put 。

獲取數據 get(key) - 如果密鑰 (key) 存在於緩存中，則獲取密鑰的值（總是正數），否則返回 -1。
寫入數據 put(key, value) - 如果密鑰已經存在，則變更其數據值；如果密鑰不存在，則插入該組「密鑰/數據值」。當緩存容量達到上限時，它應該在寫入新數據之前刪除最久未使用的數據值，從而為新的數據值留出空間。

進階:

你是否可以在 O(1) 時間複雜度內完成這兩種操作？

示例:

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lru-cache
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

首先一定要明白LRU的緩存邏輯；
一種思路是直接使用LinkedHashMap來實現LRU緩存，LinkedHashMap有一個關鍵參數是accessOrder，預設為false，也就是按照put的順序排序，若accessOrder為true，那麼將按照訪問時間排序，當前的訪問將位於尾部，歷史訪問將越靠近頭部，恰好符合LRU的邏輯；
另一種思路就是自己實現雙鏈表結構；

思路1-使用LinkedHashMap構造LRU

核心是LinkedHashMap的accessOrder參數，afterNodeAccess方法和removeEldestEntry方法：

afterNodeAccess方法將根據accessOrder實現排序，預設false按照put順序排序，設為true則按照訪問時間排序，符合緩存的更新策略；
removeEldestEntry方法實現淘汰策略，預設false即不淘汰也就是達到最大緩存後將不再resize，設為true將淘汰頭部數據，設定size()>capacity便可實現緩存滿時淘汰舊數據；

創建LinkedHashMap需要使用有參構造方法，同時順帶覆寫其removeEldestEntry方法：

LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75F, true) {
	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;

	@Override
	protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
		return size() > capacity;
	}
};

afterNodeAccess源碼部分，可以看到是實現了元素移動到鏈表尾部：

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

演算法複雜度:

時間複雜度：O(1)
空間複雜度：O(capacity)

思路2-HashMap+自己實現雙鏈表結構

實際與LinkedHashMap類似，唯一的區別在於更新節點時，LinkedHashMap對於相同key的節點需要遍歷key下的鏈表，而自己實現的雙鏈表無需遍歷；

演算法複雜度:

時間複雜度：O(1)
空間複雜度：O(capacity)

演算法源碼示例

package leetcode;

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * @author ZhouJie
 * @date 2020年4月8日 下午9:55:11 
 * @Description: 146. LRU緩存機制
 *
 */
public class LeetCode_0146 {

}

/**
 * @author ZhouJie
 * @date 2020年4月8日 下午10:11:52 
 * @Description: 1-利用LinkedHashMap的特性直接構造一個LRU，缺點：在移除key相同的元素時需要遍歷鏈表
 *
 */
class LRUCache_1 {
	private LinkedHashMap<Integer, Integer> cache;

	public LRUCache_1(int capacity) {
		cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75F, true) {
			/**
			 * 
			 */
			private static final long serialVersionUID = 1L;

			@Override
			protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
				return size() > capacity;
			}
		};

	}

	public int get(int key) {
		Integer value = cache.get(key);
		if (value == null) {
			return -1;
		} else {
			return value;
		}
	}

	public void put(int key, int value) {
		cache.put(key, value);
	}
}

/**
 * @author ZhouJie
 * @date 2020年4月8日 下午10:44:26 
 * @Description: 2-只使用HashMap保存數據，自建Node雙向鏈表來記錄訪問順序；
 *
 */
class LRUCache_2 {
	/**
	 * @author ZhouJie
	 * @date 2020年4月8日 下午10:47:19 
	 * @Description: 定義雙鏈表的Node節點，_0146_2，尾碼為題號_方法號
	 *
	 */
	class Node_0146_2 {
		Node_0146_2 pre;
		Node_0146_2 next;
		int k;
		int v;

		public Node_0146_2(int k, int v) {
			this.k = k;
			this.v = v;
		}
	}

	// 雙鏈表的頭尾節點
	Node_0146_2 head;
	Node_0146_2 tail;
	private int capacity;
	private HashMap<Integer, Node_0146_2> cache;

	public LRUCache_2(int capacity) {
		this.capacity = capacity;
		this.cache = new HashMap<Integer, Node_0146_2>();
	}

	public int get(int key) {
		Node_0146_2 node = cache.get(key);
		if (node != null) {
			moveToTail(node);
			return node.v;
		} else {
			return -1;
		}
	}

	public void put(int key, int value) {
		Node_0146_2 node = cache.get(key);
		// 存在時需要更新map對應值並將節點移到鏈表尾部
		if (node != null) {
			node.v = value;
			moveToTail(node);
		} else {
			// 不存在時需要先判斷容量，滿了需要先刪除頭部節點和對應map中的數據，然後再新建節點放到鏈表的尾部並放入map
			if (cache.size() == capacity) {
				Node_0146_2 oldHead = removeHead();
				if (oldHead != null) {
					cache.remove(oldHead.k);
				}
			}
			Node_0146_2 newNode = new Node_0146_2(key, value);
			addToTail(newNode);
			cache.put(key, newNode);
		}
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月8日 下午11:27:17 
	 * @param: @return
	 * @return: Node_0146_2
	 * @Description: 緩存滿時需要刪除最舊的數據，對應到方法是丟棄頭部節點，返回的節點供map刪除對應數據
	 *
	 */
	private Node_0146_2 removeHead() {
		if (head == null) {
			return null;
		} else {
			Node_0146_2 temp = head;
			head = head.next;
			temp.next = null;
			head.pre = null;
			return temp;
		}
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月8日 下午11:28:53 
	 * @param: @param node
	 * @return: void
	 * @Description: get命中時需要更新緩存，對應到方法是移動節點到尾部
	 *
	 */
	private void moveToTail(Node_0146_2 node) {
		// 若緩存最多只有一個數據或目標節點就是尾部節點時，什麼都不做
		if (head == tail || node == tail) {
			return;
		}
		// 若目標節點是頭結點，則需要先更新頭結點，否則直接改動上下節點的關聯關係
		if (node == head) {
			head = head.next;
			head.pre = null;
		} else {
			node.pre.next = node.next;
			node.next.pre = node.pre;
		}
		// 將目標節點移動到尾部
		tail.next = node;
		node.pre = tail;
		node.next = null;
		tail = node;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月8日 下午11:31:34 
	 * @param: @param node
	 * @return: void
	 * @Description: 新建緩存總是放到尾部
	 *
	 */
	private void addToTail(Node_0146_2 node) {
		// 首個數據
		if (tail == null) {
			head = tail = node;
		}
		tail.next = node;
		node.pre = tail;
		tail = node;
	}

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */