LinkedHashMap

1 LinkedHashMap是什么？

LinkedHashMap直接继承HashMap类，其节点元素为Entry<K,V>，直接继承HashMap.Node<K,V>。UML类图关系如下：

LinkedHashMap类关系图.jpg

LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。LinkedHashMap实现与HashMap的不同之处在于维护着一个运行于所有条目的双向链表。

LinkedHashMap结构.png

Entry元素除了有next 指针，还有before，after指针指定前后结点的关系。新增了一个header元素，作为entry 双向链表的头结点。

2 LinkedHashMap实现

LinkedHashMap是HashMap的子类，它可以实现对容器内Entry的存储顺序和对Entry的遍历顺序保持一致。为了实现这个功能，LinkedHashMap内部使用了一个Entry类型的双向链表，用这个双向链表记录Entry的存储顺序。当需要对该Map进行遍历的时候，实际上是遍历的是这个双向链表。

LinkedHashMap内部使用的LinkedHashMap.Entry类继承自 Map.Entry类，在其基础上增加了LinkedHashMap.Entry类型的两个字段before和after，分别用来指向前面的Entry对象和后面的Entry对象。

LinkedHashMap的内部结构.png

2.1 put数据

将下面数据存放到LinkedHashMap中，来了解内部双向链表是怎样构造的：

LinkedHashMap linkedHashMap = new LinkedHashMap();
linkedHashMap.put("name","louis");
linkedHashMap.put("age","24");
linkedHashMap.put("sex","male");

上述的代码除了会将对应的Entry对象放置到在Entry[] table 表示的数组链表中外，还会将该Entry对象添加到其内部维护的双向链表中。对应的LinkedHashMap内部的双向链表变化如下：

LinkedHashMap内部的双向链表变化.png

2.2 遍历数据

2.2.1 按插入顺序遍历

对LinkedHashMap进行遍历的策略：从 header.after 指向的Entry对象开始，然后一直沿着此链表遍历下去，直到某个entry.after == header 为止，完成遍历。由此，就可以保证遍历LinkedHashMap内元素的顺序，就是Entry插入到LinkedHashMap中的顺序。

Iterator<Map.Entry> iterator= linkedHashMap.entrySet().iterator();
while(iterator.hasNext()){
    Map.Entry entry = iterator.next();
    System.out.println(entry.getKey()+":"+entry.getValue());
}

将上面代码中定义的linkedHashMap 遍历输出，会发现遍历的顺序跟插入的顺序完全一致。

2.2.2 Get读取顺序

如果LinkedHashMap的这个Get读取遍历顺序开启，那么，当我们在LinkedHashMap上调用get(key) 方法时，会导致内部 key对应的Entry在双向链表中的位置移动到双向链表的最后。

//默认情况下LinkedHashMap的遍历模式是插入模式，如果想显式地指定为get读取模式，那么要将其构造方法的参数置为true
LinkedHashMap linkedHashMap = new LinkedHashMap(16, (float) 0.75,true);

linkedHashMap.put("name","louis");
linkedHashMap.put("age","24");
linkedHashMap.put("sex","male");
linkedHashMap.get("name");//get()方法调用，导致对应的entry移动到双向链表的最后位置

Iterator<Map.Entry> iterator= linkedHashMap.entrySet().iterator();

while(iterator.hasNext()){
    Map.Entry entry = iterator.next();
    System.out.println(entry.getKey()+":"+entry.getValue());
}

上面代码运行后的，双向链表的变化如下所示：

get读取顺序.png

3 源码分析

针对JDK1.7，Jdk1.8的实现方式改变；

3.1 初始化

@Override
void init() {
    // 创建了一个hash=-1，key、value、next都为null的Entry
    header = new Entry<>(-1, null, null, null);
    // 让创建的Entry的before和after都指向自身，注意after不是之前提到的next
    // 其实就是创建了一个只有头部节点的双向链表
    header.before = header.after = header;
}

3.2 存储

LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。

void addEntry(int hash, K key, V value, int bucketIndex) {    
    // 调用create方法，将新元素以双向链表的的形式加入到映射中。    
    createEntry(hash, key, value, bucketIndex);    
    
    // 删除最近最少使用元素的策略定义    
    Entry<K,V> 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) {    
    HashMap.Entry<K,V> old = table[bucketIndex];    
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);    
    table[bucketIndex] = e;    
    // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。    
    e.addBefore(header);    
    size++;    
}

private void addBefore(Entry<K,V> existingEntry) {    
    after  = existingEntry;    
    before = existingEntry.before;    
    before.after = this;    
    after.before = this;    
}

这四行代码是关键，改变链表指向，不明白自己画图试验下。

3.3 读取

LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断排序模式 accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

public V get(Object key) {    
    // 调用父类HashMap的getEntry()方法，取得要查找的元素。    
    Entry<K,V> e = (Entry<K,V>)getEntry(key);    
    if (e == null)    
        return null;    
    // 记录访问顺序。    
    e.recordAccess(this);    
    return e.value;    
}

void recordAccess(HashMap<K,V> m) {    
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;    
    // 如果定义了LinkedHashMap的迭代顺序为访问顺序，    
    // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。    
    if (lm.accessOrder) {    
        lm.modCount++;    
        remove();    
        addBefore(lm.header);    
    }    
}

/**
* Removes this entry from the linked list.
*/
private void remove() {
    before.after = after;
    after.before = before;
}

4 LinkedHashMap应用

LinkedHashMap的顺序访问非常适合构建LRU缓存。LinkedHashMap提供了 removeEldestEntry(Map.Entry<K,V> eldest)方法，在将新条目插入到映射后，put和 putAll将调用此方法。

public class LRUCache extends LinkedHashMap {
    private static final long serialVersionUID = 1L;
    protected int maxElements;
    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {
        return size() > maxElements;
    }   
}

参考资料：

[1] HashMap、LinkedHashMap元素遍历机制探讨 ★
[2] LinkedHashMap的实现原理详解
[3] 图解LinkedHashMap原理 ★