一、LRU缓存机制(LeetCode-146)
1.1 题目描述
1.2 解题思路
思路1：
使用Map存放key，value，使用List存放key和count，count为最新的index值，每次put、get操作都会使index自增。
进行put操作时，如果发现超过容量值capacity，则对list中的count排序，map和list都删除掉index最小的元素。（提示超时）
思路2：
使用LinkedList，每次put操作或get操作，当list中没有该key的元素的时候，且不超过容量时，直接插入元素，若有则删除key对应的原有元素，插入key对应的新元素值。
如果超过容量，则删除第一个元素，再添加进去。（通过）
1.3 解题代码
思路1：
public class LRUCache { private Map<Integer, Integer> map = null;
private List<HitCount> list = null;
private Map<Integer, HitCount> locationMap = null;
private int index = 0;
private int capacity = 0; public LRUCache(int capacity) {
map = new HashMap<>(capacity);
list = new LinkedList<>();
locationMap = new HashMap<>(capacity);
this.capacity = capacity;
} public int get(int key) {
//先找到key-value
Integer value = map.get(key);
if (value == null) {
return -1;
} HitCount h = locationMap.get(key);
h.setCount(++index);
return value;
} public void put(int key, int value) {
//若key已存在
Integer existValue = map.get(key);
//容量不充足
if (existValue == null && map.size() == capacity) {
//找到命中次数最少的一个、若命中次数相同，则去除插入最早的
HitCount leastKey = getLeastKey();
map.remove(leastKey.getKey());
list.remove(leastKey);
locationMap.remove(leastKey.getKey());
}
HitCount h = null;
if (existValue != null) {
h = locationMap.get(key);
h.setCount(++index);
} else {
h = new HitCount(key, ++index);
list.add(h);
}
map.put(key, value);
locationMap.put(key, h);
index++;
} private HitCount getLeastKey() {
list = list.stream().sorted((u1, u2) -> (u1.getCount() - u2.getCount())).collect(Collectors.toList());
return list.get(0);
} class HitCount {
private int key;
private int count; HitCount(int key, int count) {
this.key = key;
this.count = count;
} public int getKey() {
return key;
} public void setKey(int key) {
this.key = key;
} public int getCount() {
return count;
} public void setCount(int count) {
this.count = count;
} }}思路2：
public class LRUCache { private List<LRUMap> list = null;
private int capacity = 0; public LRUCache(int capacity) {
list = new LinkedList<>();
this.capacity = capacity;
} public int get(int key) {
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
LRUMap node = (LRUMap) iterator.next();
if (node.getKey() == key) {
int value = node.getValue();
list.remove(node);
list.add(new LRUMap(key, value));
return value;
}
}
return -1;
} public void put(int key, int value) {
LRUMap node = new LRUMap(key, value); //查看该节点是否存在
if (list.contains(node)) {
list.remove(node);
}
//如果超过容量
if (list.size() == capacity) {
list.remove(0);
}
list.add(node); } class LRUMap { private int key;
private int value; public LRUMap(int key, int value) {
this.key = key;
this.value = value;
} public int getKey() {
return key;
} public void setKey(int key) {
this.key = key;
} public int getValue() {
return value;
} public void setValue(int value) {
this.value = value;
} @Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (obj == null || obj.getClass() != this.getClass()) {
return false;
} LRUMap map = (LRUMap) obj;
return key == map.key;
}
}}
