算法通关村-----LRU的设计与实现

LRU 缓存

问题描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

问题分析

cache的优点是速度快，缺点是价格高，因此cache的容量是在平衡速度与价格基础上设计的。当cache已满，在添加元素时，无法添加，我们需要先移除，在添加，LRU是一种移除策略，最近最少使用，即移除最长时间未访问的元素。题目中要求get和put在常数时间内完成，get操作是先定位，然后返回，定位的常数时间，我们直接使用Hash即可，put操作是先get，看能不能获取到，如果存在，我们需要改变值，不存在添加值，get操作使用Hash，找到后，添加或更新是可以直接操作的。那么我们如何确定最近最少使用呢，假设我们有一个线性空间（很明显不适合用树或图，所以假设线性空间）,我们可以将元素按照最近最多使用到最近最少使用的顺序存放，即如果一个元素被访问了，立即放在最前面，如此，最后面就是就近最少使用。另外，当缓存满了，我们需要从最后方移除元素。数组无法在线性时间移除，单链表、栈无法同时操作前后端进行添加或移除，队列只能从队尾入，队头出，无法实现世界添加到队头，因此，我们只能使用双向链表或者双端队列了。最终我们的结论是，使用Hash在常数时间内获取，使用双向链表实现最近最少使用的添加和删除。

代码实现

class LRUCache {
    class DoubleLinkedNode{
        int key;
        int value;
        DoubleLinkedNode pre;
        DoubleLinkedNode next;

        public DoubleLinkedNode(){

        }

        public DoubleLinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    Map<Integer,DoubleLinkedNode> map;
    DoubleLinkedNode head;
    DoubleLinkedNode tail;
    int size;
    int capacity;
    public LRUCache(int capacity) {
        map = new HashMap<>();
        head = new DoubleLinkedNode();
        tail = new DoubleLinkedNode();
        head.next = tail;
        tail.pre = head;
        size = 0;
        this.capacity = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            DoubleLinkedNode node = map.get(key);
            remove(node);
            addToHead(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            DoubleLinkedNode node = map.get(key);
            node.value = value;
            remove(node);
            addToHead(node);
        }else{
            DoubleLinkedNode node = new DoubleLinkedNode(key, value);
            map.put(key, node);
            addToHead(node);
            size++;
            if(size>capacity){
                int removeKey = removeFromTail();
                map.remove(removeKey);
                size--;
            }
        }
    }

    public void remove(DoubleLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void addToHead(DoubleLinkedNode node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    public int removeFromTail() {
        DoubleLinkedNode pre = tail.pre;
        remove(tail.pre);
        return pre.key;
    }
}

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