LinkedHashMap继承了HashMap，他在HashMap的基础上增加了一个双向链表的结构，链表默认维持key插入的顺序，重复的key值插入不会改变顺序，适用于使用者需要返回一个顺序相同的map对象的情况。还可以生成access-order顺序的版本，按照最近访问顺序来存储，刚被访问的结点处于链表的末尾，适合LRU，put get compute merge都算作一次访问，其中put key值相同的结点也算作一次访问，replace只有在换掉一个键值对的时候才算一次访问，putAll产生的访问顺序取决于原本map的迭代器实现。

在插入键值对时，可以通过对removeEldestEntry重写来实现新键值对插入时自动删除最旧的键值对

拥有HashMap提供的方法，迭代器因为是通过遍历双向链表，所以额外开销与size成正比与capacity无关，因此选择过大的初始大小对于遍历时间的增加没有HashMap严重，后者的遍历时间依赖与capacity。

同样是非线程安全方法，对于LinkedHashMap来说，修改结构的操作除了增加和删除键值对外，还有对于access-order时进行了access导致迭代器顺序改变，主要是get操作，对于插入顺序的来说，仅仅修改一个已有key值的value值不是一个修改结构的操作，但对于访问顺序，put和get已有的key值会改变顺序。迭代器也是fail-fast设计，但是fail-fast只是一个调试功能，一个设计良好的程序不应该出现这个错误

因为HashMap加入了TreeNode，所以现在LinkedHashMap也有这个功能

 以下描述中的链表，若无特别说明都是指LinkedHashMap的双向链表

---

 

先来看一下基本结构，每个键值对加入了前后指针，集合加入了头尾指针来形成双向链表，accessOrder代表链表是以访问顺序还是插入顺序存储

static class Entry
     
       extends HashMap.Node
      
        {        Entry
       
         before, after;//增加了先后指针来形成双向链表        Entry(int hash, K key, V value, Node
        
          next) {            super(hash, key, value, next);        }    }    /**     * The head (eldest) of the doubly linked list.头部     */    transient LinkedHashMap.Entry
         
           head;    /**     * The tail (youngest) of the doubly linked list.尾部     */    transient LinkedHashMap.Entry
          
            tail; //true访问顺序 false插入顺序 final boolean accessOrder;
          
         
        
       
      
     

然后是几个内部方法。linkNodeLast将p连接到链表尾部

private void linkNodeLast(LinkedHashMap.Entry
     
       p) {        LinkedHashMap.Entry
      
        last = tail;        tail = p;        if (last == null)            head = p;//原本链表为空则p同时为头部        else {            p.before = last;            last.after = p;        }    }
      
     

transferLinks用dst替换src

private void transferLinks(LinkedHashMap.Entry
     
       src,                               LinkedHashMap.Entry
      
        dst) {        LinkedHashMap.Entry
       
         b = dst.before = src.before;        LinkedHashMap.Entry
        
          a = dst.after = src.after;        if (b == null)            head = dst;        else            b.after = dst;        if (a == null)            tail = dst;        else            a.before = dst;    }
        
       
      
     

reinitialize在调用HashMap方法的基础上，将head和tail设为null

void reinitialize() {        super.reinitialize();        head = tail = null;    }

newNode生成一个LinkedHashMap结点，next指向e，插入到LinkedHashMap链表末端

Node
     
       newNode(int hash, K key, V value, Node
      
        e) {        LinkedHashMap.Entry
       
         p =            new LinkedHashMap.Entry
        
         (hash, key, value, e);//新建一个键值对，next指向e        linkNodeLast(p);//p插入到LinkedHashMap链表末端        return p;    }
        
       
      
     

replacementNode根据原结点生成一个LinkedHashMap结点替换原结点

Node
     
       replacementNode(Node
      
        p, Node
       
         next) {        LinkedHashMap.Entry
        
          q = (LinkedHashMap.Entry
         
          )p;        LinkedHashMap.Entry
          
            t = new LinkedHashMap.Entry
           
            (q.hash, q.key, q.value, next);//生成一个新的键值对next是给出的next参数 transferLinks(q, t);//用t替换q return t; }
           
          
         
        
       
      
     

newTreeNode生成一个TreeNode结点，next指向next，插入到LinkedHashMap链表末端

TreeNode
     
       newTreeNode(int hash, K key, V value, Node
      
        next) {        TreeNode
       
         p = new TreeNode
        
         (hash, key, value, next);//生成一个TreeNode，next指向参数next        linkNodeLast(p);//p插入到LinkedHashMap链表末端        return p;    }
        
       
      
     

replacementTreeNode根据结点p生成一个新的TreeNode，next设为给定的next，替换原本的p

TreeNode
     
       replacementTreeNode(Node
      
        p, Node
       
         next) {        LinkedHashMap.Entry
        
          q = (LinkedHashMap.Entry
         
          )p;        TreeNode
          
            t = new TreeNode
           
            (q.hash, q.key, q.value, next); transferLinks(q, t);//根据结点p生成一个新的TreeNode，next设为给定的next，替换原本的p return t; }
           
          
         
        
       
      
     

afterNodeRemoval从LinkedHashMap的链上移除结点e

void afterNodeRemoval(Node
     
       e) {         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;    }
       
      
     

afterNodeInsertion可能移除最旧的结点，需要evict为true同时链表不为空同时removeEldestEntry需要重写

void afterNodeInsertion(boolean evict) {         LinkedHashMap.Entry
     
       first;        if (evict && (first = head) != null && removeEldestEntry(first)) {
   //removeEldestEntry需要重写才从发挥作用，否则一定返回false            K key = first.key;//移除链表头部的结点            removeNode(hash(key), key, null, false, true);        }    }
     

afterNodeAccess在访问过后将结点e移动到链表尾部，需要Map是access-order，若移动成功则增加modCount

void afterNodeAccess(Node
     
       e) {         LinkedHashMap.Entry
      
        last;        if (accessOrder && (last = tail) != e) {
   //Map是access-order同时e不是链表的尾部            LinkedHashMap.Entry
       
         p =                (LinkedHashMap.Entry
        
         )e, b = p.before, a = p.after;            p.after = null;            if (b == null)//将结点e从链表中剪下                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;//结点e移动到链表尾部            ++modCount;//因为有access-order下结点被移动，所以增加modCount        }    }
        
       
      
     

构造函数方面，accessOrder默认是false插入顺序，初始大小为16，负载因子为0.75，这里是同HashMap。复制构造也是调用了HashMap.putMapEntries方法

containsValue遍历链表寻找相等的value值，这个操作一定不会造成结构改变

public boolean containsValue(Object value) {        for (LinkedHashMap.Entry
     
       e = head; e != null; e = e.after) {
   //检查同样是根据LinkedHashMap提供的链表顺序进行遍历            V v = e.value;            if (v == value || (value != null && value.equals(v)))                return true;        }        return false;    }
     

 get方法复用HashMap的getNode方法，若找到结点且Map是访问顺序时，要将访问的结点放到链表最后，若没找到则返回null。而getOrDefault仅有的区别是没找到时返回defaultValue

public V get(Object key) {        Node
     
       e;        if ((e = getNode(hash(key), key)) == null)//复用HashMap的getNode方法            return null;        if (accessOrder)            afterNodeAccess(e);//access-order时将e放到队尾        return e.value;    }    public V getOrDefault(Object key, V defaultValue) {       Node
      
        e;       if ((e = getNode(hash(key), key)) == null)           return defaultValue;//复用HashMap的getNode方法，若没有找到对应的结点则返回defaultValue       if (accessOrder)           afterNodeAccess(e);//access-order时将e放到队尾       return e.value;   }
      
     

clear方法在HashMap的基础上要把head和tail设为null

public void clear() {        super.clear();        head = tail = null;    }

removeEldestEntry在put和putAll插入键值对时调用，原本是一定返回false的，如果要自动删除最旧的键值对要返回true，需要进行重写。比如下面这个例子，控制size不能超过100

private static final int MAX_ENTRIES = 100;     protected boolean removeEldestEntry(Map.Entry eldest) {        return size() > MAX_ENTRIES;     }

下面两个方法和HashMap相似，返回key的Set和value的Collection还有返回键值对的Set，这个是直接引用，所以对它们的remove之类的修改会直接反馈到LinkedHashMap上

public Set
     
       keySet() {        Set
      
        ks = keySet;        if (ks == null) {            ks = new LinkedKeySet();            keySet = ks;        }        return ks;//返回key值的set    }    public Collection
       
         values() {        Collection
        
          vs = values;        if (vs == null) {            vs = new LinkedValues();            values = vs;        }        return vs;//返回一个包含所有value值的Collection    }    public Set
         
          
           > entrySet() { Set
           
            
             > es; return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;//返回一个含有所有键值对的Set }
            
           
          
         
        
       
      
     

检查HashMap的putVal方法，我们可以看到在找到了相同key值并修改value值时会调用afterNodeAccess，对于access-order会改变结点顺序

if (e != null) { // 找到了相同的key则修改value值并返回旧的value                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }