Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) -
Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache
reached its capacity, it should invalidate the least recently used item before inserting a new item.
题目分析：
LRU 是将最不常用的换出。因此，对于每一片cache都需要有更新迭代的记录。
首先我想到了如下结构：
class Node {
int key;
int val;
private Node(int key, int val){
this.key = key;
this.val = val;
}
}
但是随后一想，这不就是hashmap么。而选用什么样的hashmap能够自动记录最不常用的key-value对呢？
经过调研，LinkedHashMap最能胜任。其构造函数：
map = new LinkedHashMap<Integer, Integer>(capacity,(float)0.5,true);
参数1：容量
参数2：负载因子（值越大，查找越慢，默认0.75）
参数3：排序是否保持跟插入顺序（更新顺序）一致
这样，记录最不常用的一个cache，就一定是该map的第一个键值对。
在set方法中，判断一下是否size达到了capacity即可。
public void set(int key, int value) {
if(map.size()<capacity || map.containsKey(key))
map.put(key,value);
else{
Iterator<Integer> it = map.keySet().iterator();
int itt = it.next();
map.remove(itt);
map.put(key,value);
}
}
AC代码：
import java.util.Iterator;
import java.util.LinkedHashMap;
/**
* Created by Ghost on 2014/10/8 0008.
*/
public class LRUCache {
public int capacity;
public LinkedHashMap<Integer,Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<Integer, Integer>(capacity,(float)0.5,true);
}
public int get(int key) {
if(map.containsKey(key))
return map.get(key);
return -1;
}
public void set(int key, int value) {
if(map.size()<capacity || map.containsKey(key))
map.put(key,value);
else{
Iterator<Integer> it = map.keySet().iterator();
int itt = it.next();
map.remove(itt);
map.put(key,value);
}
}
}