JDK源码分析系列--LinkedHashMap

引言

前面已对java.util.HashMap的源码做了详细的分析。HashMap底层采用哈希表，保证了put和get操作的高效。但也导致了遍历操作是无序的。java.util.LinkedHashMap则是在HashMap的基础上，维护了一条双向链表，记录了节点的插入顺序。使遍历操作可以按插入顺序进行。本文通过源码解析的方式，对LinkedHashMap的有序性进行说明。

数据结构

LinkedHashMap继承自HashMap，在保持数组+链表+红黑树的结构下，还维护着一条双向链表，可以记录节点插入顺序。

红色连线表示双向链表

LinkedHashMap数据结构的最小单元是java.util.LinkedHashMap.Entry，LinkedHashMap.Entry在HashMap.Node的基础上，增加了指向前后节点的引用before和after。LinkedHashMap.Entry源码如下：

static class Entry<K,V> extends HashMap.Node<K,V> {
    // 指向前、后节点，记录了插入顺序
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

成员变量

指向双向链表头节点

1	transient LinkedHashMap.Entry<K,V> head;

指向双向链表尾节点

1	transient LinkedHashMap.Entry<K,V> tail;

是否改变访问顺序。开启这个，每次更新或查询节点都会将该节点移至双向链表末尾

1	final boolean accessOrder;

构造方法

所有LinkedHashMap构造方法内部都显示调用了父类HashMap构造方法。

构造一

默认accessOrder=false

public LinkedHashMap() {
    super();
    accessOrder = false;
}

构造二

指定数组初始容量，默认accessOrder=false

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

构造三

指定数组初始容量和加载参数，默认accessOrder=false

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

构造四

指定数组初始容量、加载参数和accessOrder

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

构造五

通过Map构建LinkedHashMap，默认accessOrder=false

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

成员方法

LinkedHashMap大部分还是沿用了HashMap的方法逻辑，通过对部分方法的改造，巧妙加入了链表的思想。

newNode方法

在HashMap#putVal方法中，通过newNode方法创建节点。

LinkedHashMap重写了newNode方法，使创建的节点类型为LinkedHashMap.Entry

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

newNode内部调用了linkNodeLast方法。

linkNodeLast方法

给head，tail，before，after引用赋值，形成双向链表。通过这种方式，使添加的节点有了顺序

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    // 尾结点指向p
    tail = p;
    // 说明只有一个节点
    if (last == null)
        // 头节点也指向p
        head = p;
    else { // 有不止一个节点
        // 把p放到末尾，和前一个节点互相指向
        p.before = last;
        last.after = p;
    }
}

afterNodeAccess方法

在putVal方法中，如果是更新value的情况，会调用一次afterNodeAccess方法。

LinkedHashMap实现了afterNodeAccess方法，作用是：

每次更新节点后，都会将该节点移动到双向链表的末尾。

源码如下：

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    // accessOrder开启且当前节点不是尾节点
    if (accessOrder && (last = tail) != e) {
        // 当前节点p；前节点b；后节点a
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 将当前节点移动到末尾，after指向null
        p.after = null;
        // 说明p是头节点
        if (b == null)
            // 将a设为头节点
            head = a;
        else // p是中间节点
            // 让a作为b的后节点
            b.after = a;
        
        if (a != null)
            // a与b互相指向
            a.before = b;
        else
            // p不是尾节点，且a为0，说明链表还未初始化，b一定为null
            last = b;
        
        if (last == null)
            // 链表未初始化，只有p一个节点，作为头节点
            head = p;
        else {
            // p与尾结点互相指向
            p.before = last;
            last.after = p;
        }
        // p作为尾节点
        tail = p;
        ++modCount;
    }
}

注意：

accessOrder默认为false，需要手动开启。

总结起来，该方法处理了四种情况：

e为尾节点，则不需要任何操作
e为头节点，则b为null，需要将a设为头节点，e设为尾结点
e为中间节点，则需要连接b和a，e设为尾结点
链表未初始化，则b，a都为null，e既是头节点也是尾结点

afterNodeInsertion方法

在putVal方法中，插入新的节点后，调用了afterNodeInsertion方法

LinkedHashMap实现了该方法，作用是：

在插入新的节点后，移除双向链表的头节点。

源码如下：

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry方法

注意removeEldestEntry方法默认返回false，需要重新实现。

1
2
3

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

示例

重写removeEldestEntry方法，以满足：使map中节点数不超过3，超过自动移除

public static void main(String[] args) {
    HashMap<String, String> map = new MyMap<>();
    for (int i = 1; i < 6; i++) {
        String s = String.valueOf(i);
        map.put(s, s);
        System.out.println(map);
    }
}

static class MyMap<K, V> extends LinkedHashMap<K, V>{
    // 节点数不超过3
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > 3;
    }
    public MyMap (){
        super();
    }
}

结果：

{1=1}
{1=1, 2=2}
{1=1, 2=2, 3=3}
{2=2, 3=3, 4=4}
{3=3, 4=4, 5=5}

再配合afterNodeAccess方法，将更新或查询的节点移动到链表末尾，就可以实现按使用频率淘汰旧数据的逻辑

afterNodeRemoval方法

在HashMap#removeNode方法中，删除节点后，会调用一次afterNodeRemoval方法。

LinkedHashMap实现了该方法，作用是：

在删除节点后，调整双向链表相关的引用。具体表现为：

首先移除e的前后引用
如果e是中间节点，则直接连接a、b节点
如果e是头节点，则使head指向a节点
如果e是尾节点，则使after指向b节点

void afterNodeRemoval(Node<K,V> e) {
    // 被删除节点p，前节点b，后节点a
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // p的前后引用置为null
    p.before = p.after = null;
    
    // 说明p是头节点
    if (b == null)
        // 头节点指向a
        head = a;
    else
        // b指向a
        b.after = a;
    
    // 说明p是尾节点
    if (a == null)
        // 尾节点指向b
        tail = b;
    else
        // a指向b
        a.before = b;
}

get方法

get方法与 HashMap#get 方法基本相同，区别是如果accessOrder=true，会调用afterNodeAccess将该节点移动到双向链表末尾。

public V get(Object key) {
    Node<K,V> e;
    // 调用父类getNode方法
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

keySet方法

LinkedHashMap重写了keySet方法，使遍历按节点插入顺序进行。源码如下：

keySet方法返回LinkedHashMap.LinkedKeySet对象

// 初次调用，会创建一个LinkedKeySet对象
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new LinkedKeySet();
        keySet = ks;
    }
    return ks;
}

LinkedKeySet类

iterator方法返回一个LinkedHashMap.LinkedKeyIterator迭代器对象

final class LinkedKeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); 
    
    // 重写了iterator方法，创建LinkedKeyIterator对象
    public final Iterator<K> iterator() {
        return new LinkedKeyIterator();
    }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
   
    // Java8流式编程。与HashMap不同，是按链表遍历
    public final void forEach(Consumer<? super K> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

LinkedKeyIterator类

next方法内部调用了LinkedHashMap.LinkedHashIterator#nextNode方法

final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K> {
    // 重写了next方法，调用nextNode方法
    public final K next() { 
        return nextNode().getKey(); 
    }
}

LinkedHashIterator类

LinkedHashIterator初始化时会使next指向head节点，每调用一次nextNode方法，会使next在双向链表上移动一次。

可以看到，与HashMap.HashIterator#nextNode相比，LinkedHashMap.LinkedHashIterator#nextNode的指针是在双向链表上移动，既保留了数据插入的顺序，也提升了遍历效率。

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;
    
    // 初始化LinkedHashIterator，使next指向头节点
    LinkedHashIterator() {
        next = head;
        expectedModCount = modCount;
        current = null;
    }
    
    // 直到next为null
    public final boolean hasNext() {
        return next != null;
    }
    
    // 每次调用，都会使next在双向链表上移动一次
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after;
        return e;
    }
}

values和entrySet方法与keySet类似，这里不再展开