2024-06-05-链表复习第四篇.md

发表于 | 分类于
基于双端链表的LRU缓存

LRU缓存实现

题目在这里，LeetCode 146 LRU 缓存

首先明确LRU策略缓存：Least Recently Used，最近最少使用，也就是在缓存删除的时候，优先选择最近没有使用过的缓存。

双端链表+哈希表算是LRU缓存的标准实现了。

看下LRU class的方法定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class LRUCache {


  /**
   * 缓存初始化
   * @param capacity 缓存大小
   */
  public LRUCache(int capacity) {

  }

  /**
   * 从缓存中获取key
   * @param key key
   * @return 对应的value
   */
  public int get(int key) {

  }

  /**
   * 往缓存中set Key和value
   * @param key key
   * @param value value
   */
  public void put(int key, int value) {

  }
}

get操作：

  • 获取key对应的value
  • 更新当前key为最近使用的key、value

set操作：

  • 检查当前缓存是否还有容量，如果有的话直接set
  • 如果当前缓存已经没有容量，删除使用时间最久远的key，然后set

哈希表用来存储数据，get和set都依托于哈希表操作肯定没问题；

关键操作在于记录使用记录，双端链表非常适合这个场景只需要：

  • 插入数据的时候，将数据移动到链表的头部；
  • 删除数据的时候从链表的尾部删除；

双端链表

1
2
3
4
5
6
7
8
9
10
11
12
public class ListNode {

  int key;
  int value;
  ListNode prev;
  ListNode next;

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

双端链表的关键操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class ListNodeUtil {

  protected static void addNode(ListNode node, ListNode head) {
    node.prev = head;
    node.next = head.next;

    head.next.prev = node;
    head.next = node;
  }

  private static void removeNode(ListNode node) {
    ListNode prev = node.prev;
    ListNode next = node.next;

    prev.next = next;
    next.prev = prev;
  }

  protected static void moveToHead(ListNode node, ListNode head) {
    removeNode(node);
    addNode(node, head);
  }

  protected static ListNode popTail(ListNode tail) {
    ListNode res = tail.prev;
    removeNode(res);
    return res;
  }
}

完整版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.HashMap;

public class LRUCache {

  private int capacity;
  private HashMap<Integer, ListNode> map;
  private ListNode head;
  private ListNode tail;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<>();
    this.head = new ListNode(0, 0);
    this.tail = new ListNode(0, 0);
    head.next = tail;
    tail.prev = head;
  }

  public int get(int key) {
    if (!map.containsKey(key)) {
      return -1; // 缓存中不存在该数据
    }
    ListNode node = map.get(key);
    ListNodeUtil.moveToHead(node, head); // 将访问的节点移动到链表头部
    return node.value;
  }

  public void put(int key, int value) {
    if (map.containsKey(key)) {
      ListNode node = map.get(key);
      node.value = value;
      ListNodeUtil.moveToHead(node, head); // 更新值并移动到链表头部
    } else {
      ListNode newNode = new ListNode(key, value);
      map.put(key, newNode);
      ListNodeUtil.addNode(newNode, head); // 新节点插入链表头部

      if (map.size() > capacity) {
        ListNode res = ListNodeUtil.popTail(tail);
        map.remove(res.key); // 删除哈希表中的对应项
      }
    }
  }
}

链表应该还有一点点就要结束了。