LinkedHashMap那点事儿

是前面分析了 HashMap 源码，今天分析下 LinkedHashMap，废话不多说直接开始。

LinkedHashMap

众所周知，HashMap 里的元素是无序的。如果想按照一定的顺序，比如插入顺序来访问元素，就需要 LinkedHashMap 这个集合来实现了，LinkedHashMap 相较于 HashMap 最大的特点就是元素有序。

LinkedHashMap 的构造方法是基于 HashMap的，不同之处是多了 accessOrder 这一属性。

数据结构

LinkedHashMap 是数组+单向链表+双向链表+红黑树的结构（便于理解，没画红黑树，红黑树其实也是在双向链表里）。

图中表示，节点 A 和 B 和 D，E 和 C的 key 有 hash 冲突，节点顺序是 A->B->E->C->D

核心属性

/**
 * LinkedHashMap 双向链表的头节点
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * LinkedHashMap 双向链表的尾节点
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 排序策略 默认 false
 */
final boolean accessOrder;

注：accessOrder是 LinkedHashMap 的排序策略，默认是false，即按照插入顺序排序，设置为 true 表示按照访问顺序来排序，可在初始化 LinkedHashMap 时指定。

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(5,0.75f,true);
map.put(1,"A");
map.put(2,"B");
map.put(3,"C");
map.put(4,"D");
map.put(5,"E");
map.get(3);
System.out.println(map.toString());

控制台输出：

{1=A, 2=B, 4=D, 5=E, 3=C}

哪个元素最后被访问，则会被放置到末尾节点。

Entry

LinkedHashMap 中的节点是静态内部类 Entry，它是 HashMap节点 Node的子类。

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);
    }
}

可以看出Entry 节点继承了 HashMap 的节点 Node，保留了 Node 的单向链表特点，但自身拥有 before 和 after 两个属性，同时 LinkedHashMap 继承自 HashMap，所以 LinkedHashMap 的数据结构是 数组+单向链表+双向链表。

继承关系图：

常用方法

链表添加节点

nowNode(…)

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    //创建一个 LinkedHashMap 的 Entry 节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //将此节点放置双向链表末尾
    linkNodeLast(p);
    return p;
}

// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    //原末节点
    LinkedHashMap.Entry<K,V> last = tail;
    //新末节点
    tail = p;
    //判断添加节点前集合是空集合的话需要将新节点设置为 head
    if (last == null)
        head = p;
    else {
        //将新节点放置双向链表尾部
        p.before = last;
        last.after = p;
    }
}

put(…)

LinkedHashMap 的 put 方法实际是调用 HashMap 的 put() 方法（参照上篇文章 [HashMap那点事儿](link: http://zhengyk.cn/2018/07/14/java/HashMap/ ) ），不同的是在 HashMap 的 putVal() 方法中 afterNodeAccess()、afterNodeInsertion()方法是空方法，具体由 LinkedHashMap来实现，流程如下图：

HashMap 的 putVal 方法中：

if (e != null) { // put 的 key 已存在
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

当向 LinkedHashMap 中 put一个元素时，如果 key 已存在，除了覆盖 value外，LinkedHashMap 会调用afterNodeAccess() 方法，如果accessOrder 是 true，且被覆盖的元素节点不是 last 节点，那么需要移动该节点至双向链表末尾

afterNodeAccess()

void afterNodeAccess(Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeInsertion()

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根据条件判断是否移除最近最少被访问的头节点，因为后访问的元素在尾部
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
//LinkedHashMap 的此方法返回 false，所以 afterNodeInsertion()方法不会移除元素，我们重写此方法可以简单实现LRU算法，比如自己设计一个缓存集合。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

获取元素

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

LinkedHashMap 重写了 get() 方法，多了一步判断，如果是按照访问顺序来排序的话，每一次 get 元素，都会使该元素所在的节点移动至链表末尾。

总结

LinkedHashMap 在 HashMap 的基础上拓展了双向链表，在分析 LinkedHashMap 的源码时要先理解它的数据结构模型，结合模型去拆解、分析源码就会很简单。