手撕LRU缓存——LinkedHashMap简易源码

题���链接：https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked

原理非常简单，一个双端链表配上一个hash表。

首先我们要知道什么是LRU就是最小使用淘汰。怎么淘汰，链表尾部就是最不常用的直接删除，最近使用过的就移动到链表头部。要查找就利用hash表进行映射查找。

代码：

class LRUCache {    //需要定义的双端链表节点    //哈希表    class Node{        int key;        int value;        Node prev;        Node next;        public Node() {}        public Node(int _key,int _value) {            key = _key;            value = _value;        }    }    private Map cache = new HashMap();    private int size;    private int capacity;    private Node head,tail;    public LRUCache(int capacity) {        this.size = 0;        this.capacity = capacity;        head = new Node();        tail = new Node();        head.next = tail;        tail.prev = head;    }        public int get(int key) {        Node node = cache.get(key);        if(node == null)             return -1;        moveToHead(node);        return node.value;    }        public void put(int key, int value) {        //如果存在        if(cache.containsKey(key)){            Node t = cache.get(key);            t.value = value;            moveToHead(t);        }else{            //如果不存在            size++;            if(size>capacity){                cache.remove(tail.prev.key);                //System.out.println(tail.prev.key);                moveTail();                size--;            }            Node node = new Node(key,value);            Node temp = head.next;            head.next = node;            node.prev = head;            temp.prev = node;            node.next = temp;            cache.put(key,node);        }    }    public void moveToHead(Node node){        //本身删除了        Node qian = node.prev;        qian.next = node.next;        node.next.prev = qian;        //再插到头部        Node temp = head.next;        head.next = node;        node.prev = head;        temp.prev = node;        node.next = temp;    }    public void moveTail(){        Node temp = tail.prev.prev;        temp.next = tail;        tail.prev = temp;    }}/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */