头条面试高频题目,手撕 LRU

2019-03-09 10:53:34 +08:00
 Acceml

题目

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

题解

这道题在今日头条、快手或者硅谷的公司中是比较常见的,代码要写的还蛮多的,难度也是 hard 级别。

最重要的是 LRU 这个策略怎么去实现, 很容易想到用一个链表去实现最近使用的放在链表的最前面。 比如 get 一个元素,相当于被使用过了,这个时候它需要放到最前面,再返回值, set 同理。 那如何把一个链表的中间元素,快速的放到链表的开头呢? 很自然的我们想到了双端链表。

基于 HashMap 和 双向链表实现 LRU 的

整体的设计思路是,可以使用 HashMap 存储 key,这样可以做到 save 和 get key 的时间都是 O(1),而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点,如图所示。

LRU 存储是基于双向链表实现的,下面的图演示了它的原理。其中 head 代表双向链表的表头,tail 代表尾部。首先预先设置 LRU 的容量,如果存储满了,可以通过 O(1) 的时间淘汰掉双向链表的尾部,每次新增和访问数据,都可以通过 O(1)的效率把新的节点增加到对头,或者把已经存在的节点移动到队头。

下面展示了,预设大小是 3 的,LRU 存储的在存储和访问过程中的变化。为了简化图复杂度,图中没有展示 HashMap 部分的变化,仅仅演示了上图 LRU 双向链表的变化。我们对这个 LRU 缓存的操作序列如下:

save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)

相应的 LRU 双向链表部分变化如下:

总结一下核心操作的步骤:

save(key, value),首先在 HashMap 找到 Key 对应的节点,如果节点存在,更新节点的值,并把这个节点移动队头。如果不存在,需要构造新的节点,并且尝试把节点塞到队头,如果 LRU 空间不足,则通过 tail 淘汰掉队尾的节点,同时在 HashMap 中移除 Key。

get(key),通过 HashMap 找到 LRU 链表节点,因为根据 LRU 原理,这个节点是最新访问的,所以要把节点插入到队头,然后返回缓存的值。

    private static class DLinkedNode {
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode post;
    }

    /**
     * 总是在头节点中插入新节点.
     */
    private void addNode(DLinkedNode node) {

        node.pre = head;
        node.post = head.post;

        head.post.pre = node;
        head.post = node;
    }

    /**
     * 摘除一个节点.
     */
    private void removeNode(DLinkedNode node) {
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }

    /**
     * 摘除一个节点,并且将它移动到开头
     */
    private void moveToHead(DLinkedNode node) {
        this.removeNode(node);
        this.addNode(node);
    }

    /**
     * 弹出最尾巴节点
     */
    private DLinkedNode popTail() {
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }

    private HashMap<Integer, DLinkedNode>
            cache = new HashMap<Integer, DLinkedNode>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        head.pre = null;

        tail = new DLinkedNode();
        tail.post = null;

        head.post = tail;
        tail.pre = head;
    }

    public int get(int key) {

        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1; // cache 里面没有
        }

        // cache 命中,挪到开头
        this.moveToHead(node);

        return node.value;
    }


    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);

        if (node == null) {

            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            this.cache.put(key, newNode);
            this.addNode(newNode);

            ++count;

            if (count > capacity) {
                // 最后一个节点弹出
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                count--;
            }
        } else {
            // cache 命中,更新 cache.
            node.value = value;
            this.moveToHead(node);
        }
    }
    

热门阅读

8102 次点击
所在节点    程序员
28 条回复
xylophone21
2019-03-09 11:29:51 +08:00
这个场景下,你们把 key 翻译成密钥?
cxtrinityy
2019-03-09 11:37:13 +08:00
既然已经用了 HashMap,直接 LinkedHashMap 可破,不需要自己再去实现链表吧
count > capacity 时,你需要 foreach map 逐个排除,直至 count 降到 capacity 以下,这里是以个数为准,所以直接踢掉 tail 也可以
gethermyp
2019-03-09 13:06:05 +08:00
直接用 linkedhashmap
swulling
2019-03-09 13:07:06 +08:00
为什么把 Key 翻译为密钥?不是键么
HarryQu
2019-03-09 13:18:58 +08:00
lazydog
2019-03-09 13:22:51 +08:00
看到 LRU,我就只知道要用 HashMap 和双向链表实现,但具体怎么实现,不造~
ecrazy
2019-03-09 15:43:03 +08:00
这样直接抄没事?
CSM
2019-03-09 15:46:13 +08:00
@HarryQu #5 你好,看了这个代码有个疑问,就是 get 的实现中在命中 cache 后,貌似并没有将其移到 LinkedHashMap 的末尾?
pythondean
2019-03-09 16:01:03 +08:00
https://github.com/golang/groupcache/blob/master/lru/lru.go
golang 团队在 groupcache 中使用到了 lru
HarryQu
2019-03-09 16:28:00 +08:00
要理解 LruCache, 首先你要了解 HaspMap 原理,

然后理解 LinkedHashMap 原理, 再然后理解 LinkedHashMap 中的 accessOrder 属性 。

节点的移动是在 LinkedHashMap 中的 get 方法中 ,以 JDK 1.8 为例 , 方法调用为 :
LinkedHashMap.get() => accessOrder 为 true => afterNodeAccess() 中 移动节点

其中 accessOrder 是 LruCache 在 LinkedHashMap 初始化的时候设置为 true .

因个人水平有限 , 具体的源码分析就不做阐述了,麻烦你 Google 一下 。

需要注意一点的是在 JDK 1.7 和 JDK 1.8 的源码中 ,HashMap 内部实现不同 。
HarryQu
2019-03-09 16:28:54 +08:00
@CSM 忘记 @ 你了 你看下 10 楼
CSM
2019-03-09 16:37:26 +08:00
@HarryQu #10 原来 LinkedHashMap 的迭代除了插入顺序,还可以是访问顺序,现在明白了。非常感谢。
BBCCBB
2019-03-09 20:47:57 +08:00
@cxtrinityy
@gethermyp
两位老哥, 虽然楼主一直发公众号很烦, 但是这个面试的时候要你自己写一个 LRU,你说直接用 linkedhashmap,这不就 GG 了, ==
Actrace
2019-03-09 21:06:57 +08:00
我觉得面试要手写 LRU 的公司不去也罢。
cxtrinityy
2019-03-09 21:18:22 +08:00
@BBCCBB 没有啊,你既然都用了 HashMap 本身就表示接受 JDK 类了,HashMap 本身也是优化后的实现,既然不能用 LinkedHashMap,那么就不能用 HashMap,那么文章里就应该用数组自己去实现 Hash 存储
hanxiV2EX
2019-03-09 21:25:55 +08:00
在电脑上写过,知道原理就很好写出来。hash 表和双端链表配合。get 或者 set 之后就把这个节点放到 head,set 时判断下 size,超过了就把 tail 删掉。
hanxiV2EX
2019-03-09 21:27:38 +08:00
LRU 在游戏服务端开发很有用的,把活跃数据缓存到内存中。
BBCCBB
2019-03-09 22:12:20 +08:00
@cxtrinityy 我觉得这个还是主要考怎么实现一个 lru,主要是思路,就是将双端队列和 hashmap 结合起来的思路,并不会说让实现一个 hashmap 的。或者你直接照着 linkedhashmap 的原理说。
woscaizi
2019-03-09 22:17:46 +08:00
@Actrace 蚂蚁伯乐系统面试里就有这题。
zpxshl
2019-03-09 23:33:47 +08:00
真巧面头条时确实遇到...虽然知道原理但一时脑抽说写不出来...我后面也在纳闷为什么我会觉得写不出来

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/542739

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX