LinkHashMap 与 LRU

数据结构与算法

Android 为我们提供了 LruCache 类，LruCache 提供了一种使用 LRU 缓存的数据结构，里面本质还是对 LinkedHashMap 的封装。如果你深入研究 LinkedHashMap 的实现原理，就会发现其中就用到了双向链表这种数据结构。LRU (Least Recently Used) 的意思就是近期最少使用算法，它的核心思想就是会优先淘汰那些近期最少使用的缓存对象。

LinkedHashMap

JDK 文档地址：https://docs.oracle.com/javase/9/docs/api/java/util/LinkedHashMap.html

通过查看 LinkedHashMap 的文档我们不难得出以下结论：

1、LinkedHashMap 继承自 HashMap，同时通过双向链表维持迭代元素的有序性（默认插入顺序迭代）

2、 如果在映射中重新插入键，则插入顺序不受影响（如果在调用 m.put (k, v) 前 m.containsKey (k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中）

3、 LinkedHashMap 这种结构很适合用来构建 LRU 缓存

4、由于底层是 HashMap，所以也支持 null Key

5、 由于增加了维护链接列表的开支，其性能很可能比 HashMap 稍逊一筹，不过迭代时间比 HashMap 快，因为 HashMap 需要迭代 table 中的 null，而 LinkedHashMap 直接迭代链表就行

6、底层是 HashMap，所以线程也不安全

构造方法

构造方法一共有 5 个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//true 表示访问顺序、 false 表示插入顺序 
final boolean accessOrder;

// 默认插入顺序 
public LinkedHashMap() {
    super();
    accessOrder = false; 
}

// 给 HashMap 指定初始化容量 
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity); 
    accessOrder = false;
}

// 给 HashMap 指定初始化容量和负载因子 
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 根据另一个 Map 初始化自己 
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;
}

put () 方法

其实 put () 方法调用的是父类 HashMap 的 put () 方法，但是其中的 newNode () 方法被 LinkedHashMap 重写了，所以 LinkedHashMap 只不过是重写了 newNode 从而实现了链表的功能：

1
2
3
4
5
6
7
8
9
10
11
//link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

这个 tail 就是双向循环链表的末尾，由此可见 p 这个 entity 被插入到了链表的末尾。

1
2
3
4
5
6
7
if (e != null) { //existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess (e);
    return oldValue;
}

在 put 过程中，如果遇到 key 已经存在的情况，会调用 afterNodeAccess () 方法，先替换 value，然后把节点移到链表的末尾，这也就印证了第二点：如果在映射中重新插入键，则插入顺序不受影响（如果在调用 m.put (k, v) 前 m.containsKey (k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中）。

然后调用了 afterNodeInsertion () 进行老旧节点的淘汰：

关于 afterNodeInsertion () 方法，可以看 remove () 方法介绍中的代码！

get () 方法

1
2
3
4
5
6
7
8
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;
}

这个 getNode 是 HashMap 中的方法，用 Key 快速查找对应的 value，不存在则返回 null；如果找到了，就判断当前链表排序方式是否是按照访问顺序排序，如果是的话，需要把节点放在链表的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//move node to last (把节点放在链表的末尾)
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>) e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

remove () 方法

remove () 其实也是 HashMap 中的方法，本质是调用了 removeNode () 方法，在这个 removeNode () 方法中我们可以看到，调用了 afterNodeRemoval () 方法：

所以，LinkedHashMap 的 remove 操作。首先把它从 table 中删除，即断开 table 或者其他对象通过 next 对其引用，然后也要把它从双向链表中删除，断开其他对应通过 after 和 before 对其引用。

既然已经看了 afterNodeRemoval () 方法，自然再看看 afterNodeInsertion () 方法与 afterNodeAccess () 方法，afterNodeInsertion () 方法如下：

1
2
3
4
5
6
7
8
//possibly remove eldest (可能移除最老旧的节点)
void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry (first)) {
        K key = first.key;
        removeNode (hash (key), key, null, false, true);
    }
}

在 LinkedHashMap（本质还是 HashMap 进行 put）调用 put 的时候，不但使用了 LinkedHashMap 重写的 newNode () 方法，最后还调用了 afterNodeInsertion () 方法。LinkedHashMap 中被覆盖的 afterNodeInsertion 方法，用来回调移除最早放入 Map 的对象，可以看 removeEldestEntry () 方法的实现：

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

其实这个就是实现 LRU 的关键了，通过重写该方法，我们可以通过自己设定的规则去判断是否达到了移除元素的时机，如果开启逐出模式（evict = true），并且头节点不为空，而且满足了移除元素的条件，那么就会把最老旧的节点进行移除。afterNodeAccess () 方法在上面已经说过了，不再赘述。

Iterator

LinkedHashMap 的哈希映射具有两个影响其性能的参数：初始容量和加载因子。它们的定义与 HashMap 极其相似。要注意，为初始容量选择非常高的值对此类的影响比对 HashMap 要小，因为此类的迭代时间不受容量的影响。这句话也就是说你的 LinkedHashMap 的初始容量跟迭代时间没有关系，为什么呢？我们需要其查看 LinkedHashMap 的迭代器：

因为它遍历的是 LinkedHashMap 内部维护的双向链表，而不是散列表，但是双向链表的元素都来源于散列表的，所以无论初始化多大的 LinkedHashMap，遍历的时候依旧是走双向链表的指针，逐个逐个 next。

测试 LinkedHashMap 的顺序

测试 LinkedHashMap 的顺序和 HashMap 的顺序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void main(String [] args) {
    // 默认是插入顺序 
    LinkedHashMap<String, String> map = new LinkedHashMap<>();
    map.put ("AAA", "Hello");
    map.put ("BBB", "World");
    map.put ("CCC", "Linked");
    map.put ("DDD", "Hash");
    map.put ("EEE", "Map");
    Set<String> keySet = map.keySet ();
    for(String k: keySet){
        System.out.println ("Key=" + k + ", Value=" + map.get (k));
    }

    System.out.println ("========================================");

    HashMap<String, String> hashMap = new HashMap<>();
    hashMap.put ("AAA", "Hello");
    hashMap.put ("BBB", "World");
    hashMap.put ("CCC", "Linked");
    hashMap.put ("DDD", "Hash");
    hashMap.put ("EEE", "Map");
    Set<String> hashKeySet = hashMap.keySet ();
    for(String k: hashKeySet){
        System.out.println ("Key=" + k + ", Value=" + map.get (k));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String [] args) {
    // 使用访问顺序 
    LinkedHashMap<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
    map.put ("AAA", "Hello");
    map.put ("BBB", "World");
    map.put ("CCC", "Linked");
    map.put ("DDD", "Hash");
    map.put ("EEE", "Map");
    Set<String> keySet = map.keySet ();

    for(String k: keySet){
        System.out.println ("Key=" + k + ", Value=" + map.get (k));
    }
}

可以看到，当我们使用访问顺序构造 LinkedHashMap 的时候，在遍历时发生了并发修改异常，这是因为我们在访问第一个元素的时候，由于 get () 方法检测到 accessOrder 为 true，所以把元素放在了链表的末尾，此时去遍历当然会发生并发修改异常！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String [] args) {
    LinkedHashMap<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
    map.put ("AAA", "Hello");
    map.put ("BBB", "World");
    map.put ("CCC", "Linked");
    map.put ("DDD", "Hash");
    map.put ("EEE", "Map");

    map.get ("CCC");
    map.get ("DDD");
    map.get ("AAA");
    map.get ("EEE");
    map.get ("BBB");

    Set<String> keySet = map.keySet ();
    for(String k: keySet){
        System.out.println ("Key=" + k);
    }
}

实现自己的 LRU

关于 LinkedHashMap 的知识大致就完了，那么如何基于链表实现 LRU 缓存淘汰算法呢？

我的思路是这样的：我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1、如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

2、如果此数据没有在缓存链表中，又可以分为两种情况：

  • 如果此时缓存未满，则将此结点直接插入到链表的头部；
  • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

这样我们就用链表实现了一个 LRU 缓存，是不是很简单？

这样做虽然可以，但是效率是有问题的，假设我的链表比较长的时候我需要去找我的缓存的对象在不在这个 LRU 缓存中，需要逐个遍历，时间复杂度为 O (n)。有没有一种办法可以很快的判断在不在这个缓存中呢？

那就轮到 LinkedHashMap 登场了，因为底层是 HashMap + 双向链表的数据结构，所以只要通过 HashMap 来查找就变成了 O (logn)，甚至 O (1)。下面就通过 LinkedHashMap 实现一个自己的 LRU Cache 吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

public class LruCache<K, V> {
    // 默认负载因子 
    private static final float DEFAULT_LOAD_FACTORY = 0.75F;
    // 最大缓存数量 
    private static final int MAX_CACHE_SIZE = 10;
    // LinkedHashMap
    private final MyLinkedHashMap map;
    // 默认 size 为 16
    public LruCache() {
        map = new MyLinkedHashMap(16, DEFAULT_LOAD_FACTORY, true);
    }

    public LruCache(int initialCapacity) {
        map = new MyLinkedHashMap(initialCapacity, DEFAULT_LOAD_FACTORY, true);
    }

    public void put(K k,V v){
        map.put (k, v);
    }

    public V get(K k){
        return map.get (k);
    }

    public int size(){
        return map.size ();
    }

    public void remove(K k){
        map.remove (k);
    }

    public Set<K> keySet(){
        return map.keySet ();
    }



    private class MyLinkedHashMap extends LinkedHashMap<K, V> {
        public MyLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
            super(initialCapacity, loadFactor, accessOrder);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return MAX_CACHE_SIZE < size ();
        }
    }
}

// 测试 
public class LruCacheTest {
    public static void main(String [] args) {
        LruCache<Integer, String> lruCache = new LruCache<>(5);
        lruCache.put (1, "AAA");
        lruCache.put (2, "BBB");
        lruCache.put (3, "CCC");
        lruCache.put (4, "DDD");
        lruCache.put (5, "EEE");
        lruCache.put (6, "FFF");
        lruCache.put (7, "GGG");
        lruCache.put (8, "HHH");
        lruCache.put (9, "III");

        lruCache.get (1);
        lruCache.get (5);

        lruCache.put (10, "JJJ");
        lruCache.put (11, "KKK");
        lruCache.put (12, "LLL");
        lruCache.put (4, "MMM");

        System.out.println ("lruCache.size () = " + lruCache.size ());
        Set<Integer> keySet = lruCache.keySet ();
        for(Integer k: keySet) System.out.println ("Key = " + k);
    }
}

通过调试我们确实不难发现，整个 LRUCache 的淘汰过程。

数据结构与算法