特点

* 各个元素不仅仅按照HashMap的结构存储，而且每个元素包含了before/after指针，通过一个头元素header，形成一个双向循环链表。使用循环链表，保存了元素插入的顺序。

* 可设置参数，让每次get()后的元素排在双向链表的最后。

 

Entry类

private static class Entry
       
         extends HashMap.Entry
        
          // 继承自HashMap的Entry（已有key/value/hash/next字段）{     // 双向链表     Entry
         
           before;     Entry
          
            after;     // 构造函数     Entry(int hash, K key, V value, HashMap.Entry
           
             next) {            super(hash, key, value, next);     }          // 删除当前结点     private void remove(){          before.after = after;          after.before = before;     }     // 在当前结点的前面添加结点     private void addBefore(Entry
            
              existingEntry){ after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } // 如果设定某个参数，get()命中后，把当前元素放到链表最后 void recoreAccess(HashMap
             
               m) { LinkedHashMap
              
                lm = (LinkedHashMap
               
                )m; // 把调用者的this转化成LinkedHashMap if(lm.accessOrder){ remove(); // 删除当前结点 addBefore(lm.header); // 插入到header前面 } }}
               
              
             
            
           
          
         
        
       

　　

源码简要分析

public class LinkedHashMap
       
         extends HashMap
        
         {     private Entry
         
           header; // 双向链表的头部。     private final boolean accessOrder; // 默认false。如果true表示get()命中后，把当前元素放到链表最后。     // init()    void init() {        header = new Entry<>(-1, null, null, null);        header.before = header.after = header; // 双向链表首尾相连    }     // put() 继承自 HashMap     // 添加元素时，不仅按照HashMap的方式散列存储，而且还通过双向链表记录先后顺序     public V put(K key, V value) {           int hash = hash(key.hashCode());     // key的特殊hash值          int i = indexFor(hash,table.length);     // 槽位 index          // key是否已经存在，存在则返回value。          for (Entry
          
            e = table[i]; e != null; e = e.next) {            Object k;            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                V oldValue = e.value;                e.value = value;                e.recordAccess(this); //LinkedHashMap特有                return oldValue;            }              }               // key不存在就添加Entry               addEntry(hash,key,value,i);               return null;     }    void addEntry(int hash, K key, V value, int bucketIndex) {        createEntry(hash, key, value, bucketIndex);        // Remove eldest entry if instructed, else grow capacity if appropriate        Entry
           
             eldest = header.after;        if (removeEldestEntry(eldest)) {            removeEntryForKey(eldest.key);        } else {            if (size >= threshold)                resize(2 * table.length);        }    }    void createEntry(int hash, K key, V value, int bucketIndex/*槽位index*/) {        HashMap.Entry
            
              old = table[bucketIndex]; Entry
             
               e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; e.addBefore(header); size++; } // get() // 取元素是按照散列而不是双向链表进行查找，速度快 public V get(Object key) { Entry
              
                e = (Entry
               
                )getEntry(key); // getEntry()使用了HashMap的getEntry，即按照HashMap的方式寻找元素。 if (e == null) return null; e.recordAccess(this); return e.value; }}
               
              
             
            
           
          
         
        
       

　　

添加元素的过程示意图

初始化时，头元素header的before/after均指向自身。

 

插入元素e1后，header的before/after均指向e1；e1的before/after均指向header。

 

插入元素e2后，header的after继续指向e1，e1的after指向e2，e1的before指向header。header的before指向e2。e2的before指向e1，e2的after指向header。