你所熟知的 LRU(最近最少使用)

关于LRU这个名词在很多地方或听说,或使用,接下来看下lru缓存回收的实现

1、大体的想法

    a、查询出最近最晚使用的项

    b、给最近的使用的项做标记

通过使用链表就可以完成这两个操作,关于最近最少使用的项只需要返回链表的尾部;标记最近使用的项,只需要将该项移除并放置到头部,那么难点就出现 你如何能够快速在链表定位对应的该项?

这时候多半很多人想到使用哈希表,它可以在常规的时间内容,定位到某一个对象,采用 key关联存放链表节点的哈希表,这样我们就可以根据key执行hash获取到对应的链表节点对应的哈希表,这样就可以快点找到最近使用的节点(也就是实际需要的列表项),同样可以判断节点的存在与否。

那么这种结构是我们自己构造还是采用现有的api;熟悉java 的人都知道,LinkedHashMap是完全满足我们的需求,这样只需在继承LinkedHashMap的基础进行微调即可满足我们所需的LRU回收。

你可能感兴趣的