Java编程拾遗『LinkedHashMap』

在之前的文章，分别介绍过HashMap、TreeMap。HashMap就是普通的K-V存储数据结构，TreeMap在K-V存储数据结构的基础上添加了K-V之间按键值有序的特性。本篇文章来介绍一下，另一种特殊的K-V存储数据结构LinkedHashMap。LinkedHashMap是HashMap的子类，但可以保持元素按插入或访问有序（默认是按插入顺序有序）。LinkedHashMap继承关系如下：

LinkedHashMap是HashMap的子类，每个键值对都是通过之前讲HashMap的存储方式(数组 + 链表 + 红黑树)存储的，但同时内部各个键值对之间还有一个双向链表维护键值对的顺序。所以，HashMap除了键值对之间无序之外所有的特性，LinkedHashMap都有，比如存储方式、hash策略、扩容机制等。LinkedHashMap支持两种顺序，一种是插入顺序，另外一种是访问顺序。插入顺序是指，先添加的在前面，后添加的在后面，修改操作不影响顺序。访问顺序是指get/put操作，对一个键执行get/put操作后，其对应的键值对会移到双向链表末尾，所以，最末尾的是最近访问的，最开始的最久没被访问的，这种顺序就是访问顺序。

1. 调用示例

public static void main(String[] args) {
    /*默认构造函数，按照插入顺序有序*/
    System.out.println("按插入顺序有序：");
    Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*按插入顺序有序时，put修改操作，并不会改变顺序*/
    linkedHashMap.put(3, "e");

    Iterator iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    /*调用
    * public LinkedHashMap(int initialCapacity,
                           float loadFactor,
                           boolean accessOrder)
      构造函数，指定accessOrder为true时，可以按照访问顺序有序
    * */
    System.out.println("按访问顺序有序：");
    linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*1 -> 2 -> 3 -> 4*/

    linkedHashMap.get(2);//2被访问了，移动到内部双向链表末尾
    /*1 -> 3 -> 4 -> 2*/

    linkedHashMap.get(4);//4被访问了，移动到内部双向链表末尾
    /*1 -> 3 -> 2 -> 4*/

    linkedHashMap.put(1, "e");//1被访问(put)了，移动到内部双向链表末尾
    /*3 -> 2 -> 4 -> 1*/

    linkedHashMap.put(5, "f");//插入5
    /*3 -> 2 -> 4 -> 1 -> 5*/

    iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

运行结果：

按插入顺序有序：
1=a
2=b
3=e
4=d
按访问顺序有序：
3=c
2=b
4=d
1=e
5=f

1.1 按插入有序使用场景

LinkedHashMap经常用来处理一些数据，接受一些键值对作为输入，处理，然后输出，输出时希望跟插入的顺序保持一致。比如从数据库查询数据放到内存时，已经使用SQL的order by语句让数据库对数据排序，在数据输入有序的前提下，希望通过Map存储查询结果，并且保持顺序输出，这时候就没必要使用TreeMap了，效率比LinkedHashMap低(TreeMap直接使用红黑树存储，LinkedHashMap使用Hash表)，直接使用LinkedHashMap也能达到相同的排序目标。

1.2 按访问有序使用场景

上面的例子，已经讲了按访问有序的示例。那么按访问有序在开发中有什么使用场景？最常见的一个用法就是通过LinkedHashMap的按访问有序实现LRU(Least Recently Used—最近最久未使用)算法。

缓存，原始意义是指访问速度比一般随机存取存储器（RAM）快的一种RAM，通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。当CPU处理数据时，它会先到缓存中去寻找，如果数据因之前的操作已经读取而被暂存其中，就不需要再从随机存取存储器（Main memory）中读取数据——由于CPU的运行速度一般比主内存的读取速度快，主存储器周期（访问主存储器所需要的时间）为数个时钟周期。因此若要访问主内存的话，就必须等待数个CPU周期从而造成浪费。

CPU的缓存曾经是用在超级计算机上的一种高级技术，不过现今计算机上使用的的AMD或Intel微处理器都在芯片内部集成了大小不等的数据缓存和指令缓存，通称为L1缓存；而比L1更大容量的L2缓存曾经被放在CPU外部（主板或者CPU接口卡上），但是现在已经成为CPU内部的标准组件；更昂贵的CPU会配备比L2缓存还要大的L3缓存（level 3 On-die Cache第三级高速缓冲存储器）。L1容量缓存非常小、价格非常贵、读取速度快，三级缓存容量会大一些、便宜一些、读取速度也慢一些。

如今缓存的概念已被扩充，不仅在CPU和主内存之间有Cache，而且在内存和硬盘之间也有Cache（磁盘缓存），乃至在硬盘与网络之间也有某种意义上的Cache──称为Internet临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称之为Cache。

主存容量远大于CPU缓存，磁盘容量远大于主存，因此无论是哪一层次的缓存都面临一个同样的问题：当容量有限的缓存的空闲空间全部用完后，又有新的内容需要添加进缓存时，如何挑选并舍弃原有的部分内容，从而腾出空间放入这些新的内容。解决这个问题的算法有几种，如最久未使用算法（LFU）、先进先出算法（FIFO）、最近最少使用算法（LRU）、非最近使用算法（NMRU）等，这些算法在不同层次的缓存上执行时拥有不同的效率和代价，需根据具体场合选择最合适的一种。而本文讲的LinkedHashMap的按访问有序，就可以很容易的实现LRU算法。

LinkedHashMap中存在一个protected方法，如下：

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

这个方法用于插入键值对后调用，如果返回true，则会清除LinkedHashMap中“最老”(最久未访问)的键值对，LinkedHashMap的实现总是返回false，所以无论何时插入键值对，都不会对之前的键值对进行清除。所以如果要实现实现LRU算法，只要继承LinkedHashMap类，并按照具体策略重写此方法即可，如下：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxSize;

    public LRUCache(int maxSize){
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        lruCache.put(1, "a");
        lruCache.put(2, "b");
        lruCache.put(3, "c");
        //访问1->a
        //key顺序为：2 -> 3 -> 1
        System.out.println(lruCache.get(1));

        //插入一个新键值对，理论上，由于超过LruCache的maxSize了，所以会删除最老的键值对
        //插入后，删除最老键值对前，key顺序：2 -> 3 -> 1 -> 4
        //所以最老的键值对，key为2
        lruCache.put(4, "d");

        System.out.println(lruCache);
    }
}

运行结果：

a
{3=c, 1=a, 4=d}

限定缓存容量为3，先后添加了4个键值对，最久没被访问的key是”2″，会被删除。

2. 方法说明

LinkedHashMap的设计很巧妙，使用了钩子方法的设计模式，在HashMap中定义了钩子方法，然后再LinkedHashMap中实现，在钩子方法中保证键值对之间的顺序。

2.1 构造函数

2.2 Map接口

除了构造函数之外的方法，全部继承自HashMap，但是针对个别方法，进行了重写。

3. 实现源码分析

3.1 LinkedHashMap类声明

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
	/**
     * 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);
        }
    }

    /**
     * 双向链表头(最老的元素)
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 双向链表尾(最新的元素)
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * LinkedHashMap访问顺序:
     * true: 按访问有序
     * false: 按插入有序
     * @serial
     */
    final boolean accessOrder;

    //成员方法

}  

相比于HashMap，LinkedHashMap中的每一个节点Entry除了有一个next指针(继承自HashMap.Node)外，还有一个指向当前Entry前驱和后继的before、after指针。除此之外，还添加了一个成员变量accessOrder，表示LinkedHashMap访问顺序。LinkedHashMap可以说是通过数组 + 链表 + 红黑树 + 双向链表实现的。假设hash算法就是简单的用key mod 一下表的大小（也就是数组的长度），其中的哈希桶数组table的size=4，负载因子loadFactor=1，通过put顺序添加如下四个元素（5、1、9、3为键值对的key），则LinkedHashMap存储结构如下：

由上图可以清楚的看到，LinkedHashMap = HashMap + before&after构成的双向链。当LinkedHashMap发生改变时，当前双向链表结构也会发生改变，保证head始终指向“最老”的节点，tail始终指向“最新”的节点。比如按访问有序前提下，现有LinkedHashMap结构如上图，这时候代码调用了linkedHashMap.get(1)操作，那么节点1会移动到双向链表的尾部，tail指向节点1，节点5的后继变为节点9。下面讲实现时，会详细讲解。

3.2 构造函数

/*
* 调用HashMap默认构造函数初始化HashMap，访问顺序按插入有序
*/
public LinkedHashMap() {
    super();
    accessOrder = false;
}

/*
* 指定HashMap初始容量，访问顺序按插入有序
*/
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

/*
* 通过Map初始化LinkedHashMap
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    //调用HashMap默认构造函数初始化HashMap
    super();
    accessOrder = false;
    //通过调用putMapEntries方法，将Map中的键值对插入到默认构造函数构造的HashMap中
    //putMapEntries方法第二个参数控制插入后是否进行检查，清除最老元素
    //按插入有序，所以在插入元素后，不用考虑是否需要删除最老元素，直接赋值false即可
    putMapEntries(m, false);
}

/*
* 初始化一定容量，负载因子的HashMap，并指定LinkedHashMap的访问顺序
* 这个构造函数也是唯一一个能够指定访问顺序的构造函数
*/
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

3.3 put操作

LinkedHashMap类中没有重写HashMap的put和putAll，那么它是怎么实现上面讲的双向链表元素顺序的？我们可能有两个显而易见的疑问，第一LinkedHashMap的节点类型是内部类LinkedHashMap.Entry而非HashMap.Node，LinkedHashMap内部的Entry节点是如何初始化出来的；第二LinkedHashMap没有重写put/putAll方法，是通过什么方式维护双向链表的；

第一个问题，LinkedHashMap内部的Entry节点是如何实例化出来的。在之前讲HashMap的文章中，我们讲过在putVal方法中，通过调用newNode方法，构建一个待插入的Node对象，而LinkedHashMap重写了newNode方法，构建一个带插入的LinkedHashMap.Entry对象。在HashMap类中，newNode方法被putVal方法调用，而putVal方法会在put及putAll方法中调用，所以当LinkedHashMap对象调用put或putAll方法时，就能保证插入的节点是LinkedHashMap.Entry对象。

第二个问题，LinkedHashMap对象在调用put或putAll方法后，是如何保证双向链表顺序的。LinkedHashMap.newNode方法中，调用了一个linkNodeLast的linkNodeLast方法，新节点链接在内部双向链表的尾部。下面结合源码来看一下：

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2：计算index，并对null做处理 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4：判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5：该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key,value,null);
                     //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);
                    break;
                }
                 // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                           break;
                p = e;
            }
        }
        
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;
    // 6：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

上面是HashMap的put方法，在putVal方法中，如果需要插入节点，则调用newNode方法生成待插入的节点对象。LinkedHashMap类中重写的newNode如下：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    //调用LinkedHashMap.Entry的构造函数，生成Entry节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //调整双向链表结构，是新插入的节点p插入到双向链表尾部
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    //tail指针移到p节点
    tail = p;
    //如果插入p节点之前链表为null，则讲head指针指向新插入的节点p
    if (last == null)
        head = p;
    else {
        //讲新插入的节点p插入到双向链表尾部
        p.before = last;
        last.after = p;
    }
}

这就是为什么调用HashMap的put/putAll方法，可以生成LinkedHashMap.Entry类型的节点插入，同时可以维护双向链表顺序的原因，如下图所示：

 下面看一下HashMap类putVal方法两个比较“别致”的方法afterNodeAccess和afterNodeInsertion。这两个方法是钩子方法，在HashMap中并没有具体实现，只是一个空方法，LinkedHashMap中重写了这两个方法。

• afterNodeAccess：负责当LinkedHashMap按访问有序时，节点被访问后，调整双向链表结构，讲最新访问的节点移动到双向链表的尾部。
• afterNodeInsertion：负责在插入节点后检查是否需要清除最老的节点(就是上文讲的实现LRU)

LinkedHashMap中afterNodeAccess实现如下：

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    //如果LinkedHashMap按访问有序，并且刚被访问的节点e不是双向链表尾节点，则调整双向链表
    if (accessOrder && (last = tail) != e) {
        //p为刚被访问的节点，b为p的前驱节点，a为p的后继节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //首先将p的后继指针断开
        p.after = null;
        //如果p为双向链表头结点，则将head指针指向p的后继节点a
        if (b == null)
            head = a;
        else
            //如果p不是双向链表头结点，则将p的前驱节点的后继指针指向p的后继节点a
            b.after = a;
        //如果p的后继节点a不为null，则将a的前驱指针指向p的前驱节点b
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            //将p节点连接到双向链表尾部
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeAccess除了在HashMap类的put方法中调用外，在replace、merge、compute方法中也有调用，保证按访问有序情况下，最后被访问的节点会被移到双向链表尾部。

LinkedHashMap中afterNodeInsertion实现如下：

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    //如果evit为tur(需要删除最老元素)，并且双向链表不为null，并且removeEldestEntry方法返回true
    //则清除head指向的节点(最老的节点)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

这里回头看一下本文开头讲的LRUCache类，重写了removeEldestEntry方法，因为LinkedHashMap中默认返回false，如下：

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

如果想要实现LRU，子类中要重写该方法。

3.4 remove操作

LinkedHashMap也没有重写remove()方法，remove操作是通过调用HashMap的remove方法实现的，根据上节讲的LinkedHashMap要维护双向链表，那么是不是HashMap的remove方法中定义了钩子方法，然后在LinkedHashMap中实现，删除双向链表中的相应节点，答案是肯定的。

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

afterNodeRemoval就是钩子方法，LinkedHashMap中实现如下：

/*
* LinkedHashMap删除节点后，将节点从双向链表中移除
*/
void afterNodeRemoval(Node<K,V> e) {
    //当前删除的节点是p，b是删除节点的前驱节点，a是删除节点的后继节点1
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //首先将p的前驱指针和后继指针清空
    p.before = p.after = null;
    //如果p为双向链表头结点，则直接将head指针指向p的后继节点a
    if (b == null)
        head = a;
    //如果p不是双向链表头结点，则将p的前驱节点的后继指针指向p的后继节点a
    else
        b.after = a;
    //如果p为双向链表尾节点，则直接将tail指针指向p的前驱节点b
    if (a == null)
        tail = b;
    //如果p不是双向链表的尾节点，则将p的后继节点的前驱指针指向p的前驱节点b
    else
        a.before = b;
}

 也就是讲当LinkedHashMap删除节点，是通过调用HashMap的remove方法实现的，在HashMap删除节点后，会调用afterNodeRemoval方法，该方法在LinkedHashMap中实现，讲待删除节点从双向链表中移除。

3.5 get方法

LinkedHashMap中重写了HashMap的get方法，如果LinkedHashMap按访问有序，则在访问后会调用上面讲的afterNodeAccess方法，调整双向链表结构。实现如下：

public V get(Object key) {
    Node<K,V> e;
    //调用HashMap的getNode方法，获取key对应的Node节点
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //如果LinkedHashMap按访问有序，则将刚访问的节点e，移动到双向链表的尾部
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

同样，getOrDefault的实现思想也是一样的，如下：

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

其实对比HashMap的实现，可以发现，LinkedHashMap其实就是比HashMap多了个如果按访问有序，则维护双向链表的逻辑。

3.6 containsKey方法

LinkedHashMap中没有重写containsKey方法，完全复用HashMap的containsKey方法，因为判断key是否存在，不涉及双向链表的维护，且HashMap的containsKey方法的时间复杂度为O(1)，效率较高，没必要重写。

3.7 containsValue方法

HashMap中判断value是否存在，是通过遍历hash桶数组的每个元素，然后依次判断链表/红黑树中是否存在相等的value得到的，如下：

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

两层for循环，时间复杂度应该在O(n) ~ O(n^2)之间。虽然判断value在Map中是否存在也不涉及双向链表的改变，但LinkedHashMap依然没有采用这种方式，因为LinkedHashMap内部维护了一个双向链表，直接通过双向链表访问HashMap所有节点，依次判断即可，时间复杂度为O(n)。LinkedHashMap中重写的containsValue方法如下：

public boolean containsValue(Object value) {
    //遍历双向链表，判断value是否存在
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

4. LinkedHashMap特点

• LinkedHashMap是基于HashMap实现的，除了HashMap键值对之间无序这一特点之外的特点，LinkedHashMap都有
• LinkedHashMap可以保证插入有序或访问有序，访问有序可以很方便地实现LRU算法

参考链接：

1. Java API源码
2. 《Java编程的逻辑》