LinkedHashMap源码分析以及LRU的应用

LinkedHashMap源码分析以及LRU的应用

LinkedHashMap简介

LinkedHashMap我们都知道是在HashMap的基础上，保证了元素添加时的顺序；除此之外，它还支持LRU可以当做缓存中心使用

源码分析目的

• 分析保持元素有序性是如何实现的

• LRU是如何实现的

源码分析

有序性的实现

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{transient LinkedHashMap.Entry<K,V> head;transient LinkedHashMap.Entry<K,V> tail;final boolean accessOrder;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);}}Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {}void afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node<K,V> p) { }
}

LinkedHashMap继承自HashMap，并主要重写了HashMap中四个方法，分别是newNode、afterNodeAccess、afterNodeInsertion、afterNodeRemoval,这几个方法分别会在HashMap创建元素、访问元素、添加元素、删除元素之后回调；LinkedHashMap主要通过这几个方法，构建成双向链表将元素连接起来，从而实现顺序访问的目的。

• 变量head和tail分别指向第一个元素和最后一个元素

• 添加的元素会包装成Entry对象，Entry继承自HashMap.Node，在此基础上增加before和after 变量用于指向当前元素的前后两个元素形成链式结构

• accessOrder：true表示对元素根据LRU来排序，也就是最近访问过的放链表尾部，最后访问过的放链表头部，默认为false

添加元素

在LinkedHashMap中并没有重写HashMap的put方法，根据HashMap的put方法源码可以知道当添加一个元素时会调用newNode方法去创建一个Node对象，接着会调用afterNodeInsertion方法，我们先来看看LinkedHashMap是如何重写这两个方法的：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p =new LinkedHashMap.Entry<K,V>(hash, key, value, e);linkNodeLast(p);return p;
}private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}
}

• 在创建元素节点时，会先创建一个LinkedHashMap.Entry节点，然后将该元素添加链表的尾部

void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
}

• 元素添加后，会调用afterNodeInsertion方法，LinkedHashMap重写该方法后，根据removeEldestEntry方法决定是否要将表头元素删除，这里主要是为了支持LRU，如果该方法返回true，则表示缓存已满，会移除链表头元素

• 其中evict 变量在HashMap中的解释是，如果false表示创建模式，也就是反序列化时初始化HashMap数据时调用的put方法

获取元素

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 lastLinkedHashMap.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;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
}

LinkedHashMap重写了HashMap的get方法，主要是为了在获取元素后，根据accessOrder变量来判断是否要根据LRU调整元素位置；默认为false，所以获取元素后顺序是不会变的，也就是保证了原有的顺序；

但是如果要作为LRU缓存中心来存储数据，则需要设置为true，接着调用重写了HashMap的afterNodeAccess方法，对元素位置进行调整，其实也就是将当前访问的元素移动到链表的尾部

移除元素

void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;
}

在元素移除后，需要将该元素从双向链表中移除，逻辑也是比较简单

遍历集合

LinkedHashMap重写了Map相关集合遍历的方法，比如entrySet、keySet等，让外部能够根据双向链表顺序访问到元素

public Set<Map.Entry<K,V>> entrySet() {Set<Map.Entry<K,V>> es;return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {public final int size()                 { return size; }public final void clear()               { LinkedHashMap.this.clear(); }public final Iterator<Map.Entry<K,V>> iterator() {return new LinkedEntryIterator();}public final boolean contains(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Node<K,V> candidate = getNode(hash(key), key);return candidate != null && candidate.equals(e);}public final boolean remove(Object o) {if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Object value = e.getValue();return removeNode(hash(key), key, value, true, true) != null;}return false;}public final Spliterator<Map.Entry<K,V>> spliterator() {return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED |Spliterator.DISTINCT);}public final void forEach(Consumer<? super Map.Entry<K,V>> action) {if (action == null)throw new NullPointerException();int mc = modCount;for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)action.accept(e);if (modCount != mc)throw new ConcurrentModificationException();}
}

LRU的支持

LinkedHashMap天生支持LRU，可以用于作为LRU缓存中心，当LinkedHashMap创建时可以传入参数将成员变量accessOrder设置为true；表示需要根据元素访问来调整顺序；

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

这样当访问元素时会将该元素移动到队尾，经过多次访问后，最近访问的元素到了队尾，而最早访问元素则到了队头；

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;
}

当插入元素时提供了一个方法removeEldestEntry用于根据当前最大缓存容量来决定是否要删除队头元素

void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;
}

所以创建LRU的缓存中心只需要两步：

• 创建LinkedHashMap时设置accessOrder为true

• 重写removeEldestEntry方法，在该方法中，如果当前元素个数大于最大允许的缓存元素个数，则返回true已移除双向链表中的头元素

简单LRU缓存中心实现：

public class LruCacheCenter<K, V> extends LinkedHashMap<K, V> {private int mMaxCacheSize;//最大缓存个数public LruCacheCenter() {this(MAX_CACHE_NUM);}public LruCacheCenter(int maxCacheSize) {super(maxCacheSize, 0.75f, true);//accessOrder设置为truethis.mMaxCacheSize = maxCacheSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > mMaxCacheSize;}
}