LRU 原理与算法实现

2022 年 6 月 24 日
本文字数：10990 字
阅读完需：约 36 分钟

什么是 LRU

LRU（Least Recently Used，最近最少使用）算法是一种内存数据淘汰策略，当内存不足时，需要淘汰最近最少使用的数据。

其核心思想是长期不被使用的数据，在未来被使用到的几率也不大。因此，当数据所占内存达到一定阈值的时候需要淘汰掉这些数据。

LRU 原理

按照 LRU 的核心思想，不被使用的数据，在未来被使用到的几率也不大，那么当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。即：

当新数据插入到链表头部；
每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
当链表满的时候，将链表尾部的数据丢弃。

LRU 的实现

常用的数据结构有很多，如数组、链表、栈、队列等等，这里演示 2 种做法，单链表和双向链表 + 哈希表实现。

为什么要先用单链表去实现？其目的是为了从简单到复杂的去了解 LRU 的设计过程。

当前，前提是你得了解单双链表的数据结构，不了解的可以参考：手写链表之 LinkedList 源码分析

单链表实现 LRU

既然要用单链表实现，首先得定义一个单链表，并且具备增删改查功能，如下：

1、先定义链表节点信息

/** * 节点信息 * * @param <E> */private static class Node<E> {    // 元素    E item;    // 后继节点（这里是单链表，只有一个后继节点）    Node<E> next;    public Node(E item, Node<E> next) {        this.item = item;        this.next = next;    }}

复制代码

2、定义增删方法

/** * 在头部添加节点，一般来说是在尾部添加，但这里为了演示 LRU 所以从头添加元素 * * @param e */public void addFirst(E e) {    Node<E> curNode = new Node<>(e, list);    list = curNode;    size++;}/** * 删除最后一个元素 */public void removeLast() {    if (list != null) {        // 当前节点        Node<E> cur = list;        // 最后一个节点的前一个节点        Node<E> pre = list;        // 判断当前节点是否是最后一个节点        while (cur.next != null) {            pre = cur;            cur = cur.next;        }        pre = null;        size--;    }}

复制代码

完整代码：

public class SingleLinkeList<E> {    // 链表    Node<E> list;    // 链表节点数量    int size;    /**     * 在头部添加节点，一般来说是在尾部添加，但这里为了演示 LRU 所以从头添加元素     *     * @param e     */    public void addFirst(E e) {        Node<E> curNode = new Node<>(e, list);        list = curNode;        size++;    }    /**     * 删除最后一个元素     */    public void removeLast() {        if (list != null) {            // 当前节点            Node<E> cur = list;            // 最后一个节点的前一个节点            Node<E> pre = list;            // 判断当前节点是否是最后一个节点            while (cur.next != null) {                pre = cur;                cur = cur.next;            }            pre = null;            size--;        }    }    /**     * 检测index是否在链表范围以内     *     * @param index     */    public void checkPositionIndex(int index) {        if (!(index >= 0 && index <= size)) {            throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);        }    }    /**     * 节点信息     *     * @param <E>     */    private static class Node<E> {        // 元素        E item;        // 后继节点（这里是单链表，只有一个后继节点）        Node<E> next;        public Node(E item, Node<E> next) {            this.item = item;            this.next = next;        }    }        @Override    public String toString() {        Node node = list;        for (int i = 0; i < size; i++) {            System.out.print(node.item + " ");            node = node.next;        }        System.out.println();        return super.toString();    }}

复制代码

注：以上只写了对 LRU 有用的新增和删除方法，单链表的查询和修改并没有添加。

单链表实现 LRU 缓存

1、定义内存限制

既然是缓存，内存大小肯定是存在限制的，因此我们要定义其内存大小，如下：

// 用于限定内存空间大小，也就是缓存的大小int size;// 默认容量，假设为 5static final int DEFAULT_CAP = 5;

复制代码

2、添加元素

在添加元素的时候我们需要考虑以下 2 点：

当链表满的时候，将链表尾部的数据丢弃；
新数据插入到链表头部。

/** * LRU 添加节点 * * @param e */public void lruAdd(E e) {    // 如果链表的容量大于缓存容量，将链表尾部的数据丢弃    if (size > memory_size) {        removeLast();        addFirst(e);    } else {        // 否则新数据插入到链表头部        addFirst(e);    }}

复制代码

3、LRU 删除

对于删除元素，只需将链表的最后一个元素删除即可。

/** * 删除 */public void lruRemove() {    removeLast();}

复制代码

4、LRU 访问

对于访问的数据，则将数据移到链表头部。

/** * 获取 */public E lruGet(int index) {    // 检查是否在链表范围内    checkPositionIndex(index);    // 目标节点，即 index 位置的节点    Node<E> cur = list;    // 目标节点的前一个节点    Node<E> pre = list;    // for 循环获取目标节点    for (int i = 0; i < index; i++) {        pre = cur;        cur = cur.next;    }    //获取目标元素    E item = cur.item;    // 把目标节点的后继节点重新赋值给目标节点前置节点的后置节点    pre.next = cur.next;    Node<E> head = list;    // 然后把目标节点移动到头结点，即把剩下的节点当做目标节点的后继节点    cur.next = head;    // 重新赋值给 list    list = cur;    return item;}

复制代码

完整代码：

/** * LRU 的3要素 * 1. 当新数据插入到链表头部 * 2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部 * 3. 当链表满的时候，将链表尾部的数据丢弃 */public class LRUCache<E> extends SingleLinkeList<E> {    // 用于限定内存空间大小，也就是缓存的大小    int memory_size;    // 默认容量，假设为 5    static final int DEFAULT_CAP = 5;    public LRUCache() {        this(DEFAULT_CAP);    }    public LRUCache(int memory_size) {        this.memory_size = DEFAULT_CAP;    }    /**     * LRU 添加节点     *     * @param e     */    public void lruAdd(E e) {        // 如果链表的容量大于缓存容量，将链表尾部的数据丢弃        if (size > memory_size) {            removeLast();            addFirst(e);        } else {            // 否则新数据插入到链表头部            addFirst(e);        }    }    /**     * 删除     */    public void lruRemove() {        removeLast();    }    /**     * 获取     */    public E lruGet(int index) {        // 检查是否在链表范围内        checkPositionIndex(index);        // 目标节点，即 index 位置的节点        Node<E> cur = list;        // 目标节点的前一个节点        Node<E> pre = list;        // for 循环获取目标节点        for (int i = 0; i < index; i++) {            pre = cur;            cur = cur.next;        }        //获取目标元素        E item = cur.item;        // 把目标节点的后继节点重新赋值给目标节点前置节点的后置节点        pre.next = cur.next;        Node<E> head = list;        // 然后把目标节点移动到头结点，即把剩下的节点当做目标节点的后继节点        cur.next = head;        // 重新赋值给 list        list = cur;        return item;    }}

复制代码

测试：

public static void main(String[] args) {    LRUCache<Integer> lruCache = new LRUCache<>(5);    // 初始化元素    for (int i = 1; i < 5; i++) {        lruCache.lruAdd(i);    }    System.out.println("初始化元素");    lruCache.toString();    System.out.println("获取第 3 个位置的元素：" + lruCache.lruGet(3));    // 此时，应该把第 3 个位置的元素设置为头结点    lruCache.toString();    lruCache.lruAdd(10);    System.out.println("新增第一个元素");    lruCache.toString();    lruCache.lruAdd(15);    System.out.println("新增第二个元素");    lruCache.toString();}

复制代码

输出：

初始化元素4 3 2 1 获取第 3 个位置的元素：11 4 3 2 新增第一个元素10 1 4 3 2 新增第二个元素15 10 1 4 3

复制代码

双链表实现 LRU

除了单链表 JDK 中自带了双向链表的实现，即 LinkedList，但如果在面试的情况下，可能需要你实现一个简单的双向链表，而不是用现有的。

因此，我们按照单链表的实现方式来实现一个简单的双向链表，与单链表不同的是，节点有前驱和后继 2 个引用，如下：

节点构造如下：

class Node<E> {    E item;    Node<E> prev;    Node<E> next;    public Node(E item, Node<E> prev, Node<E> next) {        this.item = item;        this.prev = prev;        this.next = next;    }}

复制代码

然后构建一个新增头节点和删除尾结点的方法，参考 JDK 中的 LinkedList，如下：

public class LinkedList<E> {    // 头结点    Node<E> head;    // 尾结点    Node<E> tail;    // 链表节点数量    int size;    /**     * 添加头结点     *     * @param e     */    public void addFirst(E e) {        Node<E> f = head;        // 新添加的元素作为新的头结点        Node<E> newNode = new Node<>(e, null, f);        head = newNode;        // 如果原头结点为 null，则说明原链表不存在数据,即空链表，因此头尾节点相等        if (f == null) {            tail = newNode;        } else {            // 否则，将原头结点的前置指针指向新的节点            f.prev = newNode;        }        size++;    }    /**     * 删除最后一个元素，参考 LinkedList     */    public E removeLast() {        // 1.这里要先判断链表是否为空,为空直接抛异常        final Node<E> h = head;        if (h == null) {            throw new NoSuchElementException();        }        Node<E> t = tail;        // 2.取出尾结点的值，用于方法返回        E element = t.item;        // 3.获取尾结点的前置节点        Node<E> prev = t.prev;        t.item = null;        t.prev = null; // help GC        // 4.将原尾结点的前置节点变为新的尾结点        tail = prev;        // 5.如果原尾结点的前置节点为 null，则说明当前链表只有一个元素，因此需将原头结点置为 null        if (prev == null) {            head = null;        } else {            // 6.否则将 prev 的后置节点置为 null，因为此时的 prev 为当前链表的尾结点            prev.next = null;        }        size--;        return element;    }        /**     * 遍历双向链表,从头结点开始遍历     */    public String showList() {        // 判断链表是否为空        if (head.next == null && head.item == null) {            System.out.println("链表为空");            return null;        }        Node<E> temp = head;        String s = String.valueOf(temp.item);        while (temp.next != null) {            temp = temp.next;            s = s + " " + String.valueOf(temp.item);        }        return s;    }    class Node<E> {        E item;        Node<E> prev;        Node<E> next;        public Node(E item, Node<E> prev, Node<E> next) {            this.item = item;            this.prev = prev;            this.next = next;        }    }}

复制代码

对于查找元素来说，JDK 中的 LinkedList 先判断想要找的节点是在集合的前半部分还是后半部分，如果是在前半部分，则从前往后查找，如果是在后半部分，则从后往前查找，这样做的目的是提高效率而不需要从头到尾去扫描。

但这里实现 LRU 的查找时为了简单则是从头到尾遍历，但有两个点需要注意：

如果查询 index 位置的是头节点，则直接返回头节点的值；
如果查询 index 位置的是尾节点，则在移动目标节点到头节点的时候，将目标节点的前置节点的后置节点置为 null 即可。

完整代码：

public class LRUCache<E> extends LinkedList<E> {    // 用于限定内存空间大小，也就是缓存的大小    int memory_size;    // 默认容量，假设为 5    static final int DEFAULT_CAP = 5;    public LRUCache() {        this(DEFAULT_CAP);    }    public LRUCache(int memory_size) {        this.memory_size = memory_size;    }    /**     * 添加节点     *     * @param e     */    public void put(E e) {        // 如果链表的容量大于缓存容量，将链表尾部的数据丢弃        if (size >= memory_size) {            removeLast();            addFirst(e);        } else {            // 否则新数据插入到链表头部            addFirst(e);        }    }    /**     * 获取     *     * @param index     * @return     */    public E get(int index) {        // 这里省略 index 范围判断，懂的都懂，懒得写了        // 目标节点，即 index 位置的节点        Node<E> curr = head;        // 如果是 index = 0，则说明是首节点，无需移动        if (index == 0)            return curr.item;        //查找 index 位置的元素        for (int i = 0; i < index; i++) {            curr = curr.next;        }        // 获取目标元素        E element = curr.item;        // 目标节点的前一个节点        Node<E> prev = curr.prev;        // 目标节点的后一个节点        Node<E> next = curr.next;        // 然后把当前节点移动到头结点        // 如果 next 为 null，则说明 index 位置的节点是尾结点        if (next == null) {            prev.next = null;            // 同时尾结点为 prev节点            tail = prev;        } else {            prev.next = next;            next.prev = prev;        }        curr.prev = null;        curr.next = head;        head = curr;        return element;    }}

复制代码

测试：

public static void main(String[] args) {    LRUCache<Integer> node = new LRUCache<>(5);    // 初始化元素    for (int i = 1; i < 5; i++) {        node.put(i);    }    System.out.println("初始化：" + node.showList());    node.get(2);    System.out.println("获取一个元素：" + node.showList());    node.put(10);    System.out.println("添加第一个元素：" + node.showList());    node.put(15);    System.out.println("添加第二个元素：" + node.showList());}

复制代码

结果如下：

链表 + 哈希表

上面通过单双链表的形式实现了 LRU，相对来说比较简单，而针对上面的操作，我们可以发现，当查询 index 位置的元素时，需要循环遍历 index 次，时间复杂度为O(n)，查询比较慢，双向链表同理，当然增删是很快的，那么为了使其查询速度快，可以使用链表 + 哈希表的方式，哈希表的搜索可以达到0(1)时间复杂度。

用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

既然用 HashMap，则原 Node 需要再添加一个 key 属性，如下：

class Node<K, V> {    K key;    V value;    Node<K, V> prev;    Node<K, V> next;    public Node(K key, V value, Node<K, V> prev, Node<K, V> next) {        this.key = key;        this.value = value;        this.prev = prev;        this.next = next;    }}

复制代码

思路

构建双向链表节点 Node，应包含key,value,prev,next属性；
定义 HashMap 用于存放 Node 节点；
对于 get 操作，在 HashMap 通过 key获取
如果存在，则将该 Node 移到链表头部
如果不存在，则直接返回 Null
对于 put 操作，如下：

代码实现

import java.util.HashMap;import java.util.NoSuchElementException;public class LRUCache<K, V> {    // 容量    private int capacity;    // 默认容量，假设为 5    static final int DEFAULT_CAP = 5;    // 头结点    Node<K, V> head;    // 尾结点    Node<K, V> tail;    // 用来存储映射    HashMap<K, Node<K, V>> map;    public LRUCache() {        this(DEFAULT_CAP);    }    public LRUCache(int initialCapacity) {        capacity = initialCapacity;        map = new HashMap<>();    }    static class Node<K, V> {        K key;        V value;        Node<K, V> prev;        Node<K, V> next;        public Node(K key, V value, Node<K, V> prev, Node<K, V> next) {            this.key = key;            this.value = value;            this.prev = prev;            this.next = next;        }    }    /**     * 添加头结点     */    public void addFirst(K key, V val) {        Node<K, V> h = head;        // 新添加的元素作为新的头结点        Node<K, V> newNode = new Node<>(key, val, null, h);        head = newNode;        // 如果原头结点为 null，则说明原链表不存在数据,即空链表，因此头尾节点相等        if (h == null) {            tail = newNode;        } else {            // 否则，将原头结点的前置指针指向新的节点            h.prev = newNode;        }        map.put(key, newNode);    }    public V removeLast() {        // 1.这里要先判断链表是否为空,为空直接抛异常        final Node<K, V> h = head;        if (h == null) {            throw new NoSuchElementException();        }        Node<K, V> t = tail;        // 2.取出尾结点的值，用于方法返回        V value = t.value;        // 3.获取尾结点的前置节点        Node<K, V> prev = t.prev;        t.key = null;        t.value = null;        t.prev = null; // help GC        // 4.将原尾结点的前置节点变为新的尾结点        tail = prev;        // 5.如果原尾结点的前置节点为 null，则说明当前链表只有一个元素，因此需将原头结点置为 null        if (prev == null) {            head = null;        } else {            // 6.否则将 prev 的后置节点置为 null，因为此时的 prev 为当前链表的尾结点            prev.next = null;        }        map.remove(t.key);        return value;    }    /**     * 移动节点到链表头部     *     * @param curr     * @return     */    public V moveToHead(Node<K, V> curr) {        // 目标节点，即 key 位置的节点        // 判断是否为首节点，时则无需移动        if (curr == head)            return curr.value;        // 目标节点的前一个节点        Node<K, V> prev = curr.prev;        // 目标节点的后一个节点        Node<K, V> next = curr.next;        // 然后把当前节点移动到头结点        // 如果 next 为 null，则说明 index 位置的节点是尾结点        if (next == null) {            prev.next = null;            // 同时尾结点为 prev节点            tail = prev;        } else {            // 如果目标节点的前一个节点的前置节点为null，则说明目标节点是链表的第二个节点，            // 那么目标节点的前一个节点就是头结点，原头结点为前置节点为null，因此要重新赋值            if (prev.prev == null) {                prev.prev = curr;            }            prev.next = next;            next.prev = prev;        }        curr.prev = null;        curr.next = head;        head = curr;        return curr.value;    }    public void put(K key, V val) {        Node<K, V> curr = map.get(key);        // 如果为空，则添加        if (curr == null) {            // 先判断容量,未满则添加            if (map.size() < capacity) {                addFirst(key, val);            } else {                // 否则先删除链表尾部的数据                removeLast();                addFirst(key, val);            }        } else {            // 如果不为空，则修改 key 对应的 value 值,并移动到头结点            curr.value = val;            moveToHead(curr);        }    }    public V get(K key) {        Node<K, V> curr = map.get(key);        // 如果为 null 直接返回        if (curr == null) {            return null;        } else {            // 否者把他移动到链表头部            return moveToHead(curr);        }    }    /**     * 遍历双向链表,从头结点开始遍历     */    public String showList() {        // 判断链表是否为空        if (head.next == null && head.value == null) {            System.out.println("链表为空");            return null;        }        Node<K, V> temp = head;        String s = String.valueOf(temp.value);        while (temp.next != null) {            temp = temp.next;            s = s + " " + String.valueOf(temp.value);        }        return s;    }}

复制代码

其实现其实和双链表大致一致，不同的就是添加了 HashMap 用于存放 Node 节点。

测试：

public static void main(String[] args) {    LRUCache<String, String> cache = new LRUCache<>(5);    // 初始化元素    cache.put("key1", "1");    cache.put("key2", "2");    cache.put("key3", "3");    cache.put("key4", "4");    System.out.println("初始化：" + cache.showList());    cache.get("key3");    System.out.println("获取一个元素：" + cache.showList());    cache.put("key10", "10");    System.out.println("添加第一个元素：" + cache.showList());    cache.put("key20", "20");    System.out.println("添加第二个元素：" + cache.showList());    // 添加 key 相同的元素    cache.put("key4", "40");    System.out.println("添加第二个元素：" + cache.showList());}

复制代码

输出：

LinkedHashMap

JDK 中其实有哈希表和双向链表组合，就是 LinkedHashMap，它就是 HashMap 和 LinkedList 的一个结合。

LinkedHashMap 中本身就实现了一个方法 removeEldestEntry 用于判断是否需要移除最不常读取的数，方法默认是直接返回 false，不会移除元素，所以需要重写该方法，即当缓存满后就移除最不常用的数。

我们可以直接使用它的方法来完成一个 LRU，代码如下：

import java.util.LinkedHashMap;import java.util.Map;class LRUCache extends LinkedHashMap<Integer, Integer> {        private int capacity;    public LRUCache(int capacity) {        super(capacity, 0.75F, true);        this.capacity = capacity;    }    public int get(int key) {        return super.getOrDefault(key, -1);    }    public void put(int key, int value) {        super.put(key, value);    }    @Override    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {        return size() > capacity;    }}