solution/0100-0199/0146.Lru Cache/README.md · Xavier1926/leetcode

# [146. LRU 缓存机制](https://leetcode-cn.com/problems/lru-cache)

[English Version](/solution/0100-0199/0146.LRU%20Cache/README_EN.md)

## 题目描述

<div class="title__3Vvk">运用你所掌握的数据结构，设计和实现一个  <a href="https://baike.baidu.com/item/LRU" target="_blank">LRU (最近最少使用) 缓存机制</a> 。</div>

<div class="original__bRMd">
<div>
实现 <code>LRUCache</code> 类：

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

</div>
</div>

进阶：你是否可以在 <code>O(1)</code> 时间复杂度内完成这两种操作？

示例：

<pre>
输入
["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
</pre>

提示：

## 解法

“哈希表 + 双向链表”实现。其中：

- 双向链表按照被使用的顺序存储 kv 键值对，靠近头部的 kv 键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表通过缓存的 key 映射到双向链表中的位置。我们可以在 `O(1)` 时间内定位到缓存的 key 所对应的 value 在链表中的位置。

对于 `get` 操作，判断 key 是否存在哈希表中：

- 若不存在，返回 -1
- 若存在，则 key 对应的节点 node 是最近使用的节点。将该节点移动到双向链表的头部，最后返回该节点的值即可。

对于 `put` 操作，同样先判断 key 是否存在哈希表中：

- 若不存在，则创建一个新的 node 节点，放入哈希表中。然后在双向链表的头部添加该节点。接着判断双向链表节点数是否超过 capacity。若超过，则删除双向链表的尾部节点，以及在哈希表中对应的项。
- 若存在，则更新 node 节点的值，然后该节点移动到双向链表的头部。

双向链表节点（哈希表的 value）的结构如下：

```java
class Node {
	int key;
	int value;
	Node prev;
	Node next;
	Node() {

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

你可能会问，哈希表的 value 为何还要存放 key？

这是因为，双向链表有一个删除尾节点的操作。我们定位到双向链表的尾节点，在链表中删除之后，还要找到该尾节点在哈希表中的位置，因此需要根据 value 中存放的 key，定位到哈希表的数据项，然后将其删除。

### **Python3**

```python
class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:

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

def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_head(node)
        return node.value

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                node = self.remove_tail()
                self.cache.pop(node.key)
                self.size -= 1

def move_to_head(self, node):
        self.remove_node(node)
        self.add_to_head(node)

def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

def add_to_head(self, node):
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        node.prev = self.head

def remove_tail(self):
        node = self.tail.prev
        self.remove_node(node)
        return node

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

### **Java**

```java
class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node() {

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

private Map<Integer, Node> cache;
 private Node head;
 private Node tail;
 private int capacity;
 private int size;

public LRUCache(int capacity) {
 cache = new HashMap<>();
 this.capacity = capacity;
 head = new Node();
 tail = new Node();
 head.next = tail;
 tail.prev = head;
 }

public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);
            cache.put(key, node);
            addToHead(node);
            ++size;
            if (size > capacity) {
                node = removeTail();
                cache.remove(node.key);
                --size;
            }
        }
    }

private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

private void addToHead(Node node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
}

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

### **Rust**

```rust
use std::cell::RefCell;
use std::collections::hash_map::HashMap;
use std::rc::Rc;

struct Node {
 key: i32,
 value: i32,
 prev: Option<Rc<RefCell<Node>>>,
 next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    #[inline]
    fn new(key: i32, value: i32) -> Node {
        Node {
            key,
            value,
            prev: None,
            next: None,
        }
    }
}

struct LRUCache {
 capacity: usize,
 cache: HashMap<i32, Rc<RefCell<Node>>>,
 head: Option<Rc<RefCell<Node>>>,
 tail: Option<Rc<RefCell<Node>>>,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        LRUCache {
            capacity: capacity as usize,
            cache: HashMap::new(),
            head: None,
            tail: None,
        }
    }

fn get(&mut self, key: i32) -> i32 {
        if let Some(node) = self.cache.get(&key) {
            let node = Rc::clone(node);
            self.remove(&node);
            self.push_front(&node);
            let value = node.borrow().value;
            value
        } else {
            -1
        }
    }

fn put(&mut self, key: i32, value: i32) {
        if let Some(node) = self.cache.get(&key) {
            let node = Rc::clone(node);
            node.borrow_mut().value = value;
            self.remove(&node);
            self.push_front(&node);
        } else {
            let node = Rc::new(RefCell::new(Node::new(key, value)));
            self.cache.insert(key, Rc::clone(&node));
            self.push_front(&node);
            if self.cache.len() > self.capacity {
                if let Some(back) = self.pop_back() {
                    self.cache.remove(&back.borrow().key);
                }
            }
        }
    }

fn push_front(&mut self, node: &Rc<RefCell<Node>>) {
 let mut node_borrow_mut = node.borrow_mut();
 if let Some(head) = self.head.take() {
 head.borrow_mut().prev = Some(Rc::clone(node));
 node_borrow_mut.next = Some(head);
 node_borrow_mut.prev = None;
 self.head = Some(Rc::clone(node));
 } else {
 self.head = Some(Rc::clone(node));
 self.tail = Some(Rc::clone(node));
 }
 }

fn remove(&mut self, node: &Rc<RefCell<Node>>) {
 match (node.borrow().prev.as_ref(), node.borrow().next.as_ref()) {
 (None, None) => {
 self.head = None;
 self.tail = None;
 }
 (None, Some(next)) => {
 self.head = Some(Rc::clone(next));
 next.borrow_mut().prev = None;
 }
 (Some(prev), None) => {
 self.tail = Some(Rc::clone(prev));
 prev.borrow_mut().next = None;
 }
 (Some(prev), Some(next)) => {
 next.borrow_mut().prev = Some(Rc::clone(prev));
 prev.borrow_mut().next = Some(Rc::clone(next));
 }
 }
 }

fn pop_back(&mut self) -> Option<Rc<RefCell<Node>>> {
 if let Some(tail) = self.tail.take() {
 match tail.borrow().prev.as_ref() {
 Some(prev) => {
 prev.borrow_mut().next = None;
 self.tail = Some(Rc::clone(prev));
 }
 None => {
 self.head = None;
 self.tail = None;
 }
 }
 Some(tail)
 } else {
 None
 }
 }
}
```

### **...**

```

Xavier1926/leetcode

About

Releases

Contributors

Activities