简介#

LinkedHashMap 是 Java 提供的一个集合类，它继承自 HashMap，并在 HashMap 基础上维护一条双向链表，使得具备如下特性:

1. 支持遍历时会按照插入顺序有序进行迭代。
2. 支持按照元素访问顺序排序,适用于封装 LRU 缓存工具。
3. 因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。

LinkedHashMap 逻辑结构如下图所示，它是在 HashMap 基础上在各个节点之间维护一条双向链表，使得原本散列在不同 bucket 上的节点、链表、红黑树有序关联起来。

使用示例#

public static void main(String[] args) {
    Map<String, Integer> m = new LinkedHashMap<>();

    m.put("hello", 5);
    m.put("lettle", 6666);
    m.put("dioxide", 233);
    m.put("c", 3434);

    for(Map.Entry<String, Integer> entry : m.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }
    System.out.println();

    m.remove("dioxide");

    for(Map.Entry<String, Integer> entry : m.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }
}

lettle:6666
c:3434
hello:5
dioxide:233

lettle:6666
c:3434
hello:5

public static void main(String[] args) {
    Map<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);		// 注意这里

    m.put("hello", 5);
    m.put("lettle", 6666);
    m.put("dioxide", 233);
    m.put("c", 3434);

    for(Map.Entry<String, Integer> entry : m.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }
    System.out.println();

    m.get("lettle");
    m.get("dioxide");

    for(Map.Entry<String, Integer> entry : m.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }
}

hello:5
lettle:6666
dioxide:233
c:3434

hello:5
c:3434
lettle:6666
dioxide:233

实现思路#

具体实现思路如下：

• 继承 LinkedHashMap;
• 构造方法中指定 accessOrder 为 true ，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素；
• 重写removeEldestEntry 方法，该方法会返回一个 boolean 值，告知 LinkedHashMap 是否需要移除链表首元素（缓存容量有限）。

什么是LinkedHashMap#

LinkedHashMap 是 Java 集合框架中 HashMap 的一个子类，它继承了 HashMap 的所有属性和方法，并且在 HashMap 的基础重写了 afterNodeRemoval、afterNodeInsertion、afterNodeAccess 方法。使之拥有顺序插入和访问有序的特性。

LinkedHashMap 如何按照插入顺序迭代元素?#

LinkedHashMap 按照插入顺序迭代元素是它的默认行为。LinkedHashMap 内部维护了一个双向链表，用于记录元素的插入顺序。因此，当使用迭代器迭代元素时，元素的顺序与它们最初插入的顺序相同。

如何实现LRU缓存#

将 accessOrder 设置为 true 并重写 removeEldestEntry 方法当链表大小超过容量时返回 true，使得每次访问一个元素时，该元素会被移动到链表的末尾。一旦插入操作让 removeEldestEntry 返回 true 时，视为缓存已满，LinkedHashMap 就会将链表首元素移除，由此我们就能实现一个 LRU 缓存。