LRU替换算法 - 哈希表、双链表

题目描述

编程模拟实现利用LRU(最近最久未使用)替换算法的缓存.

题目分析

LRU算法: 即最近最久未使用算法.

假设最上方为最近使用的元素:
3			  4			    5
4 -> get(4) -> 3 -> set(5) -> 4
2			  2			    3
1
2
3
4

数据结构选取HashMap, 双链表.

HashMap: 记录 键值对:<key, Node<key, value>>.

链表: 记录Node<key, value>

这里使用HashMap, 可以将查找的时间复杂度降低为O(1).

代码

package cn.geek51.nowcoder.class01;
/**
 * 最近最久未使用算法(LRU)实现
 * HashMap + 双向链表
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Node<K, V> {
    public Node<K, V> last;
    public Node<K, V> next;
    public K key;
    public V value;
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.last = null;
        this.next = null;
    }

    @Override
    public String toString() {
        return "key:" + this.key + " value:" + this.value;
    }
}
class MyCache<K, V> {
    private int capacity = 0;
    private HashMap<K, Node<K, V>> keyNodeMap;
    private NodeDoubleLinkedList<K, V> nodeList;
    public MyCache(int capacity) {
        this.nodeList = new NodeDoubleLinkedList<>();
        this.keyNodeMap = new HashMap<>();
        this.capacity = capacity;
    }

    // 获取缓存中元素值
    public V get(K key) {
        if (this.keyNodeMap.containsKey(key)) {
            Node<K, V> node = this.keyNodeMap.get(key);
            this.nodeList.moveToLastNode(node);
            return node.value;
        } else {
            return null;
        }
    }

    public void set(K key, V value) {
        if (this.keyNodeMap.containsKey(key)) {
            // 缓存中已经存在
            Node<K, V> node = this.keyNodeMap.get(key);
            node.value = value;
            this.nodeList.moveToLastNode(node);
        } else {
            Node<K, V> newNode = new Node<>(key, value);
            this.keyNodeMap.put(key, newNode);
            this.nodeList.addNode(newNode);
            // 考虑替换
            if (this.keyNodeMap.size() == capacity + 1) {
                Node<K, V> removeNode = this.nodeList.removeHead();
                this.keyNodeMap.remove(removeNode.key);
            }
        }
    }

    // 删除缓存元素
    public Node<K, V> del(K key) {
        if (key == null) return null;
        if (this.keyNodeMap.containsKey(key)) {
            Node<K, V> removeNode = this.keyNodeMap.get(key);
            this.keyNodeMap.remove(key);
            this.nodeList.deleteNode(removeNode);
            return removeNode;
        } else {
            return null;
        }
    }

    // 获取所有节点的数组
    public List<Node<K, V>> all() {
        return this.nodeList.getAllNode();
    }
}

class NodeDoubleLinkedList<K, V> {

    public Node<K, V> head;
    public Node<K, V> tail;

    public NodeDoubleLinkedList() {
        this.head = null;
        this.tail = null;
    }

    public void addNode(Node<K, V> newNode) {
        if (newNode == null) return;
        // 链表中无节点
        if (this.head == null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            // 链表中有节点, 添加到尾部
            this.tail.next = newNode;
            newNode.last = this.tail;
            newNode.next = null;
            this.tail = newNode;
        }
    }

    // 删除指定节点
    public void deleteNode(Node<K, V> removeNode) {
        if (removeNode == null) return;
        if (head == removeNode) {
            // 如果是头节点
            this.head = removeNode.next;
            head.last = null;
        } else if (tail == removeNode) {
            // 如果是尾节点
            this.tail = this.tail.last;
            this.tail.next = null;
            removeNode.last = null;
            removeNode.next = null;
        } else {
            removeNode.last.next = removeNode.next;
            removeNode.next.last = removeNode.last;
            removeNode.last = null;
            removeNode.next = null;
        }

    }

    // 移动元素到链表尾部, 操作已经存在缓存中的元素时触发
    public void moveToLastNode(Node<K, V> node) {
        if (this.tail == node) return;
        // 原来是头部元素
        // 先断开与原链表的连接
        if (this.head == node) {
            this.head = this.head.next;
            this.head.last = null;
        } else {
            node.last.next = node.next;
            node.next.last = node.last;
        }
        this.tail.next = node;
        node.last = tail;
        tail = node;
    }

    // 删除
    public Node<K, V> removeHead() {
        // 链表为空
        if (this.head == null) return null;
        // 获取头部元素
        Node<K, V> res = head;
        if (this.head == this.tail) {
            this.head = null;
            this.tail = null;
        } else {
            // 多于1个元素
            this.head = res.next;
            res.next = null;
            this.head.last = null;
        }
        return res;
    }

    // 获取所有元素
    public List<Node<K, V>> getAllNode() {
        List<Node<K, V>> list = new ArrayList<>();
        Node<K, V> t = tail;
        while (t != null) {
            list.add(t);
            t = t.last;
        }
        return list;
    }
}

public class LeastRecentlyUsedCache {
    public static void main(String[] args) {
        MyCache<String, Integer> cache = new MyCache<>(3);
        cache.set("A", 3);
        cache.set("B", 4);
        cache.set("C", 5);
        cache.set("D", 5);
        cache.set("B", 2);
        cache.set("C", 5);
        cache.del("C");
        cache.set("A", 5);
        List<Node<String, Integer>> nodeList = cache.all();
        for (Node node : nodeList) {
            System.out.println(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
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196