算法题--LRU

> 参考https://zhuanlan.zhihu.com/p/75390654

LRU: Least Recently Used.最近最少使用(也有说最远最少使用或最久未使用，都对，看怎么理解。总而言之就是给元素一个“热度值”，对元素的操作会给其“添加热度”，在容器满了之后，再次添加时，删除掉“热度最低”的那个)

### 题目：

实现 LRUCache 类：

- LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key，value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

注意：get(key)操作会"使用key"，put()已经存在的key也会"使用key"。凡是“使用key”都会给key添加热度。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

### 示例：

```java
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
```

来源：[力扣（LeetCode）](https://leetcode-cn.com/problems/lru-cache)

### 实现1

#### 分析：

要想O(1)时间复杂度存取元素，大概率是使用HashMap；而元素热度会变化，超出容量时低热度元素被挤掉，则可以使用链表来维护元素位置。

#### 思路：

使用 双向链表 + HashMap实现。双向链表维护元素热度，HashMap储存元素。热度的维护靠移动元素到头部来实现，这样尾部自然就是热度最低的元素；那些会增加元素热度的操作，一律会将元素移动到头部；容量不够了，去尾部删除就行了。

#### 代码：

```java
package com.example.demo.core.Leecode;

import java.util.HashMap;

/**
 * https://leetcode-cn.com/problems/lru-cache/
 *
 * LRU: Least Recently Used.最近最少使用
 * 双向链表 + HashMap，双向链表维护元素热度，HashMap储存元素
 * 维护热度就需要有 添加元素到头部，移动元素到头部，移除尾部元素 的操作；其中，移动元素到头部可以使用删除元素和添加元素到头部两个方法实现。所以底层基本操作要有3个（添加元素到头部、删除当前元素、移除尾部元素）。
 * @author hanxu03
 */
public class LRUCache {

/**
     * 双向链表节点
     */
    class Node {
        int key;
        int value;
        Node before;
        Node after;

public Node() {
        }

public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

/**
     * 真实储存数据的容器
     */
    private HashMap<Integer, Node> cache = new HashMap<>();

/**
     * 容量
     */
    private int capacity;

/**
     * 头尾指针，并不储存元素。第一个节点的前面是head，最后一个节点的后面是tail
     */
    private Node head, tail;

/**
     * 初始化
     * @param capacity
     */
    public LRUCache(int capacity) {
        //赋值容量
        this.capacity = capacity;
        //创建头尾指针
        head = new Node();
        head.before = null;
        tail = new Node();
        tail.after = null;
        //连接头尾结点
        head.after = tail;
        tail.before = head;
    }

/**
     * 插入节点到链表头部
     * @return
     */
    private void addToHead(Node node) {
        //只知道node应该在head后面，不知道node后面是啥，所以操作时只能使用head与node
        node.before = head;
        node.after = head.after;
        //顺讯不能调换
        head.after.before = node;
        head.after = node;
    }

/**
     * 移除双向链表中的某个节点
     * @param node
     */
    private void removeNode(Node node) {
        Node before = node.before;
        Node after = node.after;
        before.after = after;
        after.before = before;
    }

/**
     * 将某节点移动到双向链表头部（head后）
     * @param node
     */
    private void moveToHead(Node node) {
        //删除当前位置
        removeNode(node);
        //添加到head后
        addToHead(node);
    }

/**
     * 删除尾部节点（tail前）
     * @return
     */
    private Node delTail() {
        //获取，删除，返回
        Node node = tail.before;
        removeNode(node);
        return node;
    }

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) {
		// (注意判定顺序不能弄混)
		// 1、判断是不是新node：是就添加，不是就更新
        // 	2、判断添加后是否超出容量：是就移除尾部元素
        Node node = cache.get(key);
        //如果是新Node
        if (node == null) {
            Node newNode = new Node(key, value);
            //新来的都是最热的（放在头部）
            addToHead(newNode);
            cache.put(key, newNode);
            //如果添加后容量超出，则弹出尾部元素
            if (cache.size() > capacity) {
                Node lastNode = delTail();
                cache.remove(lastNode.key);
            }
        } else {
            //不是新Node就替换vale，并加热元素（放到链表前面）
            node.value = value;
            moveToHead(node);
        }
    }

public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1)); // 1
        lruCache.put(3, 3); //
        System.out.println(lruCache.get(2)); // -1
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1)); // -1
        System.out.println(lruCache.get(3)); // 3
        System.out.println(lruCache.get(4)); // 4
    }
}
```

### 实现2

#### 思路：

JDK中的LinkedHashMap，可以实现元素按照访问顺序倒叙输出：（先访问的最后迭代出来，就是把先访问的放在后面）

> 注意，第三个入参accessOrder需要为true才能实现这个效果。

```java
	public static void main(String[] args) {
        LinkedHashMap<Object, Object> linkedHashMap = new LinkedHashMap<>(2, 0.75F, true);
        linkedHashMap.put(1, 1);
        linkedHashMap.put(2, 2);
        linkedHashMap.get(1);
        linkedHashMap.put(3, 3);
        linkedHashMap.put(4, 4);
        System.out.println(linkedHashMap);
        /*
        头部  ---->  尾部
        本来是 1,1 2,2
        当get(1)时，会把1,1放在尾部
        变成了 2,2 1,1   再放入3,3 4,4
        变成了 2,2 1,1 3,3 4,4
        输出时从头部到尾部输出
         */
        //{2=2, 1=1, 3=3, 4=4}
    }
```

LinkedHashMap继承HashMap，HashMap的putVal方法在添加元素后，又会执行一个`afterNodeInsertion(evict);`方法，这个方法就是添加元素之后做的事情。它在HashMap中是一个空方法，子类可以实现它。

```java
void afterNodeInsertion(boolean evict) { }
```

而LinkedHashMap的实现是这样的：

```java
	void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
```

当满足`(evict && (first = head) != null && removeEldestEntry(first))`这些条件时，会将头部元素删除（`removeNode(hash(key), key, null, false, true)`）。

我们想一下，尾部元素是最近常访问的，那头部元素自然就是最近不常访问的了，所以删除头部元素刚好能满足我们的诉求。

接下来的问题就是什么时候删，总不能每次添加元素都把尾部删除吧。我们来看这个条件：

evict传过来就是true，有元素时head!=null，剩下的就是`removeEldestEntry(first)`了。我们的诉求是当空间不够时删除尾部元素。所以我们只需要控制`removeEldestEntry`这个方法，当空间不够时返回true即可！

```java
	@Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
```

总结一下这个实现思路：LinkedHashMap可以控制元素按照访问顺序倒叙遍历（内部将常访问的元素放在尾部），又有一个方法afterNodeInsertion可以在添加元素后干一些事情，而LinkedHashMap的实现就是删除头部元素，所以我们可以自由定制我们要在什么条件下删除那些元素。

#### 代码：

```java
package com.example.demo.core.Leecode;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author: HanXu
 * on 2022/2/24
 * Class description: JDK中的LinkedHashMap实现LRU
 */
public class LRUCache2 extends LinkedHashMap<Integer, Integer> {

private int capacity;

public LRUCache2(int capacity) {
        //这里必须为true
        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);
    }

/**
     * 这个必须有，控制添加元素后，哪些情况下删除头部元素
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

public static void main(String[] args) {
        LRUCache2 lruCache2 = new LRUCache2(2);
        lruCache2.put(1, 1);
        lruCache2.put(2, 2);
        System.out.println(lruCache2.get(1)); // 1
        lruCache2.put(3, 3); //
        System.out.println(lruCache2.get(2)); // -1
        lruCache2.put(4, 4);
        System.out.println(lruCache2.get(1)); // -1
        System.out.println(lruCache2.get(3)); // 3
        System.out.println(lruCache2.get(4)); // 4
    }
}
```

### 为什么需要双向链表+hashMap？
使用其他数据结构能实现吗？可以。只不过双向链表+hasMap是相对最优解。
这里的双向链表能换成单向链表吗？能，就算只使用单向链表也是可以的。
但如果换成单向链表，删除node节点时，就需要从前向后遍历，拿到node的前驱节点，才能删除；而双向链表，则可以直接获得node的前驱节点。双向链表+hashMap，所有操作时间复杂度都趋向于O(1)。

文章目录

发表评论