LinkedHashMap 源码分析

简介

继承自 HashMap，并在 HashMap 基础上维护一条双向链表，使得具备如下特性:

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

更加注重插入顺序和访问顺序

访问顺序遍历

LinkedHashMap 定义了排序模式 accessOrder (boolean 类型，默认为 false)，访问顺序则为 true，插入顺序则为 false。

默认为 false，这样最符合直觉，若为 true 了之后，(会比较迷惑？)

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
map.put(4, "four");
map.put(5, "five");
//访问元素2,该元素会被移动至链表末端
map.get(2);
//访问元素3,该元素会被移动至链表末端
map.get(3);
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}
//OUT
1 : one
4 : four
5 : five
2 : two
3 : three

LRU 缓存

Least Recently Used，最近最少使用

继承LinkedHashMap

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

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);//默认`accessOrder` 为 true
        this.capacity = capacity;
    }

    /**
     * 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {//移除链表首元素的条件
        return size() > capacity;
    }
}

LRUCache<Integer, String> cache = new LRUCache<>(3);//缓存大小为3
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.put(4, "four");
cache.put(5, "five");
for (int i = 1; i <= 5; i++) {
    System.out.println(cache.get(i));
}
//OUT
null
null
three
four
five

• LinkedHashMap 的节点内部类 Entry 基于 HashMap 的基础上，增加 before 和 after 指针使节点具备双向链表的特性。
• HashMap 的树节点 TreeNode 继承了具备双向链表特性的 LinkedHashMap 的 Entry。

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);
	}
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  //略

}