問題
如何設計實現(xiàn)LRU緩存？且Set() 和 Get() 的復雜度為O(1)。
解答
LRU，全稱Least Recently Used内地，最近最少使用緩存。
在設計數(shù)據(jù)結構時赋除，需要能夠保持順序阱缓，且是最近使用過的時間順序被記錄，這樣每個item的相對位置代表了最近使用的順序举农。滿足這樣考慮的結構可以是鏈表或者數(shù)組荆针，不過鏈表更有利于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;
}
}
更多
獲取更多內(nèi)容請關注微信公眾號豆志昂揚:
- 直接添加公眾號豆志昂揚惹想；
- 微信掃描下圖二維碼问词；
