LRU算法是一种缓存淘汰机制策略。
计算机的缓存容量有限,如果缓存满了就要删除一些内容给新的内容腾出位置,而删除哪些内容,就有不同的策略,LRU算法是其中一种策略。
LRU算法删除的是最近一段时间最少使用的内容。
代码中的capacity代表缓存的容量,使用Hash表 + 链表实现LRU算法。
基本思路
使用链表维护使用内容的先后顺序,比如最近使用了内容1,那么将内容1插入到链表的尾端。
使用Hash表可以根据key找到value。
package leetcode;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
public class LRUCache {
Map<Integer, Integer> map;
LinkedList<Integer> list;
Integer capacity;
public LRUCache(int capacity) {
map = new HashMap();
list = new LinkedList<>();
this.capacity = capacity;
}
public int get(int key) {
if(map.containsKey(key)) {
list.remove(new Integer(key));
list.addLast(key);
return map.get(key);
} else return -1;
}
public void put(int key, int value) {
if(map.containsKey(key)) {
list.remove(new Integer(key));
list.addLast(key);
map.put(key, value);
}else {
if(map.size() == capacity) {
// lru清除一个缓存
lruClear(key, value);
}else {
list.addLast(key);
map.put(key, value);
}
}
}
private void lruClear(int key, int value) {
Integer first = list.removeFirst();
list.addLast(key);
map.remove(first);
map.put(key ,value);
}
// 测试
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(2);
lruCache.put(1,1);
lruCache.put(2,2);
System.out.println(lruCache.get(1));
lruCache.put(3,3);
System.out.println(lruCache.get(2));
lruCache.put(4,4);
System.out.println(lruCache.get(1));
System.out.println(lruCache.get(3));
System.out.println(lruCache.get(4));
}
}
时间复杂度分析
get方法O(n)
put方法O(n)
之所以get和put方法的时间复杂度都是O(n),在于对链表节点的删除操作。
那么有没有方法可以将get和put方法的时间复杂度降到O(1)?
有的。
可以先自己实现一个双向链表,链表中的节点自己定义。Hash表中存储的value为链表中的节点对象,在对链表节点进行删除操作时可以将时间复杂度降到O(1)。
package leetcode;
import java.util.HashMap;
import java.util.Map;
public class LRUCacheII {
// 自定义链表节点
class Node {
Node pre;
Node next;
int key;
int value;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
Map<Integer, Node> map;
Node head;
Node tail;
int capacity;
LRUCacheII(int capacity) {
map = new HashMap<>();
head = new Node(Integer.MIN_VALUE, Integer.MIN_VALUE);
tail = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE);
head.next = tail;
tail.pre = head;
this.capacity = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
moveToLast(node);
return node.value;
} else return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
// 删除并移动最后
if(map.get(key).value != value) {
map.get(key).value = value;
}
Node node = map.get(key);
moveToLast(node);
map.put(key, node);
} else {
Node node = new Node(key, value);
if (map.size() == capacity) {
// lru清除一个
int keyFirst = deleteFirst();
addLast(node);
map.remove(keyFirst);
map.put(key, node);
} else {
addLast(node);
map.put(key ,node);
}
}
}
public void moveToLast(Node node) {
if (node.next == tail) {
return;
} else {
Node temp = node.next;
node.pre.next = temp;
temp.pre = node.pre;
tail.pre.next = node;
node.pre = tail.pre;
tail.pre = node;
node.next = tail;
}
}
public int deleteFirst() {
int res = head.next.key;
head.next = head.next.next;
head.next.pre = head;
return res;
}
public void addLast(Node node) {
tail.pre.next = node;
node.pre = tail.pre;
node.next = tail;
tail.pre = node;
}
public static void main(String[] args) {
LRUCacheII lruCache = new LRUCacheII(2);
lruCache.put(2,1);
lruCache.put(2,2);
System.out.println(lruCache.get(2));
lruCache.put(1,1);
lruCache.put(4,1);
System.out.println(lruCache.get(2));
}
}