【深入理解LRU Cache】：缓存算法的经典之作

���录

一、什么是LRU Cache？

二、LRU Cache的实现

1.JDK中类似LRUCahe的数据结构LinkedHashMap

2.自己实现双向链表

三、LRU Cache的OJ

---

一、什么是LRU Cache？

LRU Cache（Least Recently Used的缩写，即最近最少使用，它是一种Cache的替换算法。看Cache替换算法这篇文章）是一种常见的缓存淘汰算法。用于在有限的缓存空间中管理数据对象。LRU Cache 的核心思想是基于时间局部性原理，即最近被访问的数据在未来可能会被再次访问。

Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有 的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实， LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

注意：LRU Cache 应该更准确地归类为一种缓存淘汰算法，而非传统意义上的数据结构。尽管 LRU Cache 在实现时通常会利用数据结构（如双向链表和哈希表），但它本身更像是一种策略，用于管理缓存中的数据对象。

二、LRU Cache的实现

实现LRU Cache的方法和思路很多，但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的。

使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，双向链表用于记录数据对象的访问顺序，每当一个数据对象被访问时，就将其移动到链表的头部。这样，链表头部的数据对象就是最近被访问的数据，而链表尾部的数据对象则是最久未被访问的数据。同时，使用哈希表能够以 O(1) 的时间复杂度进行数据对象的查找。

当缓存空间达到上限时，需要淘汰最久未被访问的数据对象。这时只需从链表尾部删除相应的数据对象，并在哈希表中删除对应的索引即可。

1.JDK中类似LRUCahe的数据结构LinkedHashMap

LinkedHashMap中有一个这样的构造方法：

重点的accessOrder：

accessOrder 是一个 boolean 类型的参数，用于指定是否按照访问顺序来排序条目。当accessOrder 被设置为 true 时，表示按照访问顺序排序条目；当 accessOrder 被设置为 false 或未指定时（默认情况下），则按照插入顺序排序条目。

示例1：当accessOrder的值为false的时候

输出结果：

{1=a, 2=b, 4=e, 3=c} 以上结果按照插入顺序进行打印。 示例2：当accessOrder的值为true的时候 输出结果： {4=e, 3=c, 1=a, 2=b} 每次使用get方法，访问数据后，会把数据放到当前双向链表的最后。 当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值false时，从源码中可以看出recordAccess方法什么也不会做。 所以要实现一个LRU Cache，最简单的策略就是用自定义类继承LinkedHashMap，然后根据不同要求重写部分方法（ 必须重写removeEldestEntry这个方法，默认是false ）。

import java.util.LinkedHashMap;import java.util.Map;public class LRUCache extends LinkedHashMap {    private final int capacity;    public LRUCache(int capacity) {        //accessOrder设置为false时，会按照插入顺序进行排序，当accessOrder为true时，会按照访问顺序        super(capacity, 0.75f, true);        this.capacity = capacity;    }    @Override    public Integer get(Object key) {        //如果get不到，返回默认值-1        return super.getOrDefault(key, -1);    }    @Override    public Integer put(Integer key, Integer value) {        return super.put(key, value);    }    @Override    protected boolean removeEldestEntry(Map.Entry eldest) {        //如果集合内元素个数超过capacity，会将最不常用的元素出队，并将新元素插在尾部        return size() > capacity;    }}

测试：

当然在面试时这个做法肯定不会符合面试官的要求，更好的做法是自己实现一个双向链表。

2.自己实现双向链表

前面说到：

• 双向链表用于记录数据对象的访问顺序，每当一个数据对象被访问时，就将其移动到链表的头部。这样，链表头部的数据对象就是最近被访问的数据，而链表尾部的数据对象则是最久未被访问的数据。同时，使用哈希表能够以 O(1) 的时间复杂度进行数据对象的查找。
• 当缓存空间达到上限时，需要淘汰最久未被访问的数据对象。这时只需从链表尾部删除相应的数据对象，并在哈希表中删除对应的索引即可。

  为方便测试，我重写了toString方法，测试代码也包含在里面，根据需求删除即可。

  import java.util.HashMap;import java.util.Map;//双向链表 + 哈希表public class MyLRUCache {    //双向链表的节点类    static class DLinkedNode {        //键值对        int key;        int val;        DLinkedNode next;        DLinkedNode prev;        public DLinkedNode() {        }        public DLinkedNode(int key, int val) {            this.key = key;            this.val = val;        }    }    private Map cache; //缓存    private final int capacity;    private int size;    //虚拟的头尾节点（哨兵）    private DLinkedNode head;    private DLinkedNode tail;    public MyLRUCache(int capacity) {        this.capacity = capacity;        this.cache = new HashMap();        //连接虚拟头尾节点        this.head = new DLinkedNode();        this.tail = new DLinkedNode();        head.next = tail;        tail.prev = head;    }    //插入数据    public void put(int key, int value) {        //两种情况：元素是否存在        if (!cache.containsKey(key)) {            //1.元素不存在            //1.1 新元素加到cache集合中            DLinkedNode newNode = new DLinkedNode(key, value);            cache.put(key, newNode);            //1.2 插到尾部            addLast(newNode);            size++;            //1.3 判断当前的元素个数是否超过容量            if (size > capacity) {                //1.4 删除第一个节点，即最近最久未使用                DLinkedNode del = removeFirst();                //同时需要把该元素从cache中删除                cache.remove(del.key);                size--;            }        } else {            //2.元素存在，修改链表的顺序，将该节点放到尾部（最近一次使用的）            DLinkedNode node = cache.get(key);            //2.1 以新的值将该节点移动到尾部            node.val = value;            moveLast(node);        }    }    //将节点移动到尾部    private void moveLast(DLinkedNode node) {        //1.删除当前节点        removeNode(node);        //2.尾插到链表        addLast(node);    }    //删除节点    private void removeNode(DLinkedNode node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }    //删除第一个节点    private DLinkedNode removeFirst() {        DLinkedNode del = head.next;        head.next = del.next;        head.next.prev = head;        return del;    }    //尾插到链表    private void addLast(DLinkedNode node) {        //连接最后一个节点和新的尾节点        tail.prev.next = node;        node.prev = tail.prev;        //连接新尾节点和傀儡尾节点        tail.prev = node;        node.next = tail;    }    //获取数据    public int get(int key) {        //1.cache集合中拿到这个节点        DLinkedNode node = cache.get(key);        //2.判断是否有这个节点        if (node != null) {            //2.1 有该节点 将该节点移动到尾部（最近一次使用的）            moveLast(node);            return node.val;        }        //2.2 没有该节点，返回-1        return -1;    }    //删除数据    public boolean remove(int key) {        //1.看缓存中存不存在        DLinkedNode node = cache.get(key);        //2.不存在，直接返回        if (node == null) {            return false;        }        //3.存在        //3.1 删除链表的节点        removeNode(node);        //3.2 删除cache集合的数据        cache.remove(key);        size--;        return true;    }    @Override    public String toString() {        StringBuilder sbu = new StringBuilder();        DLinkedNode cur = head.next;        sbu.append("{");        while (cur != tail) {            if (cur.next != tail) {                sbu.append(cur.key).append("=").append(cur.val).append(", ");            } else {                sbu.append(cur.key).append("=").append(cur.val);            }            cur = cur.next;        }        sbu.append("}");        return sbu.toString();    }    public static void main(String[] args) {        MyLRUCache lruCache = new MyLRUCache(3);        lruCache.put(1, 10);        lruCache.put(2, 11);        lruCache.put(3, 12);        System.out.println(lruCache);        System.out.println("使用后：");        lruCache.get(2);        System.out.println(lruCache);        lruCache.get(1);        System.out.println(lruCache);        lruCache.put(4, 13);        System.out.println("最不常用的被删除，新元素插到尾部：");        System.out.println(lruCache);    }}

  三、LRU Cache的OJ

  LeetCode 热题100 链表专题的最后一题

  146. LRU 缓存 - 力扣（LeetCode）https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked前面两种实现中，MyLRUCache的get方法在获取不到数据时返回的是-1的原因就是根据这道题的要求做的，并且多写了一个remove方法。提交时将类名和构造方法改成原题默认的LRUCache，且不要main方法即可。