【LeetCode 题解】 LRU Cache

浏览数：58 / 时间：2015年06月20日

设计并实现最近最久未使用（Least Recently Used）缓存。

链接：https://oj.leetcode.com/problems/lru-cache/

题目描述：

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

设计并实现最近最久未使用的缓存数据结构，支持 get 和 set 操作.

get()-如果 key 存在，返回对应的 value 值，否则返回 -1.

set()-插入 key 对应的 value 到缓存中，如果缓存已满，将最近最久未使用的元素从缓存中移除。

要实现这个设计，我们先回顾一下大学课堂上的知识。
LRU，即最近最少使用，是操作系统内存管理的一种页面置换算法，
常见的页面置换算法，最佳置换算法（OPT，理想置换算法），先进先出置换算法(FIFO)，
最近最久未使用算法(LRU),最少使用算法。

其中，最佳置换算法是一种理想情况下的页面置换算法，实际上不可能实现。该算法的基本思想是发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法规定标记最大的页应该被置换。但当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。这个算法无法实现，但可以用于对可实现算法的性能进行衡量。

另外两种主要算法，LFU算法-实现缓存，FIFO算法-实现缓存，可以查看这里。

LRU的实现方法有很多，传统的LRU实现方法:

1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。

Java语言可以利用 LinkedHashMap， LinkedHashMap 是有序的哈希表，可以保存记录的插入顺序，并且按使用顺序排列。
重写其中的removeEldestEntry(Map.Entry)方法，就可以实现LRU算法。

我看了一下，在Mysql Jdbc Util和Apache的很多Jar包中，都是使用LinkedHashMap实现LRUCache。
下面的代码来自mysql-connector-java-5.1.18-bin.jar。

package com.mysql.jdbc.util;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache extends LinkedHashMap
{

    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        return size() > maxElements;
    }

    private static final long serialVersionUID = 1L;
    protected int maxElements;
}

不过LeetCode的OJ不支持这样实现，将上面的代码修改后提交，提示 Comoile Error .

我们来看一下，LinkedHashMap是通过继承HashMap，维护一个双链表实现，
当某个Cache位置被命中，通过调整链表的指向将该位置调整到头位置，新加入的内容直接放在链表头，在多次进行Cache操作后，最近使用的Cache就会向链表头部移动，链表尾部就是命中次数最少，最久未使用的Cache。空间充满时，移除尾部的数据就可以了。

题目有几点需要注意，一个是Key不存在的情况，一个是缓存设计要求Key唯一。

下面使用双向链表(双链表)实现LRU Cache，以下代码提交AC。

import java.util.HashMap;
/**
 * Design and implement a data structure for Least Recently Used (LRU) cache. 
 * It should support the following operations: get and set.
 * get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
 * set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity,
 *  it should invalidate the least recently used item before inserting a new item.
 *  近期最少使用算法 设计缓存
 */
public class LRUCache {
    
    private int cacheSize;//缓存容量
    private int currentSize;//当前容量
    private HashMap<Object, CacheNode> nodes;//缓存容器
    private CacheNode head;//链表头
    private CacheNode last;//链表尾

    class CacheNode{
        CacheNode prev;//前一节点
        CacheNode next;//后一节点
        int value;//值
        int key;//键
        CacheNode() {
        }
    }
    
    //初始化缓存
    public LRUCache(int capacity) {
        currentSize=0;
        cacheSize=capacity;
        nodes=new HashMap<Object, CacheNode>(capacity);    
    }
        
    public Integer get(int key) {
        CacheNode node = nodes.get(key);
        if (node != null) {
            move(node);
            return node.value;
        } else {
            return -1;//error code
        }
            
    }
        
    public void set(int key, int value) {
        CacheNode node = nodes.get(key);
        //重复Key
        if(node!=null){
            node.value=value;
            move(node);
            nodes.put(key, node);
        }else
           {//key未重复，正常流程
            node =new CacheNode();
            if(currentSize>=cacheSize){
                if (last != null){//缓存已满，进行淘汰
                    nodes.remove(last.key);}
                removeLast();//移除链表尾部并后移    
            }else{
                currentSize++;
            }
            
            node.key=key;
            node.value=value;
            move(node);
            nodes.put(key, node);
        }
    }
    
    //移动链表节点至头部
    private void move(CacheNode cacheNode){
        if(cacheNode==head)
            return;
        //链接前后节点
        if(cacheNode.prev!=null)
            cacheNode.prev.next=cacheNode.next;
        if(cacheNode.next!=null)
            cacheNode.next.prev=cacheNode.prev;
        //头尾节点
        if (last == cacheNode)
            last = cacheNode.prev;
        if (head != null) {
            cacheNode.next = head;
            head.prev = cacheNode;
        }
        //移动后的链表
        head = cacheNode;
        cacheNode.prev = null;
        //节点唯一的情况
        if (last == null)
            last = head;
    }
    
    //移除指定缓存
    public void remove(int key){
        CacheNode cacheNode =  nodes.get(key);
        if (cacheNode != null) {
            if (cacheNode.prev != null) {
                cacheNode.prev.next = cacheNode.next;
            }
            if (cacheNode.next != null) {
                cacheNode.next.prev = cacheNode.prev;
            }
            if (last == cacheNode)
                last = cacheNode.prev;
            if (head == cacheNode)
                head = cacheNode.next;
        }
        
    }
    //删除尾部的结点，即去除最近最久未使用数据
    private void removeLast(){
        if(last!=null){
            if(last.prev!=null){
                last.prev.next=null;                
            }else{//空间大小为1的情况
                head = null;                
            }
            last = last.prev;
        }
    }
    
    public void clear() {
        head = null;
        last = null;
    }
    //测试用例
//    public static void main(String[] args){
//        LRUCache lCache=new LRUCache(2);
//        lCache.set(2, 1);
//        lCache.set(1, 1);
//        lCache.set(2, 3);
//        lCache.set(4, 1);
//        System.out.println(lCache.get(1));
//        System.out.println(lCache.get(2));
//        
//    }

}

下面是提交中遇到的几组测试用例：

Input:    2,[get(2),set(2,6),get(1),set(1,5),set(1,2),get(1),get(2)]
Expected:    [-1,-1,2,6]

Input:    2,[set(2,1),set(1,1),set(2,3),set(4,1),get(1),get(2)]
Expected:    [-1,3]

Input:    1,[get(0)]
Expected:    [-1]