LRU 缓存机制

Wu_Candy

发布于 2022-07-04 21:14:29

5610

发布于 2022-07-04 21:14:29

这是无量测试之道的第222篇原创

因为希望是O(1)的时间复杂度,所以很容易想到需要使用哈希表。那么接下来，就直接讲实现思路了。 ??LRUCache 的常见实现方式是：哈希表+双向链表。那为什么不是哈希表+数组了。因为数组的查找和替换是O(N)级别的，所以需要使用双向链表。

思路：

说明：

map用来作为存储容器，key是传进来的Int值，value是Node节点；即map[int] = node。
Node节点信息包含 {keyvalueprev：Nodenext：Node

LRUCache类包含:map, 以及first , last2 个虚拟的节点 图中的first节点和last的节点都是虚节点，不存储任何值，只是为了维持双向链表的完整性。

完成这个LRUCache的核心思路是：在存和取的时候更新节点的位置。

取如果没有取到值，就直接返回-1 如果取到值了，就需要更新这个节点的位置
- 我们需要将它更新到first节点的后面。具体的执行步骤有以下2步
- 删除该结点,【也就是第5个节点】
- 把该结点添加到first节点的后面
存存的时候，先去根据key获取该结点信息

如果该节点存在，执行以下3步

将其value的值更新一下
删除该结点
并且将该节点添加到first节点的后面

如果该节点不存在

判断是否已经达到最大容量

如果不是，就将该结点添加到first节点后面
如果是，就将最后一个节点【last的prev节点】删掉，然后将新节点添加到fisrt节点的后面

代码如下：swift版本和java版本

class LRUCache { //【swift版本】
    private var map = [Int : Node]()
    private var capacity = 0
    private let first = Node(0, 0)
    private let last = Node(0, 0)
    
    init(_ capacity: Int) {
        self.capacity = capacity
        // 初始化指向
        first.next = last
        last.prev = first
    }
    
    func get(_ key: Int) -> Int {
        guard let node = map[key] else { return -1 }
        // 如果取到值了
        //1.先将该结点删除掉,但是map不删
        removeNode(node: node)
        //2.就将之插入到first节点的后面
        insertToFirstBehind(node: node)
        return node.value
    }
    
    func put(_ key: Int, _ value: Int) {
        
        guard let node = map[key] else {
            // 添加一对新的key-value
            if map.count == capacity {
                // 淘汰最近最少使用的 即删掉last节点前的那个节点，并且map也删
                let needDeleteNode = map.removeValue(forKey: last.prev!.key)!
                removeNode(node: needDeleteNode)
            }
            // 然后添加
            let node = Node(key, value)
            map[key] = node
            insertToFirstBehind(node: node)
            
            
            return
        }
        // 值不为空就更新下值
        node.value = value
        removeNode(node: node)
        insertToFirstBehind(node: node)
    }
    
    private func removeNode(node: Node) {
        node.next?.prev = node.prev
        node.prev?.next = node.next
    }
    
    private func insertToFirstBehind(node: Node) {
        // node 和 first.next
        first.next?.prev = node
        node.next = first.next
        //node 和 first
        first.next = node
        node.prev = first
    }
    
    class Node {
        public let key: Int
        public var value : Int
        public var prev: Node?
        public var next: Node?
        init(_ key: Int, _ value: Int) {
            self.key = key
            self.value = value
        }
    }
}

public class LRUCache { //【java版本】
    private Map<Integer, Node> map;
    private int capacity;
    // 虚拟头结点
    private Node first;
    // 虚拟尾结点
    private Node last;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        first = new Node();
        last = new Node();
        first.next = last;
        last.prev = first;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;

        removeNode(node);
        addAfterFirst(node);

        return node.value;
    }

    /**
     * @param node 将node节点插入到first节点的后面
     */
    private void addAfterFirst(Node node) {
        // node与first.next
        node.next = first.next;
        first.next.prev = node;

        // node与first
        first.next = node;
        node.prev = first;
    }

    /**
     * @param node 从双向链表中删除node节点
     */
    private void removeNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            removeNode(node);
        } else { // 添加一对新的key-value
            if (map.size() == capacity) {
                // 淘汰最近最少使用的node\
                removeNode(map.remove(last.prev.key));
//                map.remove(last.prev.key);
//                removeNode(last.prev);
            }
            map.put(key, node = new Node(key, value));
        }
        addAfterFirst(node);
    }

    private static class Node {
        public int key;
        public int value;
        public Node prev;
        public Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public Node() {}
    }
}