最近最久未使用LRU算法实现！

LRU全称是Least Recently Used，即最近最久未使用的意思。

如果一个数据在最近一段时间没有被使用，将来被使用的机会也比较小。

实现最不经常使用（LRU）缓存的数据结构：应该支持以下操作：get 和 put。

get(key)：

  • 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。

put(key, value)：

  • 如果键不存在，请设置或插入值。
  • 当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。

解决思路

单链表对于 put 操作，会出现以下几种情况：

如果要 put(key,value) 已经存在于链表之中（根据key来判断）：

  • 那么需要把链表中旧的数据删除，然后把新的数据插入到链表的头部。

如果要 put(key,value) 的数据没有存在于链表之中：

  • 需要判断缓存区是否已满，如果满的话，则把链表尾部的节点删除，之后把新的数据插入到链表头部。

如果没有满的话，直接把数据插入链表头部即可。

单链表对于 get 操作，则会出现以下情况:

如果要 get(key) 的数据存在于链表中：

  • 则把 value 返回，并且把该节点删除，删除之后把它插入到链表的头部（表示最新用到了该节点数据）。

如果要 get(key) 的数据不存在于链表之中：

  • 则直接返回 -1 即可。

时间、空间复杂度分析

对于这种方法，put 和 get 都需要遍历链表查找数据是否存在，所以时间复杂度为 O(n)，空间复杂度为 O(1)。

哈希表+单链表

可以考虑采用空间换时间的方式来加快 get 的操作。

用一个额外哈希表（例如HashMap）来存放 key-value。

这样，get 操作就可以在 O(1) 的时间内寻找到目标节点。

还需要删除该元素，并且把该元素插入到链表头部。

删除一个元素，需要定位到这个元素的前驱的，定位到这个元素的前驱，需要 O(n) 时间复杂度。

双向链表+哈希表

采用这两种数据结构的组合，get 操作在 O(1) 时间复杂度。

由于 put 操作要删除的节点一般是尾部节点。

所以可以用一个变量 tai 时刻记录尾部节点的位置，这样，put 操作也可以在 O(1) 时间内完成。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 链表节点的定义
class LRUNode{
    String key;
    Object value;
    LRUNode next;
    LRUNode pre;

    public LRUNode(String key, Object value) {
        this.key = key;
        this.value = value;
    }
}
// LRU
public class LRUCache {
    Map<String, LRUNode> map = new HashMap<>();
    LRUNode head;
    LRUNode tail;
    // 缓存最大容量，我们假设最大容量大于 1，
    // 当然，小于等于1的话需要多加一些判断另行处理
    int capacity;

    public RLUCache(int capacity) {
        this.capacity = capacity;
    }

    public void put(String key, Object value) {
        if (head == null) {
            head = new LRUNode(key, value);
            tail = head;
            map.put(key, head);
        }
        LRUNode node = map.get(key);
        if (node != null) {
            // 更新值
            node.value = value;
            // 把他从链表删除并且插入到头结点
            removeAndInsert(node);
        } else {
            LRUNode tmp = new LRUNode(key, value);
            // 如果会溢出
            if (map.size() >= capacity) {
                // 先把它从哈希表中删除
                map.remove(tail);
                // 删除尾部节点
                tail = tail.pre;
                tail.next = null;
            }
            map.put(key, tmp);
            // 插入
            tmp.next = head;
            head.pre = tmp;
            head = tmp;
        }
    }

    public Object get(String key) {
        LRUNode node = map.get(key);
        if (node != null) {
            // 把这个节点删除并插入到头结点
            removeAndInsert(node);
            return node.value;
        }
        return null;
    }
    private void removeAndInsert(LRUNode node) {
        // 特殊情况先判断，例如该节点是头结点或是尾部节点
        if (node == head) {
            return;
        } else if (node == tail) {
            tail = node.pre;
            tail.next = null;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        // 插入到头结点
        node.next = head;
        node.pre = null;
        head.pre = node;
        head = node;
    }
}

带有过期时间的LRU实现

每一个节点放一个过期时间，只要到了这个时间就直接删除即可。

  • 添加一个过期时间队列，和一个过期清除的线程。
  • 清除的时候使用while(true)每次判断队列队首是否过期，然后判断是否返回和清除。