JanGin's BLOG
主页
归档
标签
分类
avatar
文章
42
标签
43
分类
15
主页
归档
标签
分类
目录
  1. 1. 什么是LRU
  2. 2. 实现思路
  3. 3.实现方式
    1. 1. 双向链表
    2. 2. 双向链表加哈希表
    3. 3. LinkedHashMap
实现一个LRU缓存
|数据结构
字数总计:1.5k|阅读时长: 7 分钟

该篇文章旨在通过链表和哈希表结合实现LRU算法.

1. 什么是LRU

LRU，即 least recently used, 最近最少使用算法，当内存达到上限时，它会选择距离最近最久未使用过的部分淘汰掉，以此腾出内存空间。 该算法常见的应用场景一般有以下几个：1. 应用缓存的淘汰策略。2. 操作系统内存页面的置换淘汰。

2. 实现思路

维护一个有限个节点数量的链表，其中包含两个dummy节点，一头一尾，越靠近尾节点的节点数据是越早被访问过的。在这俩节点之间的全部节点即为容器的容量(capacity). 节点的数据结构长这样：

Code
1
2
3
4
5
6
7
8
9
10
11
12
private static class Node<K, V> {
    K key;
    V value;
    Node prev;
    Node next;
    Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.prev = this.next = null;
    }

}

当有一个新数据到达往容器里面put的时候，存在数据已经存在和不存在两个情况：

  1. 当数据在缓存中已存在, 此时又分为两种情况：

(1). 此时容器容量已满，只需把数据所在的原来节点从原来的位置上断开链接后将该节点往容器链表的开头位置放，即first节点后的第一个位置，容器此时的缓存个数不变。

(2). 若此时未达到容量上限，只需要把数据所在的原来节点从原来的位置上断开链接，并把该节点往容器链表的开头位置放。

  1. 数据不在缓存中，同样也分两种情况：

(1). 容器容量已满的情况下，需要首先删除last节点的前置节点，然后按照第一种情况的(1)方式操作。

(2). 容器容量未满，将新建一个节点，并将该节点往 first 节点后的第一个位置放，同时容器的容量加1.

3.实现方式

1. 双向链表
Code
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
public class LRUCache<K, V> {

    private Node<K, V> first;

    private Node<K, V> last;

    private int capacity;

    private int size;

    private static class Node<K, V> {
        K key;
        V value;
        Node prev;
        Node next;
        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        first = new Node(-1, -1);       //dummy node
        last = new Node(-1, -1);
        first.prev = null;
        first.next = last;
        last.prev = first;
        last.next = null;
        size = 0;
    }


    public void put(K key, V val) {
        Node<K, V> pos = null;
        for (Node node = first; node != last;) {
            if (node.key == key && node.value == val) {
                pos = node;
                break;
            }
            node = node.next;
        }
        //说明存在
        if (pos != null) {
            deleteNode(pos);
            moveToHead(pos);
        } else {
            pos = new Node<>(key, val);
            if (size < capacity) {
                moveToHead(pos);
                ++size;
            } else {
                deleteNode(last.prev);
                moveToHead(pos);
            }

        }

    }

    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        node.next = first.next;
        node.next.prev = node;
        node.prev = first;
        first.next = node;

    }

    public V get(K key) {
       for (Node<K, V> node = first; node != last;) {
           if (node.key == key) {
               V res = node.value;
               deleteNode(node);
               moveToHead(node);
               return res;
           }
           node = node.next;
       }
       return null;
    }


    public static void main(String[] args) {

        LRUCache<Integer, Character> lru = new LRUCache<>(2);
        lru.put(1, 'a');
        lru.put(2, 'b');
        System.out.println(lru.get(1));     // return 'a'
        System.out.println(lru.get(2));     // return 'b'
        lru.put(3, 'c');                    // it will evict the value on key 1
        System.out.println(lru.get(1));     // return null
        lru.put(4, 'c');                    // it will evict the  value 'b'
        System.out.println(lru.get(2));     // return null
    }
}

分析一下上述的LRU实现，会发现put() 和 get() 的时间复杂度都是O(n), 存在着优化空间。 利用空间换时间的基本指导思想，我们可以在内部维护一个哈希表，将put() 和 get() 的时间复杂度降到O(1).

2. 双向链表加哈希表
Code
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
public class LRUCache<K, V> {

    private Node<K, V> first;

    private Node<K, V> last;

    private int capacity;

    private int size;

    private Map<K, Node> cache;

    private static class Node<K, V> {
        K key;
        V value;
        Node prev;
        Node next;
        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    public LRUCache(int capacity) {
        cache = new HashMap<>();
        this.capacity = capacity;
        first = new Node(-1, -1);       //dummy node
        last = new Node(-1, -1);
        first.prev = null;
        first.next = last;
        last.prev = first;
        last.next = null;
        size = 0;
    }


    public void put(K key, V val) {
       
        if (cache.get(key) != null) {
            Node node = map.get(key);
            deleteNode(pos);
            moveToHead(pos);
        } else {
            Node n = new Node<>(key, val);
            cache.put(key, n);
            if (size < capacity) {
                moveToHead(pos);
                ++size;
            } else {
                cache.remove(last.pre.key);
                deleteNode(last.prev);
                moveToHead(pos);
            }

        }

    }

    public V get(K key) {
        if (cache.get(key) != null) {
            Node node = cache.get(key);
            V result = node.value;
            deleteNode(node);
            moveToHead(node);
            return result;
        }
        return null;
    }

    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        node.next = first.next;
        node.next.prev = node;
        node.prev = first;
        first.next = node;

    }
}

由第二种实现方式，我们很自然地想到，这不就是LinkedHashMap的大致实现吗？ 于是又有了第三种偷懒的实现方式——借助LinkedHashMap!！

3. LinkedHashMap
Code
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
public class LRUCache extends LinkedHashMap<K, V> {
    
    private LinkedHashMap<K, V> cache;
    
    private final int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(java.util.Map.Entry<K, V> var) {
                if (this.size() > capacity)
                    return true;
                    
                return false;
            }
        };
    }
    
    public V get(K key) {
        return cache.getOrDefault(key, null);
    }
    
    public void put(K key, V value) {
        cache.put(key, value);
    }
}

（全文完）

【参考链接】：

  1. https://leetcode.com/problems/lru-cache/
文章作者: JanGin
文章链接: http://jangin.github.io/2020/09/05/implement-a-lru-cache/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 JanGin's BLOG！
LRU
评论