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 eldest
LinkedHashMap.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 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;
}
}
LinkedHashMap重写了HashMap的get方法，主要是为了在获取元素后，根据accessOrder变量来判断是否要根据LRU调整元素位置；默认为false，所以获取元素后顺序是不会变的，也就是保证了原有的顺序；
但是如果要作为LRU缓存中心来存储数据，则需要设置为true，接着调用重写了HashMap的afterNodeAccess方法，对元素位置进行调整，其实也就是将当前访问的元素移动到链表的尾部
移除元素
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.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;
else
b.after = a;
if (a == null)
tail = b;
else
a.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 eldest
LinkedHashMap.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设置为true
this.mMaxCacheSize = maxCacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > mMaxCacheSize;
}
}