lru缓存机制-ag真人游戏

代码 

哈希表  双链表

class lrucache {
    //双向链表节点
    private static class dlistnode{
        int key;
        int value;
        dlistnode prev;
        dlistnode next;
        dlistnode(){
        }
        dlistnode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    //缓存的最大容量
    private int capacity;
    //缓存的当前大小
    private int size;
    private dlistnode head;
    private dlistnode tail;
    //真正的缓存结构
    private map cache = new hashmap<>();
    public lrucache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        //构造函数中初始化一个有尾结点和头节点的双向链表
        head = new dlistnode();
        tail = new dlistnode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
         dlistnode dlistnode = cache.get(key);
        if(dlistnode == null){
            return -1;
        }
        //找到链表节点则将其加入到链表头，并返回链表的节点
        removenode(dlistnode);
        addnodetohead(dlistnode);
        return dlistnode.value;
    }
    
    public void put(int key, int value) {
     
        dlistnode dnode = cache.get(key);
        if(dnode == null){
            dlistnode newnode = new dlistnode(key, value);
            cache.put(key, newnode);
            addnodetohead(newnode);
            //插入成功，大小加一
            size  ;
            //超出尺寸，则删除双链表中的最后一个元素结点，并删除该链表元素节点的hashmap中的元素
            if(size > capacity){
                dlistnode finalnode = tail.prev;
                removenode(finalnode);
                //通过链表元素的key找到hashmap中的key并删除
                cache.remove(finalnode.key);
                size--;
            }
        }else{//如果key存在则需要对hashmap的值进行更新,并将双链表节点放到链表头
            // cache.put(key, newnode);
            dnode.value = value;
            removenode(dnode);
            addnodetohead(dnode);
        }
    }
    public void removenode(dlistnode dlistnode) {
        dlistnode.prev.next = dlistnode.next;
        dlistnode.next.prev = dlistnode.prev;
    }
    public void addnodetohead(dlistnode dlistnode){
        dlistnode.next = head.next;
        head.next.prev = dlistnode;
        head.next = dlistnode;
        dlistnode.prev = head;
    }
}