链表经常见到的另一个算法是LRU（Last Recently Used）缓存淘汰算法。

我们一说到高性能，就会使用各种缓存。页面缓存，浏览器缓存，nginx缓存，接口数据缓存。缓存可以大大提高数据获取的速度。然而，缓存减少耗时的同时需要介质存储对应的数据，介质容量是有限的，所以缓存的数据必然有限。当缓存容量满的时候，我们需要淘汰一些数据，插入新的数据。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。ps. Redis内存满了是怎么淘汰数据的？

简单的，我们可以使用双向链表来实现LRU。

假设要缓存的数据为obj，我们维护一个双向链表，链表的数据就是obj。每次访问了数据，我们需要将这个数据obj缓存到我们的双向链表中。

  1. 遍历我们的缓存链表
  2. 如果数据已经存在链表了，取下来，插入链表头部；
  3. 如果数据不在链表中：
  4. 如果链表容量没满，则将我们的obj插入链表头部；
  5. 如果链表容量已经满了，把链表结尾的节点删除，把我们的obj插入头部

双向链表

前面我们熟悉了单链表的数据结构. 而双链表就是在单链节点的基础上新增一个指向前面一个节点的指针。这样，我们可以很容易获取前后的节点。

构造Node结构如下：

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

/**
 * node
 *
 * @author Ryan Miao
 */
@Data
public class Node {
    private boolean head = false;
    private Integer data;
    private Node next;
    private Node pre;

    public Node() {
    }

    public static Node head() {
        Node node = new Node();
        node.setHead(true);
        node.setData(-1);
        return node;
    }

    public static Node normal(Integer data) {
        Node node = new Node();
        node.setHead(false);
        node.setData(data);
        return node;
    }

    public void insert(Node node) {
        node.setNext(this.getNext());
        node.setPre(this);
        if (this.getNext() != null) {
            this.getNext().setPre(node);
        }
        this.setNext(node);
    }

    public String print() {
        StringBuilder sb = new StringBuilder();
        Node p = this;
        Node theNext = p.getNext();
        if (!p.isHead()) {
            sb.append(p.getData());
            if (theNext != null) {
                sb.append("->");
            }
        }

        while (theNext != null && !theNext.isHead()) {
            sb.append(theNext.getData());
            theNext = theNext.getNext();
            if (theNext != null && !theNext.isHead()) {
                sb.append("->");
            }

        }
        
        return sb.toString();
    }
    
}

根据前面的路程图，对于LRU cache, 我们可以分成这几个部分：

  • 检查链表是否存在给定data
  • 取下一个节点
  • 删除尾巴节点
  • 插入头部

构造一个链表

首先创建一个成员变量存储链表。

1
2
private final Node cacheHead = Node.head();
private final AtomicInteger size = new AtomicInteger(0);

查询缓存链表中是否存在data

遍历链表，从链表中查询是否包含data节点。如果找到data节点，取下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 1.find if exist remove
Node firstNode = cacheHead.getNext();
Node cur = firstNode;
// 遍历指针，直到null或者head节点。
while (cur != null && !cur.isHead()) {
    //因为是循环链表， curNext永远不为null，不过可以做个检测校验
    Node curNext = cur.getNext();
    if (data.equals(cur.getData())) {
        // remove
        Node pre = cur.getPre();
        log.debug("exist, remove {}, pre{} -> next{}", cur.getData(), pre.getData(), curNext.getData());
        pre.setNext(curNext);
        curNext.setPre(pre);
        size.decrementAndGet();

        node = cur;
        node.setNext(null);
        node.setPre(null);
        break;
    }

    cur = curNext;
}

删除尾节点

当缓存链表已经满了，即缓存满了，要删除链表最后的一个节点。

1
2
3
4
5
Node tail = cacheHead.getPre();
Node tailPre = tail.getPre();
tailPre.setNext(cacheHead);
cacheHead.setPre(tailPre);
size.decrementAndGet();

插入头节点

要缓存的新数据放入链表头部。

1
2
3
4
5
6
7
8
9
10
11
12
// 2.insert to head
if (firstNode == null) {
    cacheHead.setPre(node);
    cacheHead.setNext(node);
    node.setPre(cacheHead);
    node.setNext(cacheHead);
} else {
    node.setNext(cacheHead.getNext());
    cacheHead.getNext().setPre(node);
    cacheHead.setNext(node);
    node.setPre(cacheHead);
}

完整代码

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

static class MyLRUCache {

    private static final int CACHE_MAX_SIZE = 4;


    private final Node cacheHead = Node.head();
    private final AtomicInteger size = new AtomicInteger(0);

    public void add(Integer data) {
        log.debug("add {}", data);
        //要插入的node
        Node node = null;

        // 1.find if exist remove
        Node firstNode = cacheHead.getNext();
        Node cur = firstNode;
        while (cur != null && !cur.isHead()) {
            Node curNext = cur.getNext();
            if (data.equals(cur.getData())) {
                // remove
                Node pre = cur.getPre();
                log.debug("exist, remove {}, pre {} -> next {}", cur.getData(), pre.getData(), curNext.getData());
                pre.setNext(curNext);
                curNext.setPre(pre);
                size.decrementAndGet();

                node = cur;
                node.setNext(null);
                node.setPre(null);
                break;
            }

            cur = curNext;
        }

        // if not found and full remove the last
        if (node == null) {
            node = Node.normal(data);
            if (size.get() == CACHE_MAX_SIZE) {
                Node tail = cacheHead.getPre();
                Node tailPre = tail.getPre();
                tailPre.setNext(cacheHead);
                cacheHead.setPre(tailPre);
                size.decrementAndGet();
            }
        }

        // 2.insert to head
        if (firstNode == null) {
            cacheHead.setPre(node);
            cacheHead.setNext(node);
            node.setPre(cacheHead);
            node.setNext(cacheHead);
        } else {
            node.setNext(cacheHead.getNext());
            cacheHead.getNext().setPre(node);
            cacheHead.setNext(node);
            node.setPre(cacheHead);
        }

        size.incrementAndGet();
        if (log.isDebugEnabled()) {
            log.debug("current cache: {}", cacheHead.print());
        }
    }

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@Test
public void testCache() {
    MyLRUCache cache = new MyLRUCache();
    cache.add(1);
    cache.add(1);
    cache.add(2);
    for (int i = 0; i < 4; i++) {
        cache.add(i);
    }

    cache.add(1);
    cache.add(2);
    cache.add(3);
    cache.add(4);
    cache.add(4);
}

打印结果：

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
23:28:02.828 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 1
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 1
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 1
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - exist, remove 1, pre -1 -> next -1
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 1
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 2
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 2->1
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 0
23:28:02.834 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 0->2->1
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 1
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - exist, remove 1, pre 2 -> next -1
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 1->0->2
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 2
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - exist, remove 2, pre 0 -> next -1
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 2->1->0
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 3
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 3->2->1->0
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 1
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - exist, remove 1, pre 2 -> next 0
23:28:02.835 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 1->3->2->0
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 2
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - exist, remove 2, pre 3 -> next 0
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 2->1->3->0
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 3
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - exist, remove 3, pre 1 -> next 0
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 3->2->1->0
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 4
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 4->3->2->1
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - add 4
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - exist, remove 4, pre -1 -> next 3
23:28:02.836 [Test worker] DEBUG com.test.algorithm.link.LRUCache - current cache: 4->3->2->1

可以发现，缓存基本实现了，最近访问的放到链表头部。当缓存满了，删除了尾节点。

当然，有个最简单的优化地方，当只有一个节点的时候，或者说当要添加的节点就是第一个节点的时候，不需要操作。在这里我们，1和4每次加入的时候都删除了第一个节点，然后再插入。

优化 - hash table