题解 | #Java设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
思路：
用 LinkedHashMap 可以很容易实现 LRU 缓存，不过面试的时候估计这样不好，还是尽量自己实现数据结构吧🤣
主要想法是使用 JDK 提供的 HashMap，然后自己写一个 Node 节点类，用来保存 value ，并且通过这个 Node 里面的 prev、next 指针将各个值串联起来，这样就维护了顺序。
很重要的一个细节是，Node 里面还要加上 key （尽管 HashMap 本来就存了一份）。
原因是当缓存达到容量上限时，就要先移除尾部的节点，这个时候如果只移除链表的 tail 节点，忽略了 HasmMap 也要 remove ，后面再访问这个被移除的 key 就会造成空指针异常！！！
所以我们在 Node 节点里面加上 key ，删掉 tail 之前先 remove 掉 HasmMap 的这个 key，就很方便了。
代码：
import java.util.*;
public class Solution {
private int capacity;
private Map<Integer, Node> map;
private Node head;
private Node tail;
private int used;
class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value, Node prev, Node next) {
this.key = key;
this.value = value;
this.prev = prev;
this.next = next;
}
}
public Solution(int capacity) {
// write code here
this.capacity = capacity;
this.map = new HashMap<>();
this.used = 0;
}
public int get(int key) {
// write code here
if (!map.containsKey(key)) {
return -1;
}
makeRecently(key);
return map.get(key).value;
}
public void set(int key, int value) {
// 如果 key 已存在，直接修改值，再移到链表头部
if (map.containsKey(key)) {
map.get(key).value = value;
makeRecently(key);
return;
}
// 如果达到容量上限，就要移除尾部节点，注意 HashMap 要 remove！！！
if (used == capacity) {
map.remove(tail.key);
tail = tail.prev;
tail.next = null;
used--;
}
// 头节点为空，单独处理
if (head == null) {
head = new Node(key, value, null, null);
tail = head;
}
else {
Node t = new Node(key, value, null, head);
head.prev = t;
head = t;
}
map.put(key, head);
used++;
}
// 把 key 对应的节点移到链表头部
private void makeRecently(int key) {
Node t = map.get(key);
if (t != head) {
if (t == tail) {
tail = tail.prev;
tail.next = null;
}
else {
t.prev.next = t.next;
t.next.prev = t.prev;
}
t.prev = null;
t.next = head;
head.prev = t;
head = t;
}
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution solution = new Solution(capacity);
* int output = solution.get(key);
* solution.set(key,value);
*/
投递京东等公司6个岗位 >