LRU算法原理及实现

发表于 | | 阅读次数:

LRU原理简介

LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。

LRU 算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

比如:计算机为每个进程分配三块可用物理内存，现在数据为0，1，2，3，4。所以不可能把这5个数据都放在物理内存之中，每个数据的使用权重也是不一样的。比如数据使用顺序为1，3，4，1，2，0，4，2。假如一开始三块内存块都为空，我们来模拟一下LRU算法的过程：

这就是LRU算法的基本原理，那我们应该怎么实现LRU算法呢？

LRU算法实现

1.首先要保证数据可以随时取用，比如内存块中的数据为1，3，2.取1，3，2的复杂度都应该为O(1),并且需要取中间数进行刷新到头部，这很符合散列表的特性。所以我们会利用Java中的HashMap进行数据的存储获取

2.数据应该是有序的，我需要保证每次插入头节点的数据是最新的，去除尾部的历史数据。这种头尾更新数据的操作用数据需要频繁移动数据，所以需要用链表。当更新中间数据时需要链接前后链表，删除尾部时需要更新尾部指针到它上一个指针的位置，所以双向链表更方便这种操作。

3.用队列实现这种先后顺序行吗？不可以，因为需要查找到中间已存在的元素更新到头部。

1.准备一个双向链表数据结构

1
2
3
4
5
6
class DoubleLinkedNode {
    int key;
    int value;
    DoubleLinkedNode pre;
    DoubleLinkedNode post;
}

对于一个LRU算法实现，需要至少两个操作：
get(key)，set(key,value)

当get(key)的时候，如果key不存在，返回-1，若key存在，刷新对应的数据到链表头部

put(key,value) ,如果key存在，获取对应的值并刷新到头部。如果不存在，存储值到头部，若存储的数量已超出最大值，则去掉尾部的节点并移除掉map中的数据。

LRU实现

具体的实现如下：

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.util.HashMap;

public class LRUCache {

    private HashMap<Integer, DoubleLinkedNode>
            cache = new HashMap<>();
    private int count;
    private int capacity;
    private DoubleLinkedNode head, tail;

    /**
     * 构造LRU，设置两个头尾节点
     * @param capacity
     */
    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;
        head = new DoubleLinkedNode();
        tail = new DoubleLinkedNode();
        head.post = tail;
        tail.pre = head;
    }

    /**
     * 获取key对应的值
     * @param key 
     * @return 值
     */
    public int get(int key) {

        DoubleLinkedNode node = cache.get(key);
        if(node == null){
            return -1;
        }

        this.moveToHead(node);

        return node.value;
    }


    /**
     * 设置key，value
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        DoubleLinkedNode node = cache.get(key);

        if(node == null){

            DoubleLinkedNode newNode = new DoubleLinkedNode();
            newNode.key = key;
            newNode.value = value;

            this.cache.put(key, newNode);
            this.addNode(newNode);

            ++count;

            //如果超过最大值则删除尾部节点和map中的数据
            if(count > capacity){
                DoubleLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        }else{
            node.value = value;
            this.moveToHead(node);
        }
    }

    /**
     * 插入头节点
     * @param node
     */
    private void addNode(DoubleLinkedNode node){
        node.pre = head;
        node.post = head.post;

        head.post.pre = node;
        head.post = node;
    }

    /**
     * 删除节点
     * @param node
     */
    private void removeNode(DoubleLinkedNode node){
        DoubleLinkedNode pre = node.pre;
        DoubleLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }

    /**
     * 移动到头节点
     * @param node
     */
    private void moveToHead(DoubleLinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }

    /**
     * 删除尾节点
     * @return 尾节点
     */
    private DoubleLinkedNode popTail(){
        DoubleLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }
}

class DoubleLinkedNode {
    int key;
    int value;
    DoubleLinkedNode pre;
    DoubleLinkedNode post;
}

LRU算法在很多框架中有很对应的实现或者变种实现，目前就介绍到这里.