文章目录
- LRU缓存机制(lru-cache)
- java模板
- 实现
- 操作图
- 内部结构图
- 伪代码模板与思路
- 具体代码
- 小总结
- 参考资料
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
需要实现构造函数，get方法，put方法。
- 由于题目的时间复杂度要求 O(1)O(1)，空间肯定不能省，存取数据时间性能最好的就是哈希表，因此底层的数据结构一定是一个哈希表；
- 根据题目意思，访问某个数据，时间优先级得提前，还有删除末尾结点的需求，这样的数据结构得在头尾访问数据最快，这种数据结构是「双向链表」；
- 「链表」结点需要记录：1、value，2、key（在哈希表里删除的时候用得上），3、前驱结点引用，4、后继结点引用。
思路来自liweiwei1419大神，感谢。
- 新数据插入到链表头部
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
- 当链表满的时候，将链表尾部的数据丢弃
LRU Cache具备的操作：
- put(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
- get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。
LRU缓存机制，是一个哈希表+双向链表的实现，不管是获取节点，还是把节点放进LRU缓存，均须考虑对哈希表和双向链表的操作。
LRU缓存机制(lru-cache)LRU和LFU的区别146. LRU缓存机制liweiwei1419大神
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/162564.html