LeetCode的LRU缓存实现

  • 开发
  • 36

LRU是什么意思

LRU是操作系统底层的一个页面置换算法，当空间不够需要换出最长时间没有使用的页面，在本题中的意思就是当到达容量上限的时候要换出最长时间没有被访问过的节点。

如何实现

LRU的实现可以使用链表的方式，参照MySQL的实现，将热数据每次都放到链表头，删除链表尾的冷数据。

题目需要get()和put()方法都是O(1)的事件复杂度，但是链表遍历需要O(n)的时间复杂度，无法满足题目要求，可以想到数组下标索引或者HashMap辅助我们访问，本题如果用数组还需要多写一步hash()来确认key存放的位置，所以我们使用HashMap。

通过HashMap我们可以快速找到节点，也就满足了get()的O(1)，但是对于put()的O(1)，考虑到我们需要删除节点，单链表显然无法满足，因为单链表需要O(n)找到前驱节点，所以我们修改为双链表。

最终的结构就是HashMap + 双链表。

阅读全部

相关推荐

  1. LeetCode的LRU缓存实现

    2024-03-23 12:38:03       37 阅读

  9. Leetcode 146. LRU 缓存

    2024-03-23 12:38:03       22 阅读

  10. C# 实现Lru缓存

    2024-03-23 12:38:03       57 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-23 12:38:03       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-23 12:38:03       100 阅读

  9. 在Django里面运行非项目文件

    2024-03-23 12:38:03       82 阅读

  19. Python语言-面向对象

    2024-03-23 12:38:03       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-03-23 12:38:03       85 阅读

热门阅读

  1. 69、FIFO缓存发送数据（先入先出）

    2024-03-23 12:38:03       44 阅读

  5. 路径优化算法 | 基于蚁群的城市路径优化算法应用及其Matlab实现

    2024-03-23 12:38:03       37 阅读

  7. ubuntu生成 设置 core文件

    2024-03-23 12:38:03       38 阅读

  8. Vue 常见面试题(一)

    2024-03-23 12:38:03       39 阅读

  10. 0x01_实验课leetcode

    2024-03-23 12:38:03       41 阅读

  11. [leetcode] 21. 合并两个有序链表

    2024-03-23 12:38:03       45 阅读

  12. 数学系的数字信号处理：傅立叶变换

    2024-03-23 12:38:03       39 阅读

  15. android gdb 调试

    2024-03-23 12:38:03       47 阅读

  20. Android_NDK调试

    2024-03-23 12:38:03       42 阅读

  24. 简单函数_学分绩点

    2024-03-23 12:38:03       41 阅读

  26. LeetCode232：用栈实现队列

    2024-03-23 12:38:03       36 阅读

  29. 复试专业前沿问题问答合集9——密码学

    2024-03-23 12:38:03       38 阅读