LinkedHashMap源码剖析（基于JDK1.7）

你的名字 2022-06-09 01:26 199阅读 0赞

## 一、LinkedHashMap简介 ##

LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。  
LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变（扩容时映射顺序会重新设定）。  
LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。  
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。必要时通过synchronizedMap来包装实现同步类。  
根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。 默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。可以重写`removeEldestEntry`方法返回true值指定插入元素时移除最老的元素。

## 二、关键源码实现 ##

### 1、类结构 ###

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

我们可以看出LinkedHashMap继承了HashMap！

### 2、成员变量 ###

// LinkedHashMap维护了一个链表，header是链表头，且不存储数据。此链表不同于HashMap里面的那个next链表  
    private transient Entry<K, V> header;  
    
    // LRU:Least Recently Used最近最少使用算法  
    // accessOrder决定是否使用此算法，accessOrder=true使用，默认为false
    private final boolean accessOrder;

### 3、数据存储结构entry ###

//LinkedHashMap的entry继承自HashMap的Entry。
        private static class Entry<K,V> extends HashMap.Entry<K,V> {
        
            // These fields comprise the doubly linked list used for iteration.
        //通过上面这句源码的解释，我们可以知道这两个字段，是用来给迭代时使用的，相当于一个双向链表，实际上用的时候，操作LinkedHashMap的entry和操作HashMap的Entry是一样的，只操作相同的四个属性，这两个字段是由linkedHashMap中一些方法所操作。所以LinkedHashMap的很多方法度是直接继承自HashMap。
    //before：指向前一个entry元素。after：指向后一个entry元素
            Entry<K,V> before, after;
        //使用的是HashMap的Entry构造
            Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
                super(hash, key, value, next);
            }
    
    //下面是维护这个双向循环链表的一些操作。在HashMap中没有这些操作，因为HashMap不需要维护，
            /**
             * Removes this entry from the linked list.
             */
    //我们知道在双向循环链表时移除一个元素需要进行哪些操作把，比如有A,B,C，将B移除，那么A.next要指向C，C.before要指向A。
    因为这是双向循环链表，所以无论删除哪个节点，该方法都适用（包含头尾节点）。
            private void remove() {
    　　　　　　//this.before.after = this.after;
    　　　　　　//this.after.before = this.before; 这样看可能会更好理解，this指的就是要删除的那个元素。
    
                before.after = after;
                after.before = before;
            }
    
            /**
             * Inserts this entry before the specified existing entry in the list.
             */
    //双向循环立链表中，将当前的Entry插入到existingEntry的前面  。
    
            private void addBefore(Entry<K,V> existingEntry) {
                after  = existingEntry;
                before = existingEntry.before;
                before.after = this;
                after.before = this;
            }
    
            /**
             * This method is invoked by the superclass whenever the value
             * of a pre-existing entry is read by Map.get or modified by Map.set.
             * If the enclosing Map is access-ordered, it moves the entry
             * to the end of the list; otherwise, it does nothing.
             */
    //这个方法就是我们一开始说的，accessOrder为true时，就是使用的访问顺序，访问次数最少到访问次数最多，此时要做特殊处理。处理机制就是访问了一次，就将自己移动到链表尾部。这里就是先将自己删除了，然后在把自己添加。
    //这样，近期访问的少的就在链表的开始，最近访问的元素就会在链表的末尾。如果为false。那么默认就是插入顺序，直接通过链表的特点就能依次找到插入元素，不用做特殊处理。
    
    
            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();
            }
        }

### 4、构造函数 ###

//使用父类中的构造，初始化容量和加载因子，该初始化容量是指数组大小。
        public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
    //一个参数的构造
        public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
        }
    //无参构造
        public LinkedHashMap() {
            super();
            accessOrder = false;
        }
    //这个不用多说，用来接受map类型的值转换为LinkedHashMap
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super(m);
            accessOrder = false;
        }
    //真正有点特殊的就是这个，多了一个参数accessOrder。存储顺序，LinkedHashMap关键的参数之一就在这个，
    //true：指定迭代的顺序是按照访问顺序(近期访问最少到近期访问最多的元素)来迭代的。 false：指定迭代的顺序是按照插入顺序迭代，也就是通过插入元素的顺序来迭代所有元素
    //如果你想指定访问顺序，那么就只能使用该构造方法，其他三个构造方法默认使用插入顺序。
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }

还有一个需要注意的地方，在HashMap中，我们看到有一个空实现的init方法，这个方法在HashMap中没什么用，它的作用是留给子类覆盖的，也就是说，在LinkedhashMap构造方法中，调用super的构造方法后，还会调用自身的重写后的init方法，体现了Java的多态性。我们来看看被重写后的init方法：

//linkedHashMap中的init()方法，就使用header，hash值为-1，其他度为null，也就是说这个header不放在数组中，就是用来指示开始元素和标志结束元素的。
        void init() {
            header = new Entry<>(-1, null, null, null);
    //一开始是自己指向自己，没有任何元素。HashMap中也有init()方法是个空的，所以这里的init()方法就是为LinkedHashMap而写的。
            header.before = header.after = header;
        }

### 5、存数据 ###

//LinkedHashMap没有put(K key, V value)方法，只重写了被put调用的addEntry方法  
    //1是HashMap里原有的逻辑，23是LinkedHashMap特有的  
    void addEntry(int hash, K key, V value, int bucketIndex) {  
        createEntry(hash, key, value, bucketIndex);  
    
        Entry<K, V> eldest = header.after;  
        //3.如果有必要，移除LRU里面最老的Entry，否则判断是否该resize  
        if (removeEldestEntry(eldest)) {  
            removeEntryForKey(eldest.key);  
        } else {  
            if (size >= threshold)  
                resize(2 * table.length);  
        }  
    }  
    
    void createEntry(int hash, K key, V value, int bucketIndex) {  
        //1.同HashMap一样：在Entry数组+next链表结构里面加入Entry  
        HashMap.Entry<K, V> old = table[bucketIndex];  
        Entry<K, V> e = new Entry<K, V>(hash, key, value, old);  
        table[bucketIndex] = e;  
        //2.把新Entry也加到header链表结构里面去  
        e.addBefore(header);  
        size++;  
    }  
    
    //默认是false，我们可以重写此方法  
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {  
        return false;  
    }  
    
    //如果走到resize，会调用这里重写的transfer  
    //HashMap里面的transfer是n * m次运算（外层循环加内层链表遍历），LinkedHashtable重写后是n + m次运算（一次链表遍历）  
    void transfer(HashMap.Entry[] newTable) {  
        int newCapacity = newTable.length;  
        //直接遍历header链表，HashMap里面是遍历Entry数组  
        for (Entry<K, V> e = header.after; e != header; e = e.after) {  
            int index = indexFor(e.hash, newCapacity);  
            e.next = newTable[index];  
            newTable[index] = e;  
        }  
     }

### 6、取数据 ###

//重写了get(Object key)方法  
    public V get(Object key) {  
        //1.调用HashMap的getEntry方法得到e  
        Entry<K, V> e = (Entry<K, V>) getEntry(key);  
        if (e == null)  
            return null;  
        //2.LinkedHashMap新加入的操作  
        e.recordAccess(this);  
        return e.value;  
    }

accessOrder这个参数值控制着LinkedHashMap的迭代顺序，当accessOrder为true时，remove方法就是将当前元素从双向链表中移除，addBefore方法再将当前元素插入到链表的头部去，这样最近读到的元素，在迭代的时候是优先被迭代出来的！  
这就是所谓的LRU算法（Least Recently Used）：最近最少使用算法。当accessOrder为false时，不做任何事情，就按照插入顺序迭代出来。

## 三、总结 ##

### 1、结构 ###

LinkedHashMap由于继承自HashMap，因此它具有HashMap的所有特性，同样允许key和value为null。LinkedHashMap中加入了一个head头结点，将所有插入到该LinkedHashMap中的Entry按照插入的先后顺序依次加入到以head为头结点的双向循环链表的尾部。 实际上就是HashMap和LinkedList两个集合类的存储结构的结合。在LinkedHashMapMap中，所有put进来的Entry都保存在哈希表中，但它又额外定义了一个以head为头结点的空的双向循环链表，每次put进来Entry，除了将其保存到对哈希表中对应的位置上外，还要将其插入到双向循环链表的尾部。

### 2、LRU实现 ###

源码中的accessOrder标志位，当它false时，表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序，即每次put到LinkedHashMap中的Entry都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序。、  
当它为true时，表示双向链表中的元素按照访问的先后顺序排列（即访问过的元素放后面，未访问过的元素放前面），可以看到，虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序，但put和get方法均有调用recordAccess方法（put方法在key相同，覆盖原有的Entry的情况下调用recordAccess方法），该方法判断accessOrder是否为true。如果是，则将当前访问的Entry（put进来的Entry或get出来的Entry）移到双向链表的尾部（key不相同时，put新Entry时，会调用addEntry，它会调用creatEntry，该方法同样将新插入的元素放入到双向链表的尾部，既符合插入的先后顺序，又符合访问的先后顺序，因为这时该Entry也被访问了），否则，什么也不做。  
在LinkedHashMap中，有四个构造方法都将accessOrder设为false，说明默认是按照插入顺序排序的，而第五个构造方法可以自定义传入的accessOrder的值。因此可以指定双向循环链表中元素的排序规则，一般要用LinkedHashMap实现LRU算法，就要用该构造方法，将accessOrder置为true。

还有个removeEldestEntry方法，该方法如下：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {  
            return false;  
        }

该方法默认返回false，我们一般在用LinkedHashMap实现LRU算法时，要覆写该方法，一般的实现是，当设定的内存（这里指节点个数）达到最大值时，返回true，这样put新的Entry（该Entry的key在哈希表中没有已经存在）时，就会调用removeEntryForKey方法，将最近最少使用的节点删除（head后面的那个节点，实际上是最近没有使用）。

## 四、关于各种map实现 ##

java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap。Map主要用于存储健值对，根据键得到值，因此不允许键重复(重复了覆盖了),但允许值重复。

### 1、HashMap ###

Hashmap 是一个最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。遍历时，取得数据的顺序是完全随机的。 HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

### 2、HashTable ###

Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

### 3、LinkedHashMap ###

LinkedHashMap 是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢。不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

### 4、TreeMap ###

TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

### 5、小结 ###

一般情况下，我们用的最多的是HashMap,在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列.