LinkedHashMap类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是插入次序，或者是最近最少使用（LRU）的次序。只比HashMap慢一点；而在迭代访问时反而更快，因为它使用链表维护内部次序（HashMap是基于散列表实现的),源码来自android 源码.

     LinkedHashMap定义两个属性

/**     * A dummy entry in the circular linked list of entries in the map.     * The first real entry is header.nxt, and the last is header.prv.     * If the map is empty, header.nxt == header && header.prv == header.     */    transient LinkedEntry
     
       header;//双向链表    /**     * True if access ordered, false if insertion ordered.     */    private final boolean accessOrder;//默认情况false,插入顺序,true 访问顺序
     

在linkedhashmap构造器对链表进行初始化。

 

(1)get

从table数组中取（和hashmap一致），多了一步mainTail动作，把获取的数据，移到双向链表的尾部tail.

@Override public V get(Object key) {        /*         * This method is overridden to eliminate the need for a polymorphic         * invocation in superclass at the expense of code duplication.         */        if (key == null) {            HashMapEntry
     
       e = entryForNullKey;            if (e == null)                return null;            if (accessOrder)                makeTail((LinkedEntry
      
       ) e);//把访问的节点迁移到链表的尾部            return e.value;        }        int hash = Collections.secondaryHash(key);        HashMapEntry
       
        [] tab = table;        for (HashMapEntry
        
          e = tab[hash & (tab.length - 1)];//从数组中获取                e != null; e = e.next) {            K eKey = e.key;            if (eKey == key || (e.hash == hash && key.equals(eKey))) {                if (accessOrder)                    makeTail((LinkedEntry
         
          ) e);//把访问的节点迁移到链表尾部。                return e.value;            }        }        return null;    }    /**     * Relinks the given entry to the tail of the list. Under access ordering,     * this method is invoked whenever the value of a  pre-existing entry is     * read by Map.get or modified by Map.put.     */    private void makeTail(LinkedEntry
          
            e) { // Unlink e 在链表中删除该节点e e.prv.nxt = e.nxt; e.nxt.prv = e.prv; // Relink e as tail 在尾部添加 LinkedEntry
           
             header = this.header; LinkedEntry
            
              oldTail = header.prv; e.nxt = header; e.prv = oldTail; oldTail.nxt = header.prv = e; modCount++; }
            
           
          
         
        
       
      
     

 

(2)put

添加到数据中，重载了preModify和addNewEntry，把存在的节点迁移到链表尾部或者新的节点添加到链表尾部。

//hashmap public V put(K key, V value) {        if (key == null) {            return putValueForNullKey(value);        }        int hash = Collections.secondaryHash(key);        HashMapEntry
     
      [] tab = table;        int index = hash & (tab.length - 1);        for (HashMapEntry
      
        e = tab[index]; e != null; e = e.next) {            if (e.hash == hash && key.equals(e.key)) {                preModify(e);//linkedhashmap 重载该方法,map存在该key,该节点迁移到链表尾部。                V oldValue = e.value;                e.value = value;                return oldValue;            }        }        // No entry for (non-null) key is present; create one        modCount++;        if (size++ > threshold) {            tab = doubleCapacity();            index = hash & (tab.length - 1);        }        addNewEntry(key, value, hash, index);//linkedhashmap重载了这个方法        return null;    }//LinkedHashmap@Override void addNewEntry(K key, V value, int hash, int index) {        LinkedEntry
       
         header = this.header;        // Remove eldest entry if instructed to do so.        LinkedEntry
        
          eldest = header.nxt;        if (eldest != header && removeEldestEntry(eldest)) {            remove(eldest.key);        }        // Create new entry, link it on to list, and put it into table  节点添加聊表尾部和table数组中        LinkedEntry
         
           oldTail = header.prv;        LinkedEntry
          
            newTail = new LinkedEntry
           
            ( key, value, hash, table[index], header, oldTail); table[index] = oldTail.nxt = header.prv = newTail; }
           
          
         
        
       
      
     

 

(3)contains

    containsValue 从链表中查询。hashmap从table数组中查询，进行该操作时，没有hashmap快（数组比链表迭代快）。

    

@Override public boolean containsValue(Object value) {        if (value == null) {            for (LinkedEntry
     
       header = this.header, e = header.nxt;                    e != header; e = e.nxt) {                if (e.value == null) {                    return true;                }            }            return false;        }        // value is non-null        for (LinkedEntry
      
        header = this.header, e = header.nxt; e != header; e = e.nxt) {//迭代链表            if (value.equals(e.value)) {                return true;            }        }        return false;    }
      
     

　　

    containKey 从数组中查询，和hashmap一致。

(4)

remove ，重载了postRemove

//在链表中删除节点 @Override void postRemove(HashMapEntry
     
       e) {        LinkedEntry
      
        le = (LinkedEntry
       
        ) e;        le.prv.nxt = le.nxt;        le.nxt.prv = le.prv;        le.nxt = le.prv = null; // Help the GC (for performance)    }
       
      
     

 

     

(5)迭代器

 hashmap：是迭代数组 ，linkedhashmap 迭代链表。

(6)LruCache利用LinkedHashmap自身实现的lru功能，并对map进行容量限制。在进行put操作时，进行trimToSize.

public void trimToSize(int maxSize) {        while (true) {            K key;            V value;            synchronized (this) {                if (size < 0 || (map.isEmpty() && size != 0)) {                    throw new IllegalStateException(getClass().getName()                            + ".sizeOf() is reporting inconsistent results!");                }                if (size <= maxSize || map.isEmpty()) {                    break;                }                                //迭代删除多余的节点，从链表头部开始删除。                Map.Entry
     
       toEvict = map.entrySet().iterator().next();                key = toEvict.getKey();                value = toEvict.getValue();                map.remove(key);                size -= safeSizeOf(key, value);                evictionCount++;            }            entryRemoved(true, key, value, null);        }    }