前面关于HashMap的学习，我们知道HashMap 无法保证顺序，本节的主角LinkedHashMap 可以保证顺序。

访问顺序 or 插入顺序

属性 accessOrder 值true 则是访问的顺序，false 则是插入的顺序，默认记录的是插入顺序。 注意 accessOrder 加了 final 限制，说明确定访问顺序 或 插入顺序后就不能更改了。

极限的复用HashMap

LinkedHashMap 类继承了 HashMap,大部分功能复用HashMap , 只是在此基础上记录了顺序

public class LinkedHashMap
    extends HashMap
    implements Map
{
  }

它的Entry是记录顺序的关键，它继承HashMap.Node ,增加了before,after ；是不是很熟悉，没错，就是所有的Entry 构成一个双向链表。

重要的"钩子方法"

• put 已经存在的key (或者 replace )更新value后会调用,afterNodeAccess
• put 不存在的key 会调用 afterNodeInsertion
• remove 指定key 会调用 afterNodeRemoval

LinkedHashMap 重写对应的“钩子方法”，维护对应的顺序

    void afterNodeAccess(Node p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node p) { }

顺序保证

删除某个节点指针变化示意图，没图的话就太难了

• 如果b 为null ，a 变为双向链表头节点
• 如果a 为null ， 则 b 双向链表尾节点
• 一般情况 b.after =a; a.before =b;

void afterNodeRemoval(Node e) { // unlink
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)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;
    }

afterNodeAccess 指针操作情况，对照着图，不然很难

• e.before = last(操作前链表tail )
• e.after = null
• b.after =a;
• a.before =b;

a 与 b 指针与 删除一样 需要考虑空值情况，感兴趣的对照图自己推下。

   void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)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;
        }
    }

• 值得注意的是 newNode 直接linkNodeLast 放列表末尾

get 方法 如果 accessOrder 为true 会放置调用afterNodeAccess 即放到双向列表末尾

afterNodeInsertion

afterNodeInsertion其实我之前也没有明本， 直到看了removeEldestEntry这个上面注释，主要用来淘汰较早的元素

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

放码过来试试效果

        LinkedHashMap linkedHashMap = new LinkedHashMap(){
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > 5;
            };

        };
        for(int i=1;i<10;i++){
            linkedHashMap.put(i,i);
            System.out.println("the size after put i is = " + linkedHashMap.size());
        }

输出结果

the size after put i is = 1
the size after put i is = 2
the size after put i is = 3
the size after put i is = 4
the size after put i is = 5
the size after put i is = 5
the size after put i is = 5
the size after put i is = 5
the size after put i is = 5

’原来除了保证顺序还可以实现LRU功能，确实介于牛A牛C之间。

终于讲完了，下期再来