LRU缓存
由于内存是有限的,因此缓存总有满的时候,那么当缓存满了的时候,这时候又有新的数据需要加入到缓存中时,我们该怎么办了?没什么别的办法,只有从缓存中删除旧数据为新数据腾出空间,那么究竟删除原来缓存的哪些数据了?这就涉及到缓存的替换策略,LRU就是一种缓存策略。
LRU,Least Recently Used的简写,翻译过来就是“最近最少使用”, 其淘汰旧数据的策略是,距离当前最久没有被访问过的数据应该被淘汰。
LRU原理
假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,LRU就是这样工作的。
这样设计可能问题很多,内存按照访问时间进行了排序,会有大量的内存拷贝操作,所以性能肯定是不能接受的。
那么如何设计一个LRU缓存,使得放入和移除都是 O(1) 的,我们需要把访问次序维护起来,但是不能通过内存中的真实排序来反应,有一种方案就是使用双向链表。
HashMap+双向链表
基于 HashMap 和 双向链表实现 LRU的整体的设计思路是,可以使用 HashMap 存储 key,这样可以做到 save 和 get key的时间都是 O(1),而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点,如图所示:
LRU 存储是基于双向链表实现的,下面的图演示了它的原理。其中 head 代表双向链表的表头,tail 代表尾部。首先预先设置 LRU 的容量,如果存储满了,可以通过 O(1) 的时间淘汰掉双向链表的尾部,每次新增和访问数据,都可以通过 O(1)的效率把新的节点增加到对头,或者把已经存在的节点移动到队头。
代码实现
1 | // 双项链表 |