Bytebuffer 性能（bytebuffer remaining）



文章目录

• 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大神

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/hd-xnyh/20937.html