LRU - 基础数据结构算法

本文主要讲述计算机的LRU算法 (Least Recent Use) 的Java 实现

LRU 算法描述

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

LRU算法为缓存的一种淘汰机制。当缓存达到最大容量的时候，计算机会将最远使用的缓存清理掉，为新加入的缓存提供位置。

本题需要我们实现LRUCache类，并且添加查找删除都应该使用o(1)的时间复杂度

使用示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

结题思路：

• 首先我们需要建立缓存的队列
• 查找，插入、更新、删除都需要更新缓存队列，并且是o（1）的时间复杂度。这意味着我们不能遍历缓存队列，而需要直接拿到缓存的index。
• 思路是建立双向链表，而且需要使用HashMap存储每个结构体的地址，这样在CRUD操作是，我们不需要遍历即可找到他的地址

对于每个node

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

对于DoubleList

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 addLast(Node x) {
        x.prev = tail.prev;
        tail.prev.next = x;

        x.next = tail;
        tail.prev = x;

        size++;
    }

    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;

        size--;
    }

    public Node removeFirst() {
        if (head.next == tail) return null;

        Node first = head.next;
        remove(first);
        return first;
    }

    public int getSize() {
        return size;
    }
}

封装到LRUCache

public class LRUCache{
    private int capacity;
    private HashMap<Integer, Node> map;
    private DoubleList cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    private void makeRecently(int key) {
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }

    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        cache.addLast(x);
        map.put(key, x);
    }

    private void deleteKey(int key) {
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }

    private void removeLeastRecently() {
        Node deletedNode = cache.removeFirst();
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }



    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        makeRecently(key);
        return map.get(key).val;
    }



    public void put(int key, int value) {

        if (map.containsKey(key)) {
            deleteKey(key);
        } else {
            if (cache.getSize() == capacity) {
                removeLeastRecently();
            }
        }
        addRecently(key, value);
    }


}