java.util.LinkedHashMap源码解析

所属包

package java.util;

继承与实现关系

public class LinkedHashMap<K,V>  extends HashMap<K,V>  implements Map<K,V>  

准备工作

由于LinkedHashMap也是继承HashMap，在HashMap类的基础上进行的功能扩展，所以先了解下HashMap ：java集合之HashMap源码解析

LinkedHashMap中链地址的双向循环链表结构

        /**  
         * 双向循环链表维护冲突值  
         */  
        private static class Entry<K,V> extends HashMap.Entry<K,V> {  
            //双向循环链表的前驱节点和后继结点  
            Entry<K,V> before, after;  
      
            Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {  
                super(hash, key, value, next);  
            }  
      
            /**  
             * 通过前驱后继关系将节点删除  
             */  
            private void remove() {  
                //当前节点的前驱节点的后继为当前节点的后继结点  
                before.after = after;  
                //当前节点的后继结点的前驱为当前节点的前驱节点  
                after.before = before;  
            }  
      
            /**  
             * 将此项插入列表中指定的现有项之前。  
             * existingEntry :现有项  
             */  
            private void addBefore(Entry<K,V> existingEntry) {  
                //this.after =existingEntry;  
                after  = existingEntry;  
                //this.before =existingEntry.before;  
                before = existingEntry.before;  
                before.after = this;  
                after.before = this;  
            }  
      
            /**  
             * 如果LinkedHashMap的排序顺序为访问顺序，那么就将当前节点插入到头结点前面  
             */  
            void recordAccess(HashMap<K,V> m) {  
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
                //如果排序顺序为访问顺序  
                if (lm.accessOrder) {  
                    lm.modCount++;  
                    //删除当前节点  
                    remove();  
                    //在头节点前面插入当前节点  
                    addBefore(lm.header);  
                }  
            }  
      
            void recordRemoval(HashMap<K,V> m) {  
                remove();  
            }  
        }  

属性

    /**  
     * 双向链表的头结点  
     */  
    private transient Entry<K,V> header;  
  
    /**  
     * 排序模式：对于访问顺序，为 true；对于插入顺序，则为 false。  
     */  
    private final boolean accessOrder; 

构造方法

构造方法1：

    /**  
     * 传入初始化容量，加载因子，默认采用插入顺序排序的HashMap构造  
     */  
    public LinkedHashMap(int initialCapacity, float loadFactor) {  
        super(initialCapacity, loadFactor);  
        accessOrder = false;  
    }  

构造方法2：

    /**  
     * 传入初始化容量，默认加载因子为0.75,默认采用插入顺序排序的HashMap构造  
     */  
    public LinkedHashMap(int initialCapacity) {  
        super(initialCapacity);  
        accessOrder = false;  
    }  

构造方法3：

    /**  
     * 采用默认初始化容量16，默认加载因子为0.75,默认插入顺序排序的HashMap构造  
     */  
    public LinkedHashMap() {  
        super();  
        accessOrder = false;  
    }  

构造方法4：

    /**  
     * 构造一个映射关系与指定 Map 相同的 HashMap。    
     * 所创建的 HashMap 具有默认的加载因子 (0.75) 和足以容纳指定 Map 中映射关系的初始容量。   
     * 采用默认插入顺序排序  
     */  
    public LinkedHashMap(Map<? extends K, ? extends V> m) {  
        super(m);  
        accessOrder = false;  
    }  

构造方法5：

    /**  
     * 构造一个拥有初始化容量、加载因子、排序顺序的LinkedHashMap  
     */  
    public LinkedHashMap(int initialCapacity,  
                         float loadFactor,  
                         boolean accessOrder) {  
        super(initialCapacity, loadFactor);  
        this.accessOrder = accessOrder;  
    }  

方法

init方法，初始化双向循环链表

   @Override  
    void init() {  
        header = new Entry<>(-1, null, null, null);  
        header.before = header.after = header;  
    }  

createEntry方法创建节点，将节点插入到头结点的前面

void createEntry(int hash, K key, V value, int bucketIndex) {  
        HashMap.Entry<K,V> old = table[bucketIndex];  
        Entry<K,V> e = new Entry<>(hash, key, value, old);  
        table[bucketIndex] = e;  
        e.addBefore(header);  
        size++;  
    }  

transfer方法，将所有元素都放到新的数组中，重写父类的HashMap
的transfer方法。

        /**  
         * 将所有的元素放置到新的数组中  
         * 重写父类HashMap的transfer方法  
         */  
        @Override  
        void transfer(HashMap.Entry[] newTable, boolean rehash) {  
            int newCapacity = newTable.length;  
            //使用双向链表的头结点进行循环遍历  
            for (Entry<K,V> e = header.after; e != header; e = e.after) {  
                if (rehash)  
                    e.hash = (e.key == null) ? 0 : hash(e.key);  
                //通过hash值获取对应的下标索引  
                int index = indexFor(e.hash, newCapacity);  
                //插入到链表表头  
                e.next = newTable[index];  
                //新数组的索引对应的值为header  
                newTable[index] = e;  
            }  
        }  

get方法，返回此映射中映射到指定键的值。

    public V get(Object key) {  
            //调用父类的getEntry方法，通过键key来获取对应的Entry  
            Entry<K,V> e = (Entry<K,V>)getEntry(key);  
             //如果e为null，那么根本不存在对应的Entry就更没有对应的值了，所以返回null  
            if (e == null)  
                return null;  
            //会将当前节点插入到头结点前面  
            e.recordAccess(this);  
            return e.value;  
        }  

---

阅读总结：
(1) LinkedHashMap存储冲突值使用双向循环链表
(2) LinkdHashMap中accessOrder属性，true意味着排序模式为访问顺序，false意味着排序模式为插入顺序。
(3) LinkedHashMap保持插入元素的有序性原理：首先LinkedHashMap插入元素是在双向循环链表的头节点的前面插入节点（头插法，也就是我们生活中的不停插队方式插入元素）。而LinkedHashMap的遍历方式是采用HashMap的遍历方式一样，是从后向前遍历的，这样的插入元素方式和取出元素方式从而保证了元素的有序性。

---

.............................该源码为jdk1.7版本的