面试高频考题——手撸一个 LRU 算法!

原创
2021/05/12 08:46
阅读数 110

今天给大家讲一道面试中经常容易遇到的一道题:“手写一个 LRU 算法”

LRU 就是 Least Recently Used 的缩写,翻译过来就是“最近最少使用”。 也就是说 LRU 算法会将最近最少用的缓存移除,让给最新使用的缓存。这是非常常见的一个缓存淘汰策略

利用好 LRU 算法,我们能够提高对热点数据的缓存效率,进而提升缓存服务的内存使用率。

那么如何实现呢?

其实,通过缓存的 key 获取其对应的缓存,我们应该能想到用哈希表来实现,毕竟这是一个键值对结构,可以在 O(1) 时间内获取 key 对应的缓存值。

但是,哈希表本身是无序的,因此,我们还需要一个类似于队列的数据结构来记录访问的先后顺序,将最近访问的数据放在头部(如下图),移除最后一项数据(最旧),我们可以用双向链表来实现数据的增删以及顺序的调整。

因此,我们结合“哈希表 + 双向链表”来实现 LRU 算法。其中:

双向链表按照被使用的顺序存储 kv 键值对,靠近头部的 kv 键值对是最近使用的,而靠近尾部的键值对是最久未使用的。哈希表通过缓存的 key 映射到双向链表中的位置。我们可以在 O(1) 时间内定位到缓存的 key 所对应的 value 在链表中的位置。

对于 get 操作,判断 key 是否存在哈希表中:

若不存在,返回 -1。若存在,则 key 对应的节点 node 是最近使用的节点。将该节点移动到双向链表的头部,最后返回该节点的值即可。

对于 put 操作,同样先判断 key 是否存在哈希表中:

若不存在,则创建一个新的 node 节点,放入哈希表中。然后在双向链表的头部添加该节点。接着判断双向链表节点数是否超过 capacity。若超过,则删除双向链表的尾部节点,并且删除哈希表中对应的项。若存在,则更新 node 节点的值,然后该节点移动到双向链表的头部。

双向链表节点(哈希表的 value)的结构如下:

class Node {    int key;    int value;    Node prev;    Node next;    Node() {    }    Node(int key, int value) {        this.key = key;        this.value = value;    }}

你可能会问,哈希表的 value 为何还要存放 key?

这是因为,双向链表有一个删除尾节点的操作。我们定位到双向链表的尾节点,在链表中删除之后,还要找到该尾节点在哈希表中的位置,因此需要根据 value 中存放的 key,定位到哈希表的数据项,然后将其删除。

以下是 Java 版本代码的完整实现。

class LRUCache {    class Node {        int key;        int value;        Node prev;        Node next;        Node() {        }        Node(int key, int value) {            this.key = key;            this.value = value;        }    }    private int size;    private int capacity;    private Map<Integer, Node> cache;    /* 虚拟头节点 */    private Node head;    /* 虚拟尾节点 */    private Node tail;    public LRUCache(int capacity) {        this.size = 0;        this.capacity = capacity;        cache = new HashMap<>();        head = new Node();        tail = new Node();        head.next = tail;        tail.prev = head;    }    public int get(int key) {        Node node = cache.get(key);        if (node == null) {            return -1;        }        // 将最近这次访问的数据移到头部        moveToHead(node);        return node.value;    }    public void put(int key, int value) {        Node node = cache.get(key);        if (node == null) {            Node newNode = new Node(key, value);            cache.put(key, newNode);            // 将最近新增的数据放到头部            addToHead(newNode);            ++size;            // 若数据量超过设定的最大容量,移除尾部(最不常访问)的节点数据            if (size > capacity) {                Node tail = removeTail();                // 缓存淘汰,移除尾部节点数据                cache.remove(tail.key);                --size;            }        } else {            node.value = value;            moveToHead(node);        }    }    private void moveToHead(Node node) {        removeNode(node);        addToHead(node);    }    private void removeNode(Node node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }    private void addToHead(Node node) {        node.next = head.next;        head.next = node;        node.next.prev = node;        node.prev = head;    }    private Node removeTail() {        Node node = tail.prev;        removeNode(node);        return node;    }}



长按识别下图二维码,关注公众号「Doocs 开源社区」,第一时间跟你们分享好玩、实用的技术文章与业内最新资讯。



本文分享自微信公众号 - Doocs开源社区(idoocs)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部