一、算法介紹

最近最久未使用（Least Recently Used? ? LRU）算法是?種緩存淘汰策略，它是大部分操作系統(tǒng)為最大化頁面命中率而廣泛采用的一種頁面置換算法。該算法的思路是，發(fā)生缺頁中斷時，將最近一段時間內(nèi)最久未使用的頁面置換出去。 從程序運行的原理來看，最近最久未使用算法是比較接近理想的一種頁面置換算法，這種算法既充分利用了內(nèi)存中頁面調(diào)用的歷史信息，又正確反映了程序的局部問題。

虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，內(nèi)存中只存放當前所需頁面，其余頁面放入外存的管理方式。
有利就有弊，虛擬頁式存儲管理減少了進程所需的內(nèi)存空間，卻也帶來了運行時間變長這一缺點：進程運行過程中，不可避免地要把在外存中存放的一些信息和內(nèi)存中已有的進行交換，由于外存的低速，這一步驟所花費的時間不可忽略。因而，采取盡量好的交換算法以減少讀取外存的次數(shù)，也是相當有意義的事情。

二、基本原理

假設 序列為 4 3 4 2 3 1 4 2
物理塊有3個 則
4調(diào)入內(nèi)存 4
3調(diào)入內(nèi)存 3 4
4調(diào)入內(nèi)存 4 3
2調(diào)入內(nèi)存 2 4 3
3調(diào)入內(nèi)存 3 2 4
1調(diào)入內(nèi)存 1 3 2（因為最少使用的是4，所以丟棄4）
4調(diào)入內(nèi)存 4 1 3（原理同上）
2調(diào)入內(nèi)存 2 4 1

規(guī)律就是，如果新存入或者訪問一個值，則將這個值放在隊列開頭。如果存儲容量超過上限cap，那么刪除隊尾元素，再存入新的值。

我們下面通過一個簡單的存儲int的方式來實現(xiàn)LRU cache，實現(xiàn)put和get功能。

三、數(shù)據(jù)結(jié)構(gòu)

?先要接收?個參數(shù)作為緩存的最?容量， 然后實現(xiàn)兩個 API， ?個是 put(key, val) ?法存?鍵值對，get(key) ?法獲取 key 對應的 val， 如果 key 不存在則返回null，get 和 put ?法必須都是 O(1) 的時間復雜度。

因此LRU cache 的數(shù)據(jù)結(jié)構(gòu)的必要的條件： 查找快， 插?快， 刪除快， 有順序之分。那么， 什么數(shù)據(jù)結(jié)構(gòu)同時符合上述條件呢？ 哈希表查找快， 但是數(shù)據(jù)?固定順序； 鏈表有順序之分， 插?刪除快， 但是查找慢。 所以結(jié)合?下， 形成?種新的數(shù)據(jù)結(jié)構(gòu)： 哈希鏈表。如下圖所示：

四、算法細節(jié)

新插入的元素或者最新查詢的元素要放到鏈表的頭部，對于長時間未訪問的元素要放到鏈表尾部，所以每次插入或者查詢都需要維護鏈表中元素的順序。

使用哈希表的原因是查詢時間復雜度為O(1)，使用雙向鏈表的原因是對于刪除和插入操作時間復雜度為O(1)。

其中哈希表中存儲的 key 為 K，value 為 Node<K,V> 的引用，雙向鏈表存儲的元素為Node<K,V>的引用.

put 方法是線程安全方法，定義如下所示:

public synchronized void put(K key,V value)

對于put操作：

①首先判斷緩存中 元素 K 是否存在，如果存在，則把鏈表中的元素Node<K, V>刪除，map中的數(shù)據(jù)<K, Node<K, V> >不用刪除，再在鏈表頭部插入元素，并更新map，直接返回即可?；

②緩存不存在，并且緩存沒有滿的話，直接把元素插入鏈表的表頭，緩存滿了的話移除表尾元素（最舊未訪問元素）,將元素K插入表頭，增加map中的<K, Node<K, V>>, 更新map。

get 方法是線程安全方法，定義如下所示:

public synchronized V get(K key)

對于get操作：

首先要判斷 緩存中(map)是否存在，如果存在則把該節(jié)點刪除并在鏈表頭部插入該元素并更新map 返回當前元素即可，如果map不存在 則直接返回null；文章來源地址http://www.zghlxwxcb.cn/news/detail-693752.html

五、算法實現(xiàn)

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用偽頭部和偽尾部節(jié)點
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通過哈希表定位，再移到頭部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，創(chuàng)建一個新的節(jié)點
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加進哈希表
            cache.put(key, newNode);
            // 添加至雙向鏈表的頭部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，刪除雙向鏈表的尾部節(jié)點
                DLinkedNode tail = removeTail();
                // 刪除哈希表中對應的項
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通過哈希表定位，再修改 value，并移到頭部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

六、總結(jié)

到了這里，關(guān)于LRU算法（JAVA實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！