LRU 原理与算法实现（由浅入深）

ゝ一纸荒年。 2023-09-30 11:50 87阅读 0赞

### 什么是 LRU ###

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

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

### LRU 原理 ###

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

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

![image-20220328173014601][]

### LRU 的实现 ###

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

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

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

### 单链表实现 LRU ###

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

![image-20220329103528585][]

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;
    // 默认容量，假设为 5
    static 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 个位置的元素：1
    1 4 3 2 
    新增第一个元素
    10 1 4 3 2 
    新增第二个元素
    15 10 1 4 3

### 双链表实现 LRU ###

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

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

![image-20220329103413302][]

节点构造如下：

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());
    }

结果如下：

![image-20220329163235698][]

### 链表 + 哈希表 ###

上面通过单双链表的形式实现了 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;
        }
    }

**思路**

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

**代码实现**

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());
    }

输出：

![image-20220329195438220][]

### 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;
        }
    }

[image-20220328173014601]: https://img-blog.csdnimg.cn/img_convert/191ec3bbe45d0d511cac9994ecd58eec.png
[LinkedList]: https://javatv.blog.csdn.net/article/details/117308367
[image-20220329103528585]: https://img-blog.csdnimg.cn/img_convert/95e0d08dfc8ce799efcc69fe7704006c.png
[image-20220329103413302]: https://img-blog.csdnimg.cn/img_convert/641391c35dc199c92afa6ce6b628cf8f.png
[image-20220329163235698]: https://img-blog.csdnimg.cn/img_convert/bd90cc716075f45ab3778f782ca1bea0.png
[image-20220329185959784]: https://img-blog.csdnimg.cn/img_convert/400958a83b3ca4cd7aad8638a96bb2a3.png
[image-20220329195438220]: https://img-blog.csdnimg.cn/img_convert/c7ddc6fffbea27745c74a766c74a579b.png