当前位置: 首页 > 图灵资讯 > java面试题> 美团Java面试题-LRU 是什么?如何实现?

美团Java面试题-LRU 是什么?如何实现?

来源:图灵教育
时间:2023-11-08 09:53:32

  问:LRU 是什么?如何实现?

  答:LRU(Least Recently Used)是一种常见的缓存淘汰策略,它的基本思想是根据数据的访问时间来淘汰最近最少使用的数据。当缓存满了的时候,会将最近最少访问的数据从缓存中删除,以腾出空间给新的数据。

  在实现上,可以通过维护一个数据结构来记录数据的访问顺序,常用的数据结构是双向链表(Doubly Linked List)。链表的头部表示最近访问的数据,尾部表示最久未访问的数据。每次进行缓存访问时,如果数据在缓存中存在,则将其移到链表头部,表示最近访问过;如果不存在,则在链表头部插入新的数据。当缓存达到容量上限时,将链表尾部的数据删除即可。