LRU(least recently used)

发表于 | 分类于 | 阅读次数:
字数统计: 1,301 | 阅读时长 ≈ 5

不同的缓存策略适合不同的场景，这样可以保证在系统稳定的情况下拥有更好的缓存命中率，避免频繁去数据库“拿”数据。

原理

LRU是最近最少使用策略，根据元素最后一次被访问的时间来决定清除哪一部分数据，较远使用的数据较先清除，每当数据被访问后会更新它被访问的时间。

下面举例演示原理，现在假设有一个限定容量为5的LRU缓存，现往其中添加数据：

1
2
3
4
5
cache.set(1, 2);
cache.set(2, 3);
cache.set(3, 4);
cache.set(4, 5);
cache.set(5, 6);

此时如果继续添加(6, 7)，由于容量为5，需要删除原有的数据，在已存在的数据中，(1, 2)最后一次访问的时间距离当前最远，所以删除(1, 2)，输出结果为：

1
2
3
4
5
(2, 3);
(3, 4);
(4, 5);
(5, 6);
(6, 7)

如果此时对(2, 3)进行访问，那么当cache继续添加数据时，被剔除的将是(3, 4)，因为此时该数据最后一次被访问时间离当前最久远。

接下来看看LeetCode的要求：Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

本篇也将实现get()和set()方法。

实现

实现get()和set()方法之前，需要先实现两个工具方法，分别是remove()和setHead()，这两个方法主要是对双向链表进行操作，这里的链表是不同entry的value值构成的链表，并不涉及entry之间的链接。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void remove(Node node) {
    if (node.pre != null) {
        node.pre.next = node.next;
    } else {
        head = node.next;
    }
    if (node.next != null) {
        node.next.pre = node.pre;
    } else {
        end = node.pre;
    }
}

上面这段代码的含义是在双向链表中remove一个指定节点，很容易理解。

添加新节点的时候，访问时间是最新的，而如果只是对既有节点进行查询，即使没有修改节点value值，访问时间也会更新。这两种情形的代码编写都需要一个设置链表表头的工具方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void setHead(Node node) {
    node.next = head;
    node.pre = null;
    if (head != null) {
        head.pre = node;
    }
    head = node;
    if (end == null) {
        end = head;
    }
}

将一个节点设置为表头说明它的访问时间是最近的，被清除的优先级最低。

Get

get()方法是这样一种方法：首先在cache内查找是否存在以传入参数为键的键值对，如果存在，获取value值，将value设置为双向链表的表头(因为此时相当于刚刚访问键值对，设置到表头表示该数据被清除的优先级最低)；如果不存在，则返回-1，具体代码如下：

1
2
3
4
5
6
7
8
9
public int get(int key) {
    if (map.containsKey(key)) {
        Node node = map.get(key);
        remove(node);
        setHead(node);
        return node.val;
    }
    return -1;
}

Set

set()分两步走，一是当要设置的键原本存在，此时类似于进行了一次get()，只不过最后将键值对的值设置为要设置的值(实际上，在本程序中，需要设置的是键值对值的值，这个在最后再进行说明)；一是当要设置的键不存在，此时除了需要添加新的数据到cache和双向链表以外，还应考虑是否超过cache的容量，如果是，需要清除最远访问时间的数据，完整代码见下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void set(int key, int val) {
    if (map.containsKey(key)) {
        Node old = map.get(key);
        old.val = val;
        remove(old);
        setHead(old);
    } else {
        Node newNode = new Node(val);
        if (map.size() >= size) {
            // 此时如果删除hash桶的引用，node由于还在链表上有被引用，所以不被马上回收
            Collection<Node> col = map.values();
            col.remove(end);
            remove(end);
            setHead(newNode);
        } else {
            setHead(newNode);
        }
        map.put(key, newNode);
    }
}

小结

首先说说本篇算法最关键的一个细节，LRUCache将存储交给了HashMap来实现，HashMap内部是通过Entry来维护一个键值对，Entry相当于HashMap的Node，一般情况下，键和值都存入Entry中，但是此算法中的Entry维护一个(key, node)，而node中的value才是真正的value，这样处理的好处是，在node中可以定义前驱和后继，用以构造双向链表，双向链表可以控制LRUCache的大小，同时定义每个node的被访问时间优先级，Node的实现代码如下：

1
2
3
4
5
6
7
8
9
class Node {
    int val;
    Node pre;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}

由于在本算法中，本人没有在Node中定义key(这样节约不少空间，但是却花费了更多时间，属于用时间换空间，不过在这里本意是想尝试通过值而不是通过键来做删除动作)，所以在set()中，当我要删除一个满足条件的entry的key时，采用的是如下代码：

1
2
Collection<Node> col = map.values();
col.remove(end);

第二行代码并不会删除end指向的对象，对象的回收当然是交给虚拟机，虽然此时HashMap对end采用remove()操作，双向链表对end指向对象的引用仍然存在，然后再remove(end)，强调一下后者是LRUCache提供的方法，不是HashMap的方法。

参考

Java实现LRU