LUR(最近最少使用算法分析)

详解
https://zhuanlan.zhihu.com/p/52196637

实例代码：

public class LRUDemo {

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

    private Node head;
    private Node end;
    //缓存存储上限
    private int limit;
    private HashMap<String,Node> hashMap;

    public LRUDemo(int limit){
        this.limit = limit;
        hashMap =new HashMap<String,Node>();
    }

    public String get(String key){
        Node node = hashMap.get(key);
        if(node ==null){
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    public void put(String key,String value){
        Node node = hashMap.get(key);
        if(node ==null){
            //如果key不存在，插入key-value
            if(hashMap.size()>= limit){//大于缓存最大长度，移除掉队列最左边的元素，把当前元素添加到最右边
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node =new Node(key, value);
            addNode(node);
            hashMap.put(key, node);
        }else{
            //如果key存在，刷新key-value
            node.value = value;
            refreshNode(node);
        }
    }

    public void remove(String key){
        Node node = hashMap.get(key);
        removeNode(node);
        hashMap.remove(key);
    }


    /**
     * 刷新被访问的节点位置
     * 比如访问用户2，需要先把用户2删除，然后添加到最右边
     * @param node 被访问的节点
     */
    private void refreshNode(Node node){
        //如果访问的是尾节点，无需移动节点
        if(node ==end){
            return;
        }
        //移除节点
        removeNode(node);
        //重新插入节点
        addNode(node);
    }


    /**
     * 删除节点
     * @param 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;
    }

    /**
     * 尾部插入节点
     * @param node 要插入的节点
     */
    private void addNode(Node node){
        if(end!=null){
            end.next= node;
            node.pre =end;
            node.next=null;
        }
        end= node;
        if(head ==null){
            head = node;
        }
    }


    public static void main(String[] args){
        LRUDemo lruCache =new LRUDemo(5);
        lruCache.put("001","用户1信息");
        lruCache.put("002","用户2信息");
        lruCache.put("003","用户3信息");
        lruCache.put("004","用户4信息");
        lruCache.put("005","用户5信息");
        lruCache.get("002");//访问用户2，此时应该把2删除，然后重新插入到最右边
        System.out.println(lruCache.end.value);//用户2信息,此时顺序为：1-3-4-5-2
        lruCache.put("006","用户6信息");

        System.out.println(lruCache.head.value);//此时顺序为：3-4-5-2-6
        System.out.println(lruCache.end.value);
    }


}