LinkedHashMap 实现LRU缓存
LinkedHashMap是HashMap的子类,但是内部还有一个双向链表维护键值对的顺序,每个键值对既位于哈希表中,也位于双向链表中。LinkedHashMap支持两种顺序插入顺序 、 访问顺序
插入顺序:先添加的在前面,后添加的在后面。修改操作不影响顺序
访问顺序:所谓访问指的是get/put操作,对一个键执行get/put操作后,其对应的键值对会移动到链表末尾,所以最末尾的是最近访问的,最开始的是最久没有被访问的,这就是访问顺序。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
其中参数accessOrder就是用来指定是否按访问顺序,如果为true,就是访问顺序。
LRU(Least Recently Used): 最近最少使用
1 | public class LRUCache<K, V> extends LinkedHashMap<K, V> { |
在LinkedHashMap添加元素后,会调用removeEldestEntry防范,传递的参数时最久没有被访问的键值对,如果方法返回true,这个最久的键值对就会被删除。LinkedHashMap中的实现总返回false,该子类重写后即可实现对容量的控制。
1 | LRUCache<String,Object> cache = new LRUCache<>(3); |
相比HashMap,LinkedHashMap还实现了三个方法,当且仅当 accessOrder=True 时会被调用到
1 | void afterNodeAccess(Node<K,V> p) { } //访问节点之后调用的方法 |
1 | 在get()方法中调用afterNodeAccess()方法,具体作用是:在对节点进行访问之后,会更新链表,将节点移动到链表的尾部,表示最近被访问过。 |
1 | LinkedHashMap的put()是调用的父类HashMap的put()方法 |
1 | 当LinkedHashMap成功调用removeNode()方法,删除节点之后,会调用本方法 |