146. LRU緩存
設計和實現(xiàn)一個LRU(最近最少使用)的緩存機制。它可以支持以下操作： get 和 put 哗伯。
獲取數(shù)據(jù) get(key) - 如果 (key) 存在于緩存中寡喝，則獲取值（總是正數(shù)）辉川，否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果key不存在蒲讯，則寫入其數(shù)據(jù)值粹湃。當緩存容量達到上限時恐仑，在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)，從而為新的數(shù)據(jù)留出空間为鳄。
進階:
你能否在 O(1) 時間復雜度內完成裳仆？
例:
LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會使得key 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得key 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
- 本題在LeetCode上在Design分類下
方法一：雙向鏈表隊列實現(xiàn)LRU
思路設計
考慮到題目中的最近最少,我們顯然能聯(lián)想到使用隊列結構。結合題意济赎，為了盡可能的提高插入和查找的效率鉴逞，保證時間復雜度在O(1)，最大程度的提高get和put的速度司训，必然要使用雙向鏈表隊列（單鏈表需要遍歷才能插入節(jié)點液走，時間復雜度高）过咬。而在實現(xiàn)了雙向鏈表隊列結構之后還需要考慮兩點：1、插入數(shù)據(jù)put達到數(shù)量上限時氓癌，刪除最老節(jié)點（最長時間未被使用）滑凉，即鏈表隊列的尾部節(jié)點统扳，因為尾部節(jié)點是最晚插入的喘帚；2、獲取數(shù)據(jù)get到數(shù)據(jù)時咒钟，需要將當前獲取到的節(jié)點移動到隊列頭部吹由，因為最近被使用了。
編碼實踐
public class LRUCache {
/**
*
* Node類用于抽象鏈表的節(jié)點
* key朱嘴、value存儲鍵倾鲫、值，
* before萍嬉、after分別指向當前節(jié)點的前后Node節(jié)點乌昔；
*
*/
class Node {
int key;
int value;
Node before;
Node after;
}
/**
* 使用HashMap緩存Node節(jié)點
*/
private HashMap<Integer, Node> cache = new HashMap<Integer, Node>();
/**
* 最大容量，超過capacity時繼續(xù)插入會觸發(fā)刪除最老未被使用的節(jié)點
*/
private int capacity;
/**
* 頭節(jié)點壤追、尾節(jié)點（注意這兩個節(jié)點不存儲實際的數(shù)據(jù)）
*/
private Node head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node();
head.before = null;
tail = new Node();
tail.after = null;
head.after = tail;
tail.before = head;
}
/**
* 將節(jié)點插入隊列頭部
*
* @param node
*/
private void addToHead(Node node) {
node.before = head;
node.after = head.after;
head.after.before = node;
head.after = node;
}
/**
* 刪除隊列中的一個節(jié)點
*
* @param node
*/
private void removeNode(Node node) {
Node before = node.before;
Node after = node.after;
before.after = after;
after.before = before;
}
/**
* 將節(jié)點移動到有效數(shù)據(jù)頭部
*
* @param node
*/
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
/**
* 刪除有效數(shù)據(jù)尾節(jié)點
*
* @return 尾節(jié)點
*/
private Node popTail() {
Node res = tail.before;
this.removeNode(res);
return res;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1; // should raise exception here.
}
// 如果獲取到數(shù)據(jù)磕道，則將獲取到的節(jié)點移動到隊列頭部;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node == null) {
Node newNode = new Node();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addToHead(newNode);
if (cache.size() > capacity) {
// 刪除隊尾有效數(shù)據(jù)節(jié)點
Node tail = this.popTail();
this.cache.remove(tail.key);
}
} else {
node.value = value;
// 在使用get方法獲取值之后，需要將當前獲取的節(jié)點移動到隊列頭部
moveToHead(node);
}
}
}
說明
見代碼注釋
方法二：Java標準庫JDK里的LinkedHashMap
思路
事實上Java標準庫里提供了可以直接使用的LRU思想的數(shù)據(jù)結構行冰，即LinkedHashMap溺蕉，其底層實現(xiàn)原理和方法一是一致的
編碼實踐
class LRUCache extends LinkedHashMap<Integer,Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F,true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key,-1);
}
public void put(int key, int value) {
super.put(key,value);
}
@Override
public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
return size() > capacity;
}
}
說明
LinkedHashMap提供了可以覆寫的removeEldestEntry方法，removeEldestEntry方法的作用直接參考LinkedHashMap源碼：
/**
* Returns <tt>true</tt> if this map should remove its eldest entry.
* This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
* inserting a new entry into the map. It provides the implementor
* with the opportunity to remove the eldest entry each time a new one
* is added. This is useful if the map represents a cache: it allows
* the map to reduce memory consumption by deleting stale entries.
*
* <p>Sample use: this override will allow the map to grow up to 100
* entries and then delete the eldest entry each time a new entry is
* added, maintaining a steady state of 100 entries.
* <pre>
* private static final int MAX_ENTRIES = 100;
*
* protected boolean removeEldestEntry(Map.Entry eldest) {
* return size() > MAX_ENTRIES;
* }
* </pre>
*
* <p>This method typically does not modify the map in any way,
* instead allowing the map to modify itself as directed by its
* return value. It <i>is</i> permitted for this method to modify
* the map directly, but if it does so, it <i>must</i> return
* <tt>false</tt> (indicating that the map should not attempt any
* further modification). The effects of returning <tt>true</tt>
* after modifying the map from within this method are unspecified.
*
* <p>This implementation merely returns <tt>false</tt> (so that this
* map acts like a normal map - the eldest element is never removed).
*
* @param eldest The least recently inserted entry in the map, or if
* this is an access-ordered map, the least recently accessed
* entry. This is the entry that will be removed it this
* method returns <tt>true</tt>. If the map was empty prior
* to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
* in this invocation, this will be the entry that was just
* inserted; in other words, if the map contains a single
* entry, the eldest entry is also the newest.
* @return <tt>true</tt> if the eldest entry should be removed
* from the map; <tt>false</tt> if it should be retained.
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
大概意思是在新插入一個節(jié)點時悼做，刪除最老的節(jié)點焙贷，在緩存數(shù)據(jù)時可以用到（簡直是LRU思想的量身定做）。另外如果使用默認false的話贿堰，表示容器沒有限制大小辙芍，不刪除最老未被使用的節(jié)點，相當于使用普通的Map羹与。
還可以注意到注釋中有一段很醒目的demo寫法：
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
本題中由于限制條件為超過隊列最大值限制大小即開始刪除最老節(jié)點故硅，因此使用size() > capacity判斷條件。注意到get方法不是直接調用而是使用的getOrDefault(key,-1)是由于題目描述當get拿不到數(shù)據(jù)時默認返回-1纵搁。
彩蛋
觀察方法一手寫雙向鏈表的實現(xiàn)吃衅，addToHead將節(jié)點添加到頭部方法以及popTail刪除尾節(jié)點的方法，分別是添加節(jié)點到頭部第二個節(jié)點腾誉，以及刪除倒數(shù)第二個節(jié)點徘层，這是為什么呢？這便是本篇的彩蛋利职。
結語
針對阿里的LRU面試題趣效，本題分析了兩種解法。個人猜測阿里出題者的出題思路是考察LRU思想的理解猪贪，在理解思想的基礎上可能會進一步延伸到LinkedHashMap的源碼跷敬，LinkedHashMap熟悉了會假裝不經意繼續(xù)深入到它的父類HashMap，到了HashMap肯定繼續(xù)會問你負載因子热押，Hash碰撞西傀，紅黑樹裂變斤寇，左右旋扯完了HashMap再和你談談HashTable和區(qū)別...你會發(fā)現(xiàn)總有一處可能命中你的盲點，是不是細思極恐拥褂，哈哈～不要方娘锁，掃一掃，關注我的微信訂閱號饺鹃，后續(xù)會有針對類似LinkedHashMap等比較重要?的數(shù)據(jù)結構的源碼分析系列文章莫秆，敬請期待！最后尤慰，如果覺得本文對你有所幫助或啟發(fā)那就來個贊吧0.0
作者：Java數(shù)據(jù)結構與算法
鏈接：http://www.reibang.com/p/e66fc529cfe9
來源：簡書
簡書著作權歸作者所有馏锡，任何形式的轉載都請聯(lián)系作者獲得授權并注明出處。
