目录

 

1 LinkedHashMap有序

2 LRU机制介绍

3 LinkedHashMap原理

3.1 put方法

3.2 get方法

---

1 LinkedHashMap有序

LinkedHashMap是有序的原因是LinkedHashMap的内部了Entry在继承了HashMap.Node基础上新增了前驱和后继属性。

static class Entry<K,V> extends HashMap.Node<K,V> {     Entry<K,V> before, after;     Entry(int hash, K key, V value, Node<K,V> next) {         super(hash, key, value, next);     } }

LRU就是基于这个特性实现的

2 LRU机制介绍

何为LRU？基Least Recent Used，最近最少访问，通常用于缓存维护。当缓存服务器内存或别的资源不足时，把那些不经常访问的缓存数据给删除掉。 我们看一下构造方法

public LinkedHashMap(int initialCapacity,                      float loadFactor,                      boolean accessOrder) {     super(initialCapacity, loadFactor);     this.accessOrder = accessOrder; }

这里重点关注第三个参数accessOrder，默认false，遍历元素的时候按照插入顺序；如果为true则按照访问顺序。下面简单实现衣蛾LRU缓存

public class LruCache {     private LinkedHashMap<String, String> map;     private int cacheSize;     public LruCache(int cacheSize) {         this.cacheSize = cacheSize;         /**          * 第三个参数accessOrder，默认false，遍历元素的时候按照插入顺序；如果为true则按照访问顺序          */         map = new LinkedHashMap<String, String>(cacheSize, 0.75F, true) {             private static final long serialVersionUID = -6650855993931928707L;             /**              * 当map中的元素大于阈值时移除最老的元素              * @param eldest              * @return              */             @Override             protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {                 boolean result = size() > cacheSize;                 if (result) {                     System.out.println("remove eldest entry:" + eldest);                 }                 return result;             }         };     }     public void put(String k, String v) {         map.put(k, v);     }     public String get(String k) {         return map.get(k);     }     public void print() {         System.out.println(map);     } }

测试代码：

public static void main(String[] args) {     LruCache lruCache = new LruCache(5);     for (int i = 0; i < 5; i ++) {         lruCache.put(i + "", i + "");     }     lruCache.print();     lruCache.put("6", "6");     lruCache.print();     System.out.println("get key 1");     lruCache.get("1");     lruCache.print();     lruCache.put("7", "7");     lruCache.print(); }

输出： {0=0, 1=1, 2=2, 3=3, 4=4} remove eldest entry:0=0 {1=1, 2=2, 3=3, 4=4, 6=6} get key 1 {2=2, 3=3, 4=4, 6=6, 1=1} remove eldest entry:2=2 {3=3, 4=4, 6=6, 1=1, 7=7} 可以看到添加缓存元素6后会把最先添加的缓存元素0给移除掉。 访问缓存元素1后会把1放到末尾。这样就实现了LRU策略缓存

3 LinkedHashMap原理

3.1 put方法

put方法是继承的父类HashMap方法，每次添加元素后会执行模板方法afterNodeInsertion

// put方法evict传的是true void afterNodeInsertion(boolean evict) { // possibly remove eldest     LinkedHashMap.Entry<K,V> first;     if (evict && (first = head) != null && removeEldestEntry(first)) {         // 如果头结点不为空并且需要移除头部元素的时候进行移除         K key = first.key;         removeNode(hash(key), key, null, false, true);     } }

LinkedHashMap中removeEldestEntry方法返回的是false，默认不删除最老的元素，但是我们重写了该方法当容量超过阈值时移除头部元素

3.2 get方法

public V get(Object key) {     Node<K,V> e;     if ((e = getNode(hash(key), key)) == null)         return null;     if (accessOrder)         // 如果按照访问顺序，则访问节点后调整被访问元素的顺旭         afterNodeAccess(e);     return e.value; } // 这里实际上是把被访问元素放到链表尾部，代码比较简单，不做太多注释 void afterNodeAccess(Node<K,V> e) { // move node to last     LinkedHashMap.Entry<K,V> last;     if (accessOrder && (last = tail) != e) {         LinkedHashMap.Entry<K,V> p =             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;         p.after = null;         if (b == null)             head = a;         else             b.after = a;         if (a != null)             a.before = b;         else             last = b;         if (last == null)             head = p;         else {             p.before = last;             last.after = p;         }         tail = p;         ++modCount;     } }

这样就实现了链表头部是最早访问的元素，缓存淘汰的时候优先淘汰头部元素