本文代码来自JDK8

性质

1. LinkedHashMap 继承于 HashMap, 具备 HashMap 的一切性质;
2. LinkedHashMap 会按先后插入顺序对元素排序遍历;
3. LinkedHashMap 会额外使用双向链表结构来表示插入的元素.

变量

1. transient LinkedHashMap.Entry head
   表示双向链表的头部
2. transient LinkedHashMap.Entry tail
   表示双向链表的尾部
3. final boolean accessOrder
   true: 表示把最后访问的节点放到双向链表的最后一位, 访问的方式有替换旧节点和读取节点

put

LinkedHashMap 的 put 方法也是使用 HashMap 的方法, 不同在于重写了 newNode(), afterNodeAccess 和 afterNodeInsertion 这几个方法, 这几个方法的调用可以看 HashMap-详解四, 下面具体讲讲如何重写这几个方法.

newNode

/** * 根据 key-value 创建双向链表节点 * e 表示下一个节点, 不过这里是空值, 不用理会 */Node
    
      newNode(int hash, K key, V value, Node
     
       e) {    LinkedHashMap.Entry
      
        p =        new LinkedHashMap.Entry
       
        (hash, key, value, e);    linkNodeLast(p);    return p;}/** * 继承 HashMap 的静态内部类 Node */static class Entry
        
          extends HashMap.Node
         
           { Entry
          
            before, after; Entry(int hash, K key, V value, Node
           
             next) { super(hash, key, value, next); }}/** * 把新节点插入到双向链表尾部 */private void linkNodeLast(LinkedHashMap.Entry
            
              p) { LinkedHashMap.Entry
             
               last = tail; tail = p; // 如果这是空链表, 新节点就是头结点 if (last == null) head = p; else { p.before = last; last.after = p; }}
             
            
           
          
         
        
       
      
     
    

afterNodeAccess

/** * 1. 使用 get 方法会访问到节点, 从而触发调用这个方法 * 2. 使用 put 方法插入节点, 如果 key 存在, 也算要访问节点, 从而触发该方法 * 3. 只有 accessOrder 是 true 才会调用该方法 * 4. 这个方法会把访问到的最后节点重新插入到双向链表结尾 */void afterNodeAccess(Node
    
      e) { // move node to last    // 用 last 表示插入 e 前的尾节点    // 插入 e 后 e 是尾节点, 所以也是表示 e 的前一个节点    LinkedHashMap.Entry
     
       last;    if (accessOrder && (last = tail) != e) {        // p: 当前节点        // b: 前一个节点        // a: 后一个节点        // 结构为: b <=> p <=> a        LinkedHashMap.Entry
      
        p =            (LinkedHashMap.Entry
       
        )e, b = p.before, a = p.after;        // 结构变成: b <=> p <- a        p.after = null;        // 如果当前节点 p 本身是头节点, 那么头结点要改成 a        if (b == null)            head = a;        // 如果 p 不是头尾节点, 把前后节点连接, 变成: b -> a        else            b.after = a;        // a 非空, 和 b 连接, 变成: b <- a        if (a != null)            a.before = b;        // 如果 a 为空, 说明 p 是尾节点, b 就是它的前一个节点, 符合 last 的定义        else            last = b;        // 如果这是空链表, p 改成头结点        if (last == null)            head = p;        // 否则把 p 插入到链表尾部        else {            p.before = last;            last.after = p;        }        tail = p;        ++modCount;    }}
       
      
     
    

afterNodeInsertion

/** * 插入新节点才会触发该方法 * 根据 HashMap 的 putVal 方法, evict 一直是 true * removeEldestEntry 方法表示移除规则, 在 LinkedHashMap 里一直返回 false * 所以在 LinkedHashMap 里这个方法相当于什么都不做 */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 的遍历方式和 HashMap 的一样, 都是通过 entrySet 方法返回 Set 实例, 然后通过 iterator 方法返回迭代器进行遍历.

entrySet

/** * 返回 LinkedEntrySet 实例, 这是非静态内部类 */public Set
    
     
      > entrySet() {    Set
      
       
        > es;    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;}/** * 和 HashMap 的 EntrySet 类一样继承 AbstractSet * iterator 方法返回 LinkedEntryIterator 实例 */final class LinkedEntrySet extends AbstractSet
        
         
          > { ... public final Iterator
          
           
            > iterator() { return new LinkedEntryIterator(); } ...}
           
          
         
        
       
      
     
    

next 和 hasNext

/** * next 方法实际是调用父类 nextNode 方法返回节点 */final class LinkedEntryIterator extends LinkedHashIterator        implements Iterator
    
     
      > {    public final Map.Entry
      
        next() { return nextNode(); }}abstract class LinkedHashIterator {    LinkedHashMap.Entry
       
         next;    LinkedHashMap.Entry
        
          current;    int expectedModCount;    /**     * 构造函数, 从双向链表头节点开始遍历     */    LinkedHashIterator() {        next = head;        expectedModCount = modCount;        current = null;    }    public final boolean hasNext() {        return next != null;    }    /**     * 遍历比较简单, 直接读取下一个节点就行     */    final LinkedHashMap.Entry
         
           nextNode() { LinkedHashMap.Entry
          
            e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; return e; } ...}