如何设计一个带有过期时间的LRU缓存
2022-01-27
From 程序之心
By 丁仪
LRU 是 Least Recently Used 的简称，LRU 算法的原理是当缓存空间满的时候首先失效最长时间没有被访问的数据。
使用数组实现 LRU
技术方案是使用数组存储数据，给每个数据项标记一个访问时间，每次插入新数据的时候，先把数组中的时间戳自增，并将新数据项的时间戳设置为 0 插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
使用链表实现 LRU
技术方案是使用链表存储数据，每次新插入数据的时候将新数据插到链表的头部。每次访问链表中的数据项的时候，将被访问的数据项移动到链表头部。当链表空间已满时，将链表尾部的数据项淘汰。
使用 LinkedHashMap 实现 LRU
LinkedHashMap 能够像 map 一样操作，同时确保元素的顺序与插入顺序保持一致。而且 LinkedHashMap 提供了 removeEldestEntry 方法用于移除最近被访问最少的元素，不过默认实现是空实现直接返回 FALSE，需要重写此方法。
过期时间实现
维护一个线程
惰性删除
本文来源：程序之心，转载请注明出处！
君子曰：学不可以已。
《计算机科学导论（原书第4版）》
本书是国际知名的高等学校计算机科学及相关专业基础课教材，也是非常受欢迎的计算机入门读物。该教材是一本百科全书式的计算机专业入门指南，涉及计算机科学的方方面面。虽然读者对象是计算机专业的学生，但这本书深入浅出、引人入胜，勾画出了计算机科学体系的框架，可以为有志于IT行业的学生奠定计算机科学知识的基础，架设进一步深入专业理论学习的桥梁。
发表感想
浙公网安备 33011002016107号