LinkedHashMap解析

建议阅读本文前先了解HashMap，鄙人文章 HashMap解析

public class LinkedHashMap<K,V> extends HashMap<K,V>

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

很简单，LinkedHashMap的Entry只是比HashMap的Entry多了2个变量，before和after
先看put()

put()-->putVal()-->newNode()-->linkNodeLast()

transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

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

put比较简单，修改last和新增node的before和atfer。
再看remove()，remove的时候肯定也要修改node前一个node的after，后一个node的before

remove()-->removeNode()-->afterNodeRemoval() //HashMap里是个空方法，LinkedHashMap实现了

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

get()直接走HashMap

LinkedHashMap除了增加before和after之外，还有一个功能——accessOrder

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

accessOrder默认是false，如果是true，则每次put()更新旧值，或者get()的时候，都会执行方法

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

这个方法就是把操作的node移到末尾，如此可以确定，末尾的node一定是最近操作的，而head当然是最长时间未操作的。这就是LRU算法，Android里的LruCache里面其实也只是维护了1个accessOrder=true的LinkedHashMap而已，当达到/超过限定的内存maxSize时，只要从head开始移除就可以了。

public LruCache(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    this.maxSize = maxSize;
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

//Android LinkedHashMap
public Entry<K, V> eldest() {
    LinkedEntry<K, V> eldest = header.nxt;
    return eldest != header ? eldest : null;
}