问题
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.
Have you met this question in a real interview? Yes
Example
分析
请参阅 Lru实现原理——LinkedHashMap源码解析
代码
public class LRUCache {
private int max = 0;
private LinkedHashMap<Integer, Integer> map = null;
/*
* @param capacity: An integer
*/
public LRUCache(int capacity) {
// do intialization if necessary
max = capacity;
map = new LinkedHashMap<>(max, 0.1f, true);
}
/*
* @param key: An integer
* @return: An integer
*/
public int get(int key) {
// write your code here
if (map.containsKey(key)) {
return map.get(key);
}
return -1;
}
/*
* @param key: An integer
* @param value: An integer
* @return: nothing
*/
public void set(int key, int value) {
// write your code here
if (map.containsKey(key)) {
map.put(key, value);
} else {
if (map.size() >= max) {
map.remove(map.entrySet().iterator().next().getKey());
}
map.put(key, value);
}
}
}
网友评论