LRU是Least Recently Used的縮寫，即最近最久未使用，常用于頁面置換算法，是為虛擬頁式存儲管理服務(wù)的。

LRU算法的提出，是基于這樣一個事實(shí)：在前面幾條指令中使用頻繁的頁面很可能在后面的幾條指令中頻繁使用。反過來說，已經(jīng)很久沒有使用的頁面很可能在未來較長的一段時間內(nèi)不會被用到。

設(shè)計(jì)并實(shí)現(xiàn)了一個最近最少使用（LRU）緩存的數(shù)據(jù)結(jié)構(gòu)，它應(yīng)該支持以下操作：get和set。
get(key)——如果鍵存在于緩存中，則獲得鍵值（總是正數(shù)），否則返回-1。
set(key, value)——如果鍵不存在，則設(shè)置或插入值。當(dāng)緩存達(dá)到其容量時，應(yīng)在插入新項(xiàng)之前使最近最少使用的項(xiàng)無效。

分析：LRU緩存可使用一個HashMap和雙向鏈表實(shí)現(xiàn)。HashMap，使得get的時間是O（1）；雙向鏈表使節(jié)點(diǎn)添加/刪除操作O（1）。

定義雙向鏈表的節(jié)點(diǎn)：

class Node{
    int key;
    int value;
    Node pre;
    Node next;
 
    public Node(int key, int value){
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    int capacity;
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    Node head=null;
    Node end=null;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
 
    public int get(int key) {
        if(map.containsKey(key)){
            Node n = map.get(key);
            remove(n);
            setHead(n);
            return n.value;
        }
 
        return -1;
    }
 
    public void remove(Node n){
        if(n.pre!=null){
            n.pre.next = n.next;
        }else{
            head = n.next;
        }
 
        if(n.next!=null){
            n.next.pre = n.pre;
        }else{
            end = n.pre;
        }
 
    }
 
    public void setHead(Node n){
        n.next = head;
        n.pre = null;
 
        if(head!=null)
            head.pre = n;
 
        head = n;
 
        if(end ==null)
            end = head;
    }
 
    public void set(int key, int value) {
        if(map.containsKey(key)){
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        }else{
            Node created = new Node(key, value);
            if(map.size()>=capacity){
                map.remove(end.key);
                remove(end);
                setHead(created);
 
            }else{
                setHead(created);
            }    
 
            map.put(key, created);
        }
    }
}

關(guān)于操作系統(tǒng)的內(nèi)存管理，如何節(jié)省利用容量不大的內(nèi)存為最多的進(jìn)程提供資源，一直是研究的重要方向。而內(nèi)存的虛擬存儲管理，是現(xiàn)在最通用，最成功的方式—— 在內(nèi)存有限的情況下，擴(kuò)展一部分外存作為虛擬內(nèi)存，真正的內(nèi)存只存儲當(dāng)前運(yùn)行時所用得到信息。這無疑極大地擴(kuò)充了內(nèi)存的功能，極大地提高了計(jì)算機(jī)的并發(fā)度。虛擬頁式存儲管理，則是將進(jìn)程所需空間劃分為多個頁面，內(nèi)存中只存放當(dāng)前所需頁面，其余頁面放入外存的管理方式。

有利就有弊，虛擬頁式存儲管理增加了進(jìn)程所需的內(nèi)存空間，卻也帶來了運(yùn)行時間變長這一缺點(diǎn)：進(jìn)程運(yùn)行過程中，不可避免地要把在外存中存放的一些信息和內(nèi)存中已有的進(jìn)行交換，由于外存的低速，這一步驟所花費(fèi)的時間不可忽略。因而，采取盡量好的算法以減少讀取外存的次數(shù)，也是相當(dāng)有意義的事情。