问题
如何设计实现LRU缓存？且Set() 和 Get() 的复杂度为O(1)。
解答
LRU，全称Least Recently Used，最近最少使用缓存。
在设计数据结构时，需要能够保持顺序，且是最近使用过的时间顺序被记录，这样每个item的相对位置代表了最近使用的顺序。满足这样考虑的结构可以是链表或者数组，不过链表更有利于Insert和Delete的操纵。
此外，需要记录链表的head和tail，从而方便进行移动到tail或者删除head的操作：
head.next作为最近最少使用的item，tail.prev为最近使用过的item，
- 在set时，如果超出capacity，则删除head.next，同时将要插入的item放入tail.prev,
- 在get时，如果存在，只需把item更新到tail.prev即可。
这样set与get均为O(1)时间的操作 （HashMap Get/Set + LinkedList Insert/Delete)，空间复杂度为O(n), n为capacity。
public class LRUCache {
private class Node {
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private int capacity;
private HashMap<Integer, Node> hm = new HashMap<Integer, Node>();
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
// @param capacity, an integer
public LRUCache(int capacity) {
this.capacity = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
// @return an integer
public int get(int key) {
if (!hm.containsKey(key)) {
return -1;
}
Node current = hm.get(key);
current.prev.next = current.next;
current.next.prev = current.prev;
moveToTail(current);
return hm.get(key).value;
}
// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
if (get(key) != -1) {
hm.get(key).value = value;
return;
}
if (hm.size() == capacity) {
hm.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value);
hm.put(key, insert);
moveToTail(insert);
}
private void moveToTail(Node current) {
current.next = tail;
tail.prev.next = current;
current.prev = tail.prev;
tail.prev = current;
}
}
更多
获取更多内容请关注微信公众号豆志昂扬:
- 直接添加公众号豆志昂扬；
- 微信扫描下图二维码；
