学习笔记Java集合5-LinkedHashMap源码分析

共计 4416 个字符，预计需要花费 12 分钟才能阅读完成。

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

LinkedHashMap 可以看成是 LinkedList + HashMap。

LinkedHashMap 继承 HashMap，拥有 HashMap 的所有特性，并且额外增加的按一定顺序访问的特性

我们知道 HashMap 使用（数组 + 单链表 + 红黑树）的存储结构，通过上面的继承体系，我们知道 LinkedHashMap 继承了 Map，所以它的内部也有这三种结构，但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。

添加删除元素的时候需要同时维护在 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 缓存策略的关键。

在节点插入之后做些什么，在 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 为 true，且头节点不为空，且确定移除最老的元素，那么就调用 HashMap.removeNode() 把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；
HashMap.removeNode() 从 HashMap 中把这个节点移除之后，会调用 afterNodeRemoval() 方法；
afterNodeRemoval() 方法在 LinkedHashMap 中也有实现，用来在移除元素后修改双向链表，见下文；
默认 removeEldestEntry() 方法返回 false，也就是不删除元素。

在节点访问之后被调用，主要在 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;
    }
}

如果 accessOrder 为 true，并且访问的节点不是尾节点；
从双向链表中移除访问的节点；
把访问的节点加到双向链表的末尾；（末尾为最新访问的元素）

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


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

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

获取元素。

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() 方法把访问的节点移到双向链表的末尾。

LinkedHashMap 继承自 HashMap，具有 HashMap 的所有特性；
LinkedHashMap 内部维护了一个双向链表存储所有的元素；
如果 accessOrder 为 false，则可以按插入元素的顺序遍历元素；
如果 accessOrder 为 true，则可以按访问元素的顺序遍历元素；
LinkedHashMap 的实现非常精妙，很多方法都是在 HashMap 中留的钩子（Hook），直接实现这些 Hook 就可以实现对应的功能了，并不需要再重写 put() 等方法；
默认的 LinkedHashMap 并不会移除旧元素，如果需要移除旧元素，则需要重写 removeEldestEntry() 方法设定移除策略；
LinkedHashMap 可以用来实现 LRU 缓存淘汰策略；

LRU，Least Recently Used，最近最少使用，也就是优先淘汰最近最少使用的元素。

如果使用 LinkedHashMap，我们把 accessOrder 设置为 true 就差不多能实现这个策略了:


package com.coolcoding.code;

import java.util.LinkedHashMap;
import java.util.Map;

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

简介

继承体系

存储结构

源码解析

属性

内部类

构造方法

afterNodeInsertion(boolean evict) 方法

afterNodeAccess(Node<K,V> e) 方法

afterNodeRemoval(Node<K,V> e) 方法

get(Object key) 方法

总结

LinkedHashMap 实现 LRU 缓存淘汰策略

Just My Socks（注册教程内含优惠码）