LRU算法

2020-09-22 约 4148 字预计阅读 9 分钟次阅读算法

前言

小王的困惑

首先考虑这样的一个业务场景,小王在A公司上班，有一天产品提出了一个需求：“咱们系统的用户啊，每天活跃的就那么多，有太多的僵尸用户，根本不登录，你能不能考虑做一个筛选机制把这些用户刨出去，并且给活跃的用户做一个排名，我们可以设计出一些奖励活动，提升咱们的用户粘性，咱们只需要关注那些活跃的用户就行了“”。小王连忙点头，说可以啊，然而心里犯起嘀咕来了：这简单，按照常规思路，给用户添加一个最近活跃时间长度和登录次数，然后按照这两个数据计算他们的活跃度，最后直接排序就行了。嘿嘿，简直完美!不过！用户表字段已经很多了，又要加两个字段，然后还得遍历所有的数据排序？这样查询效率是不是会受影响啊？并且公司的服务器上次就蹦过一次，差点没忙出命来才调好。有没有更优雅的一种方式呢？小王面朝天空45°，陷入了无限的思考中…..

LRU是什么？

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

LRU算法的设计原则是基于一个非常著名的计算机操作系统基础理论得来的：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。

基于这个思想,会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据！它的主要衡量指标是使用的时间，附加指标是使用的次数。在计算机中大量使用了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使用的数据！因为，利用LRU我们可以解决很多实际开发中的问题，并且很符合业务场景。

小王的困惑

当小王看到LRU的时候，瞬间感觉抓住了救命稻草，这个算法不是就完全契合产品的需求吗？只要把用户数据按照LRU去筛选，利用数据结构完成的事情，完全减少了自己存储、添加字段判断、排序的过程，这样对于提高服务器性能肯定有很大的帮助，岂不美哉！小王考虑好之后，就决定先写一个demo来实现LRU，那么在java中是如何实现LRU呢？考虑了许久，小王写下了这些代码。

LRU的实现

用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。第一种方法, 需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。第二种方法, 链表在定位数据的时候时间复杂度为O(n)。
利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。一般使用第三种方式来是实现LRU算法。

java实现

定义基本的链表操作节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public class Node {
    //键
    Object key;
    //值
    Object value;
    //上一个节点
    Node pre;
    //下一个节点
    Node next;
 
    public Node(Object key, Object value) {
        this.key = key;
        this.value = value;
    }
}

链表基本定义

我们定义一个LRU类，然后定义它的大小、容量、头节点、尾节点等部分，然后一个基本的构造方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public class LRU<K, V> {
    private int currentSize;//当前的大小
    private int capcity;//总容量
    private HashMap<K, Node> caches;//所有的node节点
    private Node first;//头节点
    private Node last;//尾节点
 
    public LRU(int size) {
        currentSize = 0;
        this.capcity = size;
        caches = new HashMap<K, Node>(size);
    }
}

添加元素

添加元素的时候首先判断是不是新的元素，如果是新元素，判断当前的大小是不是大于总容量了，防止超过总链表大小，如果大于的话直接抛弃最后一个节点，然后再以传入的key\value值创建新的节点。对于已经存在的元素，直接覆盖旧值，再将该元素移动到头部，然后保存在map中。

 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


/**
 * 添加元素
 * @param key
 * @param value
 */
public void put(K key, V value) {
    Node node = caches.get(key);
    //如果新元素
    if (node == null) {
        //如果超过元素容纳量
        if (caches.size() >= capcity) {
            //移除最后一个节点
            caches.remove(last.key);
            removeLast();
        }
        //创建新节点
        node = new Node(key,value);
        caches.put(key, node);
        currentSize++;
    }else {
        //已经存在的元素覆盖旧值
        node.value = value;
    }
    //把元素移动到首部
    moveToHead(node);
}

访问元素

通过key值来访问元素，主要的做法就是先判断如果是不存在的，直接返回null。如果存在，把数据移动到首部头节点，然后再返回旧值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


/**
 * 通过key获取元素
 * @param key
 * @return
 */
public Object get(K key) {
    Node node = caches.get(key);
    if (node == null) {
        return null;
    }
    //把访问的节点移动到首部
    moveToHead(node);
    return node.value;
}

如下所示，访问key=3这个节点的时候，需要把3移动到头部，这样能保证整个链表的头节点一定是特点数据(最近使用的数据！)

节点删除操作

在根据key删除节点的操作中，我们需要做的是把节点的前一个节点的指针指向当前节点下一个位置，再把当前节点的下一个的节点的上一个指向当前节点的前一个，这么说有点绕，我们来画图来看：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


/**
 * 根据key移除节点
 * @param key
 * @return
 */
public Object remove(K key) {
    Node node = caches.get(key);
    if (node != null) {
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        if (node.next != null) {
            node.next.pre = node.pre;
        }
        if (node == first) {
            first = node.next;
        }
        if (node == last) {
            last = node.pre;
        }
    }
    return caches.remove(key);
}

假设现在要删除3这个元素，我们第一步要做的就是把3的pre节点4(这里说的都是key值)的下一个指针指向3的下一个节点2，再把3的下一个节点2的上一个指针指向3的上一个节点4，这样3就消失了，从4和2之间断开了，4和2再也不需要3来进行连接，从而实现删除的效果。

移动元素到头节点

首先把当前节点移除,类似于删除的效果(但是没有移除该元素)，然后再将首节点设为当前节点的下一个,再把当前节点设为头节点的前一个节点。当前几点设为首节点。再把首节点的前一个节点设为null，这样就是间接替换了头节点为当前节点。

 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


/**
 * 把当前节点移动到首部
 * @param node
 */
private void moveToHead(Node node) {
    if (first == node) {
        return;
    }
    if (node.next != null) {
        node.next.pre = node.pre;
    }
    if (node.pre != null) {
        node.pre.next = node.next;
    }
    if (node == last) {
        last = last.pre;
    }
    if (first == null || last == null) {
        first = last = node;
        return;
    }
    node.next = first;
    first.pre = node;
    first = node;
    first.pre = null;
}

测试

代码写完了，我们来测试一下结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public static void main(String[] args) {
    LRU<Integer, String> lru = new LRU<Integer, String>(5);
    lru.put(1, "a");
    lru.put(2, "b");
    lru.put(3, "c");
    lru.put(4,"d");
    lru.put(5,"e");
    System.out.println("原始链表为："+lru.toString());
 
    lru.get(4);
    System.out.println("获取key为4的元素之后的链表："+lru.toString());
 
    lru.put(6,"f");
    System.out.println("新添加一个key为6之后的链表："+lru.toString());
 
    lru.remove(3);
    System.out.println("移除key=3的之后的链表"+lru.toString());
}

首先我们先新放入几个元素，然后再尝试访问第4个节点，再放入一个元素，再移除一个元素，看看会输出多少：

1
2
3
4


原始链表为:5:e 4:d 3:c 2:b 1:a
获取key为4的元素之后的链表:4:d 5:e 3:c 2:b 1:a
新添加一个key为6之后的链表:6:f 4:d 5:e 3:c 2:b
移除key=3的之后的链表:6:f 4:d 5:e 2:b

看结果发现和我们预期的一致，无论添加和获取元素之后整个链表都会将最近访问的元素移动到顶点，这样保证了我们每次取到的最热点的数据，这就是LRU的最重要思想。

总结

本篇博客主要讲述了LRU的算法实现，理解了LRU也能帮助我们理解LinkedList，因为linkedList本身就是双向链表。还有就是理解数据结构这种方式，以及LRU的移动节点的过程，如果能在实际的开发中利用它的特性使用到合适的业务场景中。

附1: java实现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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160


import java.util.HashMap;
 
public class LRU<K, V> {
    private int currentSize;//当前的大小
    private int capcity;//总容量
    private HashMap<K, Node> caches;//所有的node节点
    private Node first;//头节点
    private Node last;//尾节点
 
    public LRU(int size) {
        currentSize = 0;
        this.capcity = size;
        caches = new HashMap<K, Node>(size);
    }
 
    /**
     * 放入元素
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        Node node = caches.get(key);
        //如果新元素
        if (node == null) {
            //如果超过元素容纳量
            if (caches.size() >= capcity) {
                //移除最后一个节点
                caches.remove(last.key);
                removeLast();
            }
            //创建新节点
            node = new Node(key,value);
        }
        //已经存在的元素覆盖旧值
        node.value = value;
        //把元素移动到首部
        moveToHead(node);
        caches.put(key, node);
    }
 
    /**
     * 通过key获取元素
     * @param key
     * @return
     */
    public Object get(K key) {
        Node node = caches.get(key);
        if (node == null) {
            return null;
        }
        //把访问的节点移动到首部
        moveToHead(node);
        return node.value;
    }
 
    /**
     * 根据key移除节点
     * @param key
     * @return
     */
    public Object remove(K key) {
        Node node = caches.get(key);
        if (node != null) {
            if (node.pre != null) {
                node.pre.next = node.next;
            }
            if (node.next != null) {
                node.next.pre = node.pre;
            }
            if (node == first) {
                first = node.next;
            }
            if (node == last) {
                last = node.pre;
            }
        }
        return caches.remove(key);
    }
 
    /**
     * 清除所有节点
     */
    public void clear() {
        first = null;
        last = null;
        caches.clear();
    }
 
    /**
     * 把当前节点移动到首部
     * @param node
     */
    private void moveToHead(Node node) {
        if (first == node) {
            return;
        }
        if (node.next != null) {
            node.next.pre = node.pre;
        }
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        if (node == last) {
            last = last.pre;
        }
        if (first == null || last == null) {
            first = last = node;
            return;
        }
        node.next = first;
        first.pre = node;
        first = node;
        first.pre = null;
    }
 
    /**
     * 移除最后一个节点
     */
    private void removeLast() {
        if (last != null) {
            last = last.pre;
            if (last == null) {
                first = null;
            } else {
                last.next = null;
            }
        }
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node node = first;
        while (node != null) {
            sb.append(String.format("%s:%s ", node.key, node.value));
            node = node.next;
        }
        return sb.toString();
    }
     
 
    public static void main(String[] args) {
        LRU<Integer, String> lru = new LRU<Integer, String>(5);
        lru.put(1, "a");
        lru.put(2, "b");
        lru.put(3, "c");
        lru.put(4,"d");
        lru.put(5,"e");
        System.out.println("原始链表为:"+lru.toString());
 
        lru.get(4);
        System.out.println("获取key为4的元素之后的链表:"+lru.toString());
 
        lru.put(6,"f");
        System.out.println("新添加一个key为6之后的链表:"+lru.toString());
 
        lru.remove(3);
        System.out.println("移除key=3的之后的链表:"+lru.toString());
    }
}

目录