> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/niu-ke-0093-kun-nan-she-ji-lru-huan-cun-jie-gou.md).

# 设计LRU缓存结构

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%B0%E9%9A%BE\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#困难) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E8%AE%BE%E8%AE%A1\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#设计) [![](https://img.shields.io/static/v1?label=\&message=%E7%BB%8F%E5%85%B8\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#经典)

> [设计LRU缓存结构\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84)

**问题简述**

```
设计LRU(最近最少使用)缓存结构。
```

**思路**

* 提示：
  * 核心操作：不管什么操作，只要 key 之前存在，都要移除然后重新加入缓存；
  * Python3.6 之后的 dict 就是有序的，所以不需要额外使用其他数据结构；
  * 可以通过 `next(iter(dict.keys()))` 快速获取最早未使用的 key；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:

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

    def get(self, key: int) -> int:
        ret = self.buf.get(key, -1)
        if key in self.buf:
            self.buf.pop(key)
            self.buf[key] = ret
        return ret

    def set(self, key: int, value: int) -> None:
        # 这一步很容易忽略，不论 key 是否存在，都应该先 pop，这样重新加入时才可以更新到队尾
        if key in self.buf:
            self.buf.pop(key)
        elif len(self.buf) >= self.capacity:  # key not in self.buf
            tmp = next(iter(self.buf.keys()))
            self.buf.pop(tmp)
        self.buf[key] = value
```

</details>