LRU算法的实现原理？

LRU（Least recently used，最近最少使用）

java简单实现：

import java.util.HashMap;
class Node{
    public Node(String key,String value){
        this.key = key;
        this.value = value;
    }
    public Node pre;
    public Node next;
    public String key;
    public String value;
}
public class LRUCache {
    private Node head;
    private Node end;
    //缓存上限
    private int limit;
    private HashMap map;
    public LRUCache(int limit) {
        this.limit = limit;
        map = new HashMap();
    }
    public String get(String key) {
        Node node = map.get(key);
        if(node == null) {
            return null;
        }
        //调整node到尾部
        refreshNode(node);
        return node.value;
    }
    public void put(String key, String value) {
        Node node = map.get(key);
        if(node == null) {
            //key不存在直接插入
            while(map.size() >= limit) {
                //去除链表内的节点
                String oldKey = removeNode(head);
                //去除map中的缓存
                map.remove(oldKey);
            }
            node = new Node(key, value);
            //链表中加入节点
            addNode(node);
            //map中加入节点
            map.put(key, node);
        } else {
            //更新节点并调整到尾部
            node.value = value;
            refreshNode(node);
        }
    }
    private void refreshNode(Node node) {
        //如果访问的是尾节点，无须移动节点
        if(node == end) {
            return; 
        }
        //把节点移动到尾部，相当于做一次删除插入操作
        removeNode(node);
        addNode(node);
    }
    private String removeNode(Node node) {
        //尾节点
        if(node == end) {
            end = end.pre;
        } else if(node == head) {
        //头结点
            head = head.next;
        } else {
            //中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }
    private void addNode(Node node) {
        if(end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if(head == null) {
            head = node;
        }
    }
}

通过查看LinkedHashMap源码会发现构造函数默认有一个accessOrder = false;。

官方对他的注释是The iteration ordering method for this linked hash map: true for access-order, false for insertion-order.，意思是“对于此linked hash map的迭代排序而言，accessOrder是true的话，按照访问顺序存储，accessOrder是false的话，按照插入顺序存储”。

public LinkedHashMap(int initialCapacity, float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
 }

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
 }

/**
 * Sample use: this override will allow the map to grow up to 100 
 * entries and then delete the eldest entry each time a new entry is 
 * added, maintaining a steady state of 100 entries.
 * private static final int MAX_ENTRIES = 100;
 * protected boolean removeEldestEntry(Map.Entry eldest) {
 *      return size() > MAX_ENTRIES;
 * }
 */

一目了然了，所以一般只要这么写就可以实现LRU：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_CACHE_SIZE;

    public LRUCache2(int ***Size) {
        super((int) Math.ceil(***Size / 0.75) + 1, 0.75f, true);
        MAX_CACHE_SIZE = ***Size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_CACHE_SIZE;
    }
}