LRU缓存机制

问题陈述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

你是否可以在 O(1) 时间复杂度内完成这两种操作？

思路分析

要让put和get操作的时间复杂度为O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插入快，删除快，有顺序之分。

通常哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

代码实现

1、首先我们设计双链表的结点类，假定key和val都为int类型。

class Node{
    public int key,val;
    public Node prev,next;
    public Node(int k,int v){
        this.key=k;
        this.val=v;
    }
}

2、根据Node类构建双链表。

class DoubleList{
    private Node head,tail;//虚拟首尾结点，头无前驱，尾无后继。
    private int size;//链表元素个数
    
    public DoubleList(){
        head=new Node(0,0);
        tail=new Node(0,0);
        head.next=tail;
        tail.prev=head;
        size=0;
    }
    //在链表头部添加结点
    public void addFirst(Node x){
        x.next=head.next;
        x.prev=head;
        head.next.prev=x;
        head.next=x;
        size++;
    }
    //删除链表中的结点x
    public void delete(Node x){
        x.prev.next=x.next;
        x.next.prev=x.prev;
        size--;
    }
    //删除链表中最后一个结点，并返回该结点
    public Node removeLast(){
        if(tail.prev=head) return null;
        Node last = tail.prev;
        delete(last);
        return last;
    }
    //返回链表长度
    public int size(){
        return size;
    }
}

3、LRU缓存实现

class LRUCache{
    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int Capacity;
    
    public LRUCache(int capacity){
        this.Capacity=capacity;
        map=new HashMap<>();
        cache=new DoubleList();
    }
    
    public int get(int key){
        if(!map.containsKey(key)) return -1;
        int val=map.get(key).val;
        put(key,val);
        return val;
    }
    
    public void put(int key,int val){
        Node x=new Node(key,val);
        
        if(map.containsKey(key)){//key存在，则更新值。
            cache.delete(map.get(key));
            cache.addFirst(x);
            map.put(key,x);
        }else{ //key不存在，首先判断是否到达容量，达到则删除最末尾元素，然后将新元素添加到链表头。 
            if(Capacity==cache.size()){
            Node last=cache.removeLast();
            map.delete(last.key);
            }
            cache.addFirst(x);
            map.put(key,x);
        }
    }
        
}