死磕 java集合之LinkedHashMap源码分析

欢迎关注我的公众号“彤哥读源码”，查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

简介

linkedhashmap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，可以用来实现lru缓存策略。

linkedhashmap可以看成是 linkedlist + hashmap。

继承体系

linkedhashmap继承hashmap，拥有hashmap的所有特性，并且额外增加了按一定顺序访问的特性。

存储结构

我们知道hashmap使用（数组 + 单链表 + 红黑树）的存储结构，那linkedhashmap是怎么存储的呢？

通过上面的继承体系，我们知道它继承了hashmap，所以它的内部也有这三种结构，但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。

添加删除元素的时候需要同时维护在hashmap中的存储，也要维护在linkedlist中的存储，所以性能上来说会比hashmap稍慢。

源码解析

属性

/**
* 双向链表头节点 
*/
transient linkedhashmap.entry<k,v> head;

/**
* 双向链表尾节点 
*/
transient linkedhashmap.entry<k,v> tail;

/**
* 是否按访问顺序排序 
*/
final boolean accessorder;

（1）head

双向链表的头节点，旧数据存在头节点。

（2）tail

双向链表的尾节点，新数据存在尾节点。

（3）accessorder

是否需要按访问顺序排序，如果为false则按插入顺序存储元素，如果是true则按访问顺序存储元素。

内部类

// 位于linkedhashmap中
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);
    }
}

// 位于hashmap中
static class node<k, v> implements map.entry<k, v> {
    final int hash;
    final k key;
    v value;
    node<k, v> next;
}

存储节点，继承自hashmap的node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。

构造方法

public linkedhashmap(int initialcapacity, float loadfactor) {
    super(initialcapacity, loadfactor);
    accessorder = false;
}

public linkedhashmap(int initialcapacity) {
    super(initialcapacity);
    accessorder = false;
}

public linkedhashmap() {
    super();
    accessorder = false;
}

public linkedhashmap(map<? extends k, ? extends v> m) {
    super();
    accessorder = false;
    putmapentries(m, false);
}

public linkedhashmap(int initialcapacity,
                     float loadfactor,
                     boolean accessorder) {
    super(initialcapacity, loadfactor);
    this.accessorder = accessorder;
}

前四个构造方法accessorder都等于false，说明双向链表是按插入顺序存储元素。

最后一个构造方法accessorder从构造方法参数传入，如果传入true，则就实现了按访问顺序存储元素，这也是实现lru缓存策略的关键。

afternodeinsertion(boolean evict)方法

在节点插入之后做些什么，在hashmap中的putval()方法中被调用，可以看到hashmap中这个方法的实现为空。

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

protected boolean removeeldestentry(map.entry<k,v> eldest) {
    return false;
}

evict，驱逐的意思。

（1）如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用hashmap.removenode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；

（2）hashmap.removenode()从hashmap中把这个节点移除之后，会调用afternoderemoval()方法；

（3）afternoderemoval()方法在linkedhashmap中也有实现，用来在移除元素后修改双向链表，见下文；

（4）默认removeeldestentry()方法返回false，也就是不删除元素。

afternodeaccess(node<k,v> e)方法

在节点访问之后被调用，主要在put()已经存在的元素或get()时被调用，如果accessorder为true，调用这个方法把访问到的节点移动到双向链表的末尾。

void afternodeaccess(node<k,v> e) { // move node to last
    linkedhashmap.entry<k,v> last;
    // 如果accessorder为true，并且访问的节点不是尾节点
    if (accessorder && (last = tail) != e) {
        linkedhashmap.entry<k,v> p =
                (linkedhashmap.entry<k,v>)e, b = p.before, a = p.after;
        // 把p节点从双向链表中移除
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        
        if (a != null)
            a.before = b;
        else
            last = b;
        
        // 把p节点放到双向链表的末尾
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // 尾节点等于p
        tail = p;
        ++modcount;
    }
}

（1）如果accessorder为true，并且访问的节点不是尾节点；

（2）从双向链表中移除访问的节点；

（3）把访问的节点加到双向链表的末尾；（末尾为最新访问的元素）

afternoderemoval(node<k,v> e)方法

在节点被删除之后调用的方法。

void afternoderemoval(node<k,v> e) { // unlink
    linkedhashmap.entry<k,v> p =
            (linkedhashmap.entry<k,v>)e, b = p.before, a = p.after;
    // 把节点p从双向链表中删除。
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

经典的把节点从双向链表中删除的方法。

get(object key)方法

获取元素。

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

如果查找到了元素，且accessorder为true，则调用afternodeaccess()方法把访问的节点移到双向链表的末尾。

总结

（1）linkedhashmap继承自hashmap，具有hashmap的所有特性；

（2）linkedhashmap内部维护了一个双向链表存储所有的元素；

（3）如果accessorder为false，则可以按插入元素的顺序遍历元素；

（4）如果accessorder为true，则可以按访问元素的顺序遍历元素；

（5）linkedhashmap的实现非常精妙，很多方法都是在hashmap中留的钩子（hook），直接实现这些hook就可以实现对应的功能了，并不需要再重写put()等方法；

（6）默认的linkedhashmap并不会移除旧元素，如果需要移除旧元素，则需要重写removeeldestentry()方法设定移除策略；

（7）linkedhashmap可以用来实现lru缓存淘汰策略；

彩蛋

linkedhashmap如何实现lru缓存淘汰策略呢？

首先，我们先来看看lru是个什么鬼。lru，least recently used，最近最少使用，也就是优先淘汰最近最少使用的元素。

如果使用linkedhashmap，我们把accessorder设置为true是不是就差不多能实现这个策略了呢？答案是肯定的。请看下面的代码：

package com.coolcoding.code;

import java.util.linkedhashmap;
import java.util.map;

/**
 * @author: tangtong
 * @date: 2019/3/18
 */
public class lrutest {
    public static void main(string[] args) {
        // 创建一个只有5个元素的缓存
        lru<integer, integer> lru = new lru<>(5, 0.75f);
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        lru.put(4, 4);
        lru.put(5, 5);
        lru.put(6, 6);
        lru.put(7, 7);
    
        system.out.println(lru.get(4));
    
        lru.put(6, 666);
    
        // 输出: {3=3, 5=5, 7=7, 4=4, 6=666}
        // 可以看到最旧的元素被删除了
        // 且最近访问的4被移到了后面
        system.out.println(lru);
    }
}

class lru<k, v> extends linkedhashmap<k, v> {

    // 保存缓存的容量
    private int capacity;
    
    public lru(int capacity, float loadfactor) {
        super(capacity, loadfactor, true);
        this.capacity = capacity;
    }
    
    /**
    * 重写removeeldestentry()方法设置何时移除旧元素
    * @param eldest
    * @return 
    */
    @override
    protected boolean removeeldestentry(map.entry<k, v> eldest) {
        // 当元素个数大于了缓存的容量, 就移除元素
        return size() > this.capacity;
    }
}

---

欢迎关注我的公众号“彤哥读源码”，查看更多源码系列文章, 与彤哥一起畅游源码的海洋。