146. LRU 缓存机制

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 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

思路

应用JavaAPI中的哈希链表（LinkedHashMap）

代码

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)){
            cache.put(key,value);
            makeRecently(key);
            return;
        }
        if(cache.size() >= this.cap){
            // 移除最久未使用的key--链表头部
            int oldKey = cache.keySet().iterator().next();
            cache.remove(oldKey);
        }
        cache.put(key,value);
    }

    private void makeRecently(int key){
        int value = cache.get(key);
        cache.remove(key);
        cache.put(key,value);
    }
}

复杂度分析

时间复杂度：O(1)，其中 N 为数组长度。
空间复杂度：O(N)

class LRUCache {

    class ListNode {
        int key;
        int val;
        ListNode next;
        ListNode pre;
    }

    private int capacity;

    private int count = 0;

    private Map<Integer, ListNode> map;

    private ListNode head, tail;

    public LRUCache(int capacity) {
        map = new HashMap<>();
        head = new ListNode();
        tail = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)) {
            System.out.println(-1);
            return -1;
        }
        ListNode node = map.get(key);
        moveToTail(node);
        System.out.println(map.get(key).val);
        return map.get(key).val;
    }

    private void moveToTail(ListNode node) {
        if(node == tail) {
            return;
        }
        node.pre.next = node.next;
        if(node.next != null) {
            node.next.pre = node.pre;
        }
        node.pre = tail;
        node.next = null;
        tail.next = node;
        tail = node;
    }

    public void put(int key, int value) {
        ListNode node = map.get(key);
        if(node == null) {
            node = new ListNode();
            node.key = key;
            node.val = value;
            map.put(key, node);
            tail.next = node;
            node.pre = tail;
            tail = node;
            count += 1;
            if(count > capacity) {
                ListNode remove = head.next;
                map.remove(head.next.key);
                head.next = remove.next;
                if(remove.next != null) {
                    remove.next.pre = head;
                }
                count -= 1;
            }
        }else {
            node.val =value;
            moveToTail(node);
            return;
        }

    }
}

class LRUCache {
    private int cap;
    private Map<Integer,Integer> map=new LinkedHashMap<>();

    public LRUCache(int capacity) {
    this.cap=capacity;
    }

    public int get(int key) {
        if(map.keySet().contains(key)){
            int value=map.get(key);
            map.remove(key);
            map.put(key,value);
            return value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if(map.keySet().contains(key)){
            map.remove(key);
        }else if(map.size()==cap){
            Iterator<Map.Entry<Integer,Integer>> iterator=map.entrySet().iterator();
            iterator.next();
            iterator.remove();
        }
        map.put(key,value);
    }
}

思路

LRU 采用哈希表 + 双向链表实现。

LRU 中保存哈希表用来实现 get 的 O(1) 时间复杂度。保存 capacity 用于判断是否达到容量。保存链表的头节点和尾节点用于方便添加和删除。

哈希表 key 为输入的 key 值，value 为链表中的节点。

链表节点储存输入的 key 值和输入的 value 以及前后两个指针。链表储存 key 值的作用是用于当缓存达到最大值后，移除链表尾节点时，同时获得需要移除的哈希表中的 key 值。

代码

class LRUCache {

    private Map<Integer, Node> index;
    private int capacity;

    private Node first;

    private Node last;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.index = new HashMap<Integer, Node>(capacity);
    }

    public int get(int key) {
        if (index.containsKey(key)) {
            Node node = index.get(key);
            if(first != node) {
                if (last == node) {
                    last = node.pre;
                }
                else {
                    node.next.pre = node.pre;
                }
                node.pre.next = node.next;
                first.pre = node;
                node.next = first;
                node.pre = null;
                first = node;
            }
            return node.value;
        }
        else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if(index.isEmpty()){
            Node node = new Node(key,value);
            first = node;
            last = node;
            index.put(key, node);
        }
        else {
            if(index.containsKey(key)){
                Node node = index.get(key);
                if(node != first) {
                    node.pre.next = node.next;
                    if (node == last) {
                        last = node.pre;
                    }
                    else {
                        node.next.pre = node.pre;
                    }
                    first.pre = node;
                    node.next = first;
                    first = node;
                }
                node.value = value;
            }
            else {
                if (index.size() == capacity) {
                    int lastKey = last.key;
                    if (last != first) {
                        last.pre.next = null;
                        last = last.pre;
                        index.remove(lastKey);
                    }
                    else {
                        index.remove(lastKey);
                        Node node = new Node(key,value);
                        first = node;
                        last = node;
                        index.put(key, node);
                        return;
                    }
                }
                Node node = new Node(key,value);
                first.pre = node;
                node.next = first;
                first = node;
                index.put(key, node);
            }
        }
    }

    private class Node {
        private Node pre;
        private Node next;
        private int key;
        private int value;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
}

/**
 * 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);
 */

复杂度分析

时间复杂度：O(1)

思路

将LRU翻译成大白话就是：当不得不淘汰某些数据时（通常是容量已满），选择最久未被使用的数据进行淘汰。题目让我们实现一个容量固定的LRUCache。如果插入数据时，发现容器已满时，则先按照LRU规则淘汰一个数据，再将新数据插入，其中「插入」和「查询」都算作一次“使用”。

可以通过下面来理解，假设我们有容量为2的LRUCache和测试键值对[1-1，2-2，3-3]，将其按照顺序进行插入&查询；

插入1-1，此时最新的使用数据为1-1
插入2-2，此时最新使用数据为2-2
查询1-1，此时最新使用数据为1-1
插入3-3，由于容器已经达到容量，需要先淘汰已有的数据才能插入，这是会淘汰2-2，3-3成为最新使用的数据

键值对存储方面，我们可以使用「哈希表」来确保插入和查询的复杂度为O(1)。

另外我们还需要额外维护一个「使用顺序」序列。

我们期望当「新数据被插入」或「发生键值查询」时，能够将当前键值对放到序列头部，这样当触发LRU淘汰时，只需要从序列尾部进行数据删除即可。

期望在O(1)复杂度内调整某个节点在序列中的位置，很自然想到双向链表。

双向链表

具体的，我们使用哈希表来存储「键值对」，键值对的键作为哈希表的Key,而哈希表的Value则使用我们自己封装的Node类，Node同时作为双向链表的节点。

插入：检查当前键值对是否已经存在于哈希表：
- 如果存在，则更新键值对，并将当前键值对所对应的Node节点调整到链表头部(refresh操作)
- 如果不存在，则检查哈希表容量是否已经到达容量：
- 没达到容量：插入哈希表，并将当前键值对所对应的Node节点调整到链表头部（refresh操作）
- 已到达容量：先从链表尾部找到待删除元素进行删除（delete操作），然后再插入哈希表，并将当前键值对所对应的Node节点调整到链表头部（refresh操作）
查询：如果没在哈希表中找到该Key，直接返回-1；如果存在该Key，则将对应的值返回，并将当前键值对所对应的Node节点调整到链表头部（refresh操作）

一些细节：

为了减少双向链表左右节点的「判空」操作，我们预先建立两个「哨兵」节点head和tail。


public class LRUCache {
class Node {
    int key, value;
    Node pre, post;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

int max;
Node head, tail;
Map<Integer, Node> map;

public LRUCache(int capacity) {
     head = new Node(-1, -1);
     tail = new Node(-1, -1);
    head.post = tail;
    tail.pre = head;
    this.max = capacity;
    map = new HashMap<>();
}

public int get(int key) {
    if (map.containsKey(key)) {
        Node node = map.get(key);
        refresh(node);
        return node.value;
    }
    return -1;
}

/*
检查当前键是否已经存在于哈希表
如果存在，则更新键值对，并将当前键值对所对应的Node节点调整到链表头部（refresh）操作
如果不存在，则检查哈希表是否到达容量：
    没有到达容量，插入哈希表并将当前键所对应的Node调整到链表头部（refresh）操作
    达到容量，先从链表尾部找到待删除的元素进行删除（delete）操作，然后再插入哈希表，并将
      当前键值所对应的Node调整到链表头部（refresh）操作。

* */
public void put(int key, int value) {
    Node node;
    if (map.containsKey(key)) {
        node = map.get(key);
        node.value = value;
    } else {
        if (map.size() == max) {
            Node del = tail.pre;
            map.remove(del.key);
            delete(del);
        }
        node = new Node(key, value);
        map.put(key, node);
    }
    refresh(node);

}
/*
refresh操作分为两步
1.先将当前节点从双向链表中删除(如果该节点本身存在于双向链表中的话)
2. 将当前节点添加到双向链表的头部

*/ private void refresh(Node node) { delete(node); node.post = head.post; node.pre = head; head.post.pre = node; head.post = node;

}

private void delete(Node node) { if (node.pre != null && node.post != null) { node.pre.post = node.post; node.post.pre = node.pre; } } }
时间复杂度：各操作均为 O(1)
空间复杂度：O(n)

思路

LRU( Least Recently Used ):最近最少使用,主要是通过哈希表辅以双向链表实现

双向链表按照被使用的顺序存储这些键值对,靠近尾部的键值对是最近使用的,而靠近头部的键值对是最久未使用的
哈希表及为普通的哈希映射,通过缓存数据的键映射到期双向链表中的位置

代码

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

        self.lookup = {}
        self.max_len = capacity

    def get(self, key: int) -> int:
        if key not in self.lookup:
            return -1
        node = self.lookup[key]
        self.remove(node)
        self.add(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.lookup:
            self.remove(self.lookup[key])
        if len(self.lookup) == self.max_len:
            self.remove(self.head.next)
        self.add(Node(key, value))

    def remove(self, node):
        del self.lookup[node.key]
        node.prev.next = node.next
        node.next.prev = node.prev

    def add(self, node):
        self.lookup[node.key] = node
        pre_tail = self.tail.prev
        node.next = self.tail
        node.prev = pre_tail
        self.tail.prev = node
        pre_tail.next = node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

复杂度

时间复杂度:put和get都是O(1)

空间复杂度:O(capacity)

class DBList {
    public:
        DBList* next;
        DBList* prev;
        int key;
        int value;
        DBList(int key,int val){
            this->next = nullptr;
            this->prev = nullptr;
            this->value = val;
        }
        DBList(DBList* pre,int key,int val){
            this->next = nullptr;
            this->prev = pre;
            this->value = val;
            prev->next = this;
        }
};
class LRUCache {
public:
    int cap = 0;
    DBList* head;
    DBList* end;
    unordered_map<int,DBList*> m;
    LRUCache(int capacity) {
        this->cap = capacity;
        this->head = new DBList(-1,-1);
        this->end = new DBList(this->head,-1,-1);
    }

    int get(int key) {
        auto it = m.find(key);
        if(it!=m.end()){
            auto node = it->second;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            node->next = this->head->next;
            node->prev = this->head;
            this->head->next->prev = node;
            this->head->next = node;
            return node->value;
        }else return -1;
    }

    void put(int key, int value) {
        auto it = m.find(key);
        if(it!=m.end()){
            it->second->value = value;
            auto node = it->second;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            node->next = this->head->next;
            node->prev = this->head;
            this->head->next->prev = node;
            this->head->next = node;
        }else{
            DBList* tmp = new DBList(key,value);
            if(m.size()>=cap){
                m.erace(this->end->prev->key);
                this->end->prev = this->end->prev->prev;
                this->end->prev->prev->next=this->end;
            }
            m[key] = tmp;
            tmp->next = this->head->next;
            tmp->prev = this->head;
            this->head->next = tmp;
            tmp->next->prev = tmp;
        }
    }
};

/**
 * 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);
 */

from collections import OrderedDict

class LRUCache(OrderedDict):

    def __init__(self, capacity: int):
        self.capacity = capacity 

    def get(self, key: int) -> int:
        if key not in self:
            return -1

        self.move_to_end(key)
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)

# time complexity O(1)
# space complexity O(capacity)

Time: $O(1)$
Space: $O(N)$

class DLinkedListNode {
  key: number;
  value: number;
  prev: DLinkedListNode | null;
  next: DLinkedListNode | null;

  constructor(
    key: number,
    value: number,
    prev: DLinkedListNode | null = null,
    next: DLinkedListNode | null = null,
  ) {
    this.key = key;
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}

class DLinkedList {
  dummy_head_ = new DLinkedListNode(-1, -1);
  dummy_tail_ = new DLinkedListNode(-1, -1);

  constructor() {
    this.dummy_head_.next = this.dummy_tail_;
    this.dummy_tail_.prev = this.dummy_head_;
  }

  // Adds the link to the head of the list.
  stack(node: DLinkedListNode): void {
    this.addAfter(node, this.dummy_head_);
  }

  // Adds the link to the tail of the list.
  queue(node: DLinkedListNode): void {
    this.addBefore(node, this.dummy_tail_);
  }

  // Adds the link to a list after another specified link.
  addAfter(node: DLinkedListNode, target: DLinkedListNode): void {
    const next = target.next;
    target.next = node;
    node.next = next;
    if (next) next.prev = node;
    node.prev = target;
  }

  // Adds the link to a list before another specified link.
  addBefore(node: DLinkedListNode, target: DLinkedListNode): void {
    const prev = target.prev;
    if (prev) prev.next = node;
    node.next = target;
    target.prev = node;
    node.prev = prev;
  }

  // Removes and returns the link at the head of the list.
  pop(): DLinkedListNode | null {
    if (!this.dummy_head_.next) return null;
    return this.remove(this.dummy_head_.next);
  }

  // Removes and returns the link at the tail of the list.
  popTail(): DLinkedListNode | null {
    if (!this.dummy_tail_.prev) return null;
    return this.remove(this.dummy_tail_.prev);
  }

  // Remove a specified link from the list.
  remove(target: DLinkedListNode): DLinkedListNode | null {
    const prev = target.prev;
    const next = target.next;
    if (prev) prev.next = next;
    if (next) next.prev = prev;
    target.prev = target.next = null;
    return target;
  }

  // Returns the link at the head of the list without removing it.
  peek(): DLinkedListNode | null {
    return this.dummy_head_.next;
  }

  // Returns the link at the tail of the list without removing it.
  peekTail(): DLinkedListNode | null {
    return this.dummy_tail_.prev;
  }

  stringify(): string {
    const list: Array<[number, number]> = [];

    let p = this.dummy_head_.next;

    while (p && p != this.dummy_tail_) {
      list.push([p.key, p.value]);
      p = p.next;
    }
    return JSON.stringify(list);
  }
}

class LRUCache {
  dLinkedList = new DLinkedList();
  key2ValueNodeMap_: { [index: number]: DLinkedListNode } = Object.create(null);
  capacity_: number;
  stored_: number = 0;

  constructor(capacity: number) {
    this.capacity_ = capacity;
  }

  get(key: number): number {
    if (key in this.key2ValueNodeMap_) {
      return this.refreshCache_(key);
    }
    return -1;
  }

  put(key: number, value: number): void {
    if (key in this.key2ValueNodeMap_) {
      this.refreshCache_(key, value);
      return;
    }

    if (this.stored_ === this.capacity_) {
      const removedNode = this.dLinkedList.popTail();
      if (removedNode) delete this.key2ValueNodeMap_[removedNode.key];
      this.stored_--;
    }

    const valueNode = new DLinkedListNode(key, value);
    this.dLinkedList.stack(valueNode);
    this.key2ValueNodeMap_[key] = valueNode;

    this.stored_++;
  }

  refreshCache_(key: number, value?: number): number {
    const updateNode = this.key2ValueNodeMap_[key];
    if (value !== undefined) updateNode.value = value;
    this.dLinkedList.remove(updateNode);
    this.dLinkedList.stack(updateNode);
    return updateNode.value;
  }
}

leetcode-pp / 91alg-10-daily-check

【Day 12 】2023-02-25 - 146. LRU 缓存机制 #15

146. LRU 缓存机制

入选理由

题目地址

前置知识

题目描述

思路

代码

思路

代码

思路

思路

代码

复杂度