面试官：你能写个LRU缓存吗？

发表于

0. 前情提要

面试官： 你能手写个LRU缓存吗？

你： LRU是什么东西？（一脸懵逼状）

面试官： LRU全称Least Recently Used（最近最少使用），用来淘汰不常用数据，保留热点数据。

你写了5分钟，然而只写了个get和put方法体，里面逻辑实在不知道咋写。

面试官： 今天的面试先到这吧，有其他面试我们会再联系你。

我信你个鬼，你个糟老头子坏滴很，还联系啥，凉凉了。

别担心，再有人问你LRU，就把这篇文章丢给他，保证当场发offer。

1. 实现思路

目的是把最不常用的数据淘汰掉，所以需要记录一下每个元素的访问次数。最简单的方法就是把所有元素按使用情况排序，最近使用的，移到末尾。缓存满了，就从头部删除。

2. 使用哪种数据结构实现？

常用的数据结构有数组、链表、栈、队列，考虑到要从两端操作元素，就不能使用栈和队列。

每次使用一个元素，都要把这个元素移到末尾，包含一次删除和一次添加操作，使用数组会有大量的拷贝操作，不适合。

又考虑到删除一个元素，要把这个元素的前一个节点指向下一个节点，使用双链接最合适。

链表不适合查询，因为每次都要遍历所有元素，可以和HashMap配合使用。

双链表 + HashMap

3. 代码实现

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
复制代码import java.util.HashMap;
import java.util.Map;

/**
 * @author yideng
 */
public class LRUCache<K, V> {

    /**
     * 双链表的元素节点
     */
    private class Entry<K, V> {
        Entry<K, V> before;
        Entry<K, V> after;
        private K key;
        private V value;
    }

    /**
     * 缓存容量大小
     */
    private Integer capacity;
    /**
     * 头结点
     */
    private Entry<K, V> head;
    /**
     * 尾节点
     */
    private Entry<K, V> tail;
    /**
     * 用来存储所有元素
     */
    private Map<K, Entry<K, V>> caches = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public V get(K key) {
        final Entry<K, V> node = caches.get(key);
        if (node != null) {
            // 有访问，就移到链表末尾
            afterNodeAccess(node);
            return node.value;
        }
        return null;
    }

    /**
     * 把该元素移到末尾
     */
    private void afterNodeAccess(Entry<K, V> e) {
        Entry<K, V> last = tail;
        // 如果e不是尾节点，才需要移动
        if (last != e) {
            // 删除该该节点与前一个节点的联系，判断是不是头结点
            if (e.before == null) {
                head = e.after;
            } else {
                e.before.after = e.after;
            }

            // 删除该该节点与后一个节点的联系
            if (e.after == null) {
                last = e.before;
            } else {
                e.after.before = e.before;
            }

            // 把该节点添加尾节点，判断尾节点是否为空
            if (last == null) {
                head = e;
            } else {
                e.before = last;
                last.after = e;
            }
            e.after = null;
            tail = e;
        }
    }

    public V put(K key, V value) {
        Entry<K, V> entry = caches.get(key);
        if (entry == null) {
            entry = new Entry<>();
            entry.key = key;
            entry.value = value;
            // 新节点添加到末尾
            linkNodeLast(entry);
            caches.put(key, entry);
            // 节点数大于容量，就删除头节点
            if (this.caches.size() > this.capacity) {
                this.caches.remove(head.key);
                afterNodeRemoval(head);
            }
            return null;
        }
        entry.value = value;
        // 节点有更新就移动到未节点
        afterNodeAccess(entry);
        caches.put(key, entry);
        return entry.value;
    }

    /**
     * 把该节点添加到尾节点
     */
    private void linkNodeLast(Entry<K, V> e) {
        final Entry<K, V> last = this.tail;
        if (head == null) {
            head = e;
        } else {
            e.before = last;
            last.after = e;
        }
        tail = e;
    }

    /**
     * 删除该节点
     */
    void afterNodeRemoval(Entry<K, V> e) {
        if (e.before == null) {
            head = e.after;
        } else {
            e.before.after = e.after;
        }

        if (e.after == null) {
            tail = e.before;
        } else {
            e.after.before = e.before;
        }
    }

}

4. 其实还有更简单的实现

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
复制代码import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author yideng
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    // 最大容量
    private final int maximumSize;

    public LRUCache(final int maximumSize) {
        // true代表按访问顺序排序，false代表按插入顺序
        super(maximumSize, 0.75f, true);
        this.maximumSize = maximumSize;
    }

    /**
     * 当节点数大于最大容量时，就删除最旧的元素
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry eldest) {
        return size() > this.maximumSize;
    }
}

**为啥继承了LinkedHashMap，重写了两个方法，就实现了LRU？

下篇带你手撕LinkedHashMap源码，到时你会发现LinkedHashMap的源码和上面一灯写的LRU逻辑竟然有惊人的相似。**

)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%