LRU算法简介及Java实现

LRU是Least Recently Used 的缩写，即最近最少使用，常用于置换页面算法，为虚拟页式存储管理服务。 LRU算法的提出，是基于这样一个事实：在前面几条指令中频繁使用的页面很可能在后面的几条指令中频繁使用。 反过来说，已经很久没有使用的很可能在未来较长的一段时间内不会被用到。 这就是著名的局部性原理。此外LRU算法也经常被用作缓存淘汰策略。 本文基于LRU算法的思想，使用Java语言实现一个我们自己的缓存工具类。

 最常见的实现是使用一个双向链表保存缓存数据，详细算法实现如下：

1、新数据插入到链表头部;                                                                                                    2、每当缓存命中（即缓存数据被访问），则将数据移到链表头部;                                          3、当链表满的时候，将链表尾部的数据丢弃.                                                                          

 优点：实现简单                                                                                                                               缺点：每次访问都需要更新链表，因此代价略高。

 本文将提供两个不同的实现版本，不过实现思想都是一摸一样的。 

import java.util.HashMap;
public class LRUCache01 {

    //双向链表节点定义
    class Node{
        int key;
        int value;
        Node prev;
        Node next;
    }

    private int capacity;
    //保存链表的头部节点和尾部节点
    private Node first;
    private Node last;

    private HashMap map;

    public LRUCache01(int capacity){
        this.capacity = capacity;
        map = new HashMap<>(capacity);
    }

    public int get(int key){
        Node node = map.get(key);
        //为空返回-1
        if(node==null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    private void moveToHead(Node node) {
        if(node==first){
            return;
        }else if(node==last){
            last.prev.next = null;
            last = last.prev;
        }else{
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        node.prev = first.prev;
        node.next = first;
        first.prev = node;
        first = node;
    }

    public void put(int key,int value){
        Node node = map.get(key);
        if(node==null){
            node = new Node();
            node.key = key;
            node.value = value;
            if(map.size()==capacity){
                removeLast();
            }
            addToHead(node);
            map.put(key,node);
        }else{
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(Node node) {
        if(map.isEmpty()){
            first = node;
            last = node;
        }else{
            node.next = first;
            first.prev = node;
            first = node;
        }
    }

    public void removeLast(){
        map.remove(last.key);
        Node prevNode = last.prev;
        if(prevNode!=null){
            prevNode.next = null;
            last = prevNode;
        }
    }

    @Override
    public String toString() {
        return map.keySet().toString();
    }
}

测试

public class LRUCache01Test {
    public static void main(String[] args) {
        LRUCache01 cache = new LRUCache01(3);
        cache.put(1,1);
        cache.put(2,2);
        cache.put(3,3);
        System.out.println(cache.get(1));
        cache.put(4,3);
        System.out.println(cache);
    }
}

版本二

其实JDK已经为我们提供了一个基于HashMap和双向链表实现的数据结构，它就是linkedHashMap，它内部维护的双向链表，可以帮助我们维护两种顺序：

• 插入顺序
• LRU顺序