LRU

Leetcode 题目

https://leetcode-cn.com/problems/lru-cache/submissions/

方法一 双端链表+hashmap、

get和put的时间复杂度都是o(1) 所以使用hashmap 这种数据结构来做
为了(1）的时间复杂度就获取头节点和尾部节点， 以及增加和删除方便，所以使用了双端链表， 删除的时候就是该节点的上一个指向了该节点的下一个。所以使用双端链表可以方便的知道该节点的上一个和下一个。

/**
 * 最近最少使用   并没有统计次数 只要用了就放到前面  如何统计最热 就是使用次数最多的？
 */
public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }
    /*
    永远添加到头部
     双向队列如果插入一个元素要记得赋值俩次
     */
    private void addNode(DLinkedNode newNode) {
        DLinkedNode oldHead = head.next;
        head.next = newNode;
        newNode.prev = head;
        oldHead.prev = newNode;
        newNode.next = oldHead;
    }
    /**
     *
     * @param node
     * 删除节点永远是要去删除队尾的节点
     */
    private void removeNode(DLinkedNode node){
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    private HashMap<Integer, DLinkedNode> cache =
            new HashMap<Integer, DLinkedNode>();
    private int capacity;
    private DLinkedNode head, tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLinkedNode();
        // head.prev = null;
        tail = new DLinkedNode();
        // tail.next = null;
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        //因为这就算使用了，所以要添加到头部。可以拆分成方法，把下面俩个包含进去
        removeNode(node);
        addNode(node);
        return node.value;
    }
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        //如果取出的是空节点 说明key不存在，如果存在则把该节点移动到头部
        if(node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            //在map中保存key
            cache.put(key, newNode);
            addNode(newNode);
            //如果节点超出个数 那么删除尾部节点
            if(cache.size() > capacity) {
                // pop the tail
                cache.remove(tail.prev.key);
                removeNode(tail.prev);
            }
        } else {
            // 更新数据的方式就是先删后增
            removeNode(node);
            node.value = value;
            addNode(node);
        }
    }
}

方法2、继承LinkedHashMap 都是操作父类。

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

后记

如何统计最热 就是使用次数最多的？LFU？LRU-k？

参考

https://blog.csdn.net/zhanglong_4444/article/details/88344953
https://leetcode-cn.com/problems/lru-cache/solution/lru-huan-cun-ji-zhi-by-leetcode/