10行Java代碼實(shí)現(xiàn)最近被使用（LRU）緩存
在最近的面試中，我曾被多次問到，怎么實(shí)現(xiàn)一個(gè)最近最少使用（LRU）的緩存。緩存可以通過哈希表來實(shí)現(xiàn)，然而為這個(gè)緩存增加大小限制會變成另一個(gè)有意思的問題?，F(xiàn)在我們看一下怎么實(shí)現(xiàn)。
最近最少使用緩存的回收
為了實(shí)現(xiàn)緩存回收，我們需要很容易做到：
-
查詢出最近最晚使用的項(xiàng)
-
給最近使用的項(xiàng)做一個(gè)標(biāo)記
鏈表可以實(shí)現(xiàn)這兩個(gè)操作。檢測最近最少使用的項(xiàng)只需要返回鏈表的尾部。標(biāo)記一項(xiàng)為最近使用的項(xiàng)只需要從當(dāng)前位置移除，然后將該項(xiàng)放置到頭部。比較困難的事情是怎么快速的在鏈表中找到該項(xiàng)。
哈希表的幫助
看一下我們工具箱中的數(shù)據(jù)結(jié)構(gòu)，哈希表可以在（消耗）常量的時(shí)間內(nèi)索引到某個(gè)對象。如果我們創(chuàng)建一個(gè)形如key->鏈表節(jié)點(diǎn)的哈希表，我們就能夠在常量時(shí)間內(nèi)找到最近使用的節(jié)點(diǎn)。更甚的是，我們也能夠在常量時(shí)間內(nèi)判斷節(jié)點(diǎn)的是否存在（或不存在）；
找到這個(gè)節(jié)點(diǎn)后，我們就能將這個(gè)節(jié)點(diǎn)移動到鏈表的最前端，標(biāo)記為最近使用的項(xiàng)了。
Java的捷徑
據(jù)我所知，很少有一種編程語言的標(biāo)準(zhǔn)庫中有通用的數(shù)據(jù)結(jié)構(gòu)能提供上述功能的。這是一種混合的數(shù)據(jù)結(jié)構(gòu)，我們需要在哈希表的基礎(chǔ)上建立一個(gè)鏈表。但是 Java已經(jīng)為我們提供了這種形式的數(shù)據(jù)結(jié)構(gòu)-LinkedHashMap！它甚至提供可覆蓋回收策略的方法（見removeEldestEntry文檔）。***需要我們注意的事情是，改鏈表的順序是插入的順序，而不是訪問的順序。但是，有一個(gè)構(gòu)造函數(shù)提供了一個(gè)選項(xiàng)，可以使用訪問的順序（見文檔）。
無需多說：
- import java.util.LinkedHashMap;
- import java.util.Map;
- public LRUCache<K, V> extends LinkedHashMap<K, V> {
- private int cacheSize;
- public LRUCache(int cacheSize) {
- super(16, 0.75, true);
- this.cacheSize = cacheSize;
- }
- protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
- return size() >= cacheSize;
- }
- }
