LeetCode-146：LRU缓存机制

 1 import java.util.Hashtable; // Hashtable相对HashMap来说，是线程安全的
 2 public class LRUCache {
 3 
 4   class DLinkedNode { //构建双向链表
 5     int key;
 6     int value;
 7     DLinkedNode prev;
 8     DLinkedNode next;
 9   }
10 
11   private void addNode(DLinkedNode node) {  // 始终将添加的元素放在伪节点head的后面
12     node.prev = head;
13     node.next = head.next;
14     head.next.prev = node;
15     head.next = node;
16   }
17 
18   private void removeNode(DLinkedNode node){  // 移除节点
19     DLinkedNode prev = node.prev;
20     DLinkedNode next = node.next;
21     prev.next = next;
22     next.prev = prev;
23   }
24 
25   private void moveToHead(DLinkedNode node){  // 将节点移动到缓存的前面
26     removeNode(node);
27     addNode(node);
28   }
29 
30   private DLinkedNode popTail() {  // 移除缓存最后面的节点
31     DLinkedNode res = tail.prev;
32     removeNode(res);
33     return res;
34   }
35 
36   private Hashtable<Integer, DLinkedNode> cache =
37           new Hashtable<Integer, DLinkedNode>();
38   private int size;
39   private int capacity;
40   private DLinkedNode head, tail;
41 
42   public LRUCache(int capacity) {  // 初始化缓存，构建以伪节点head和tail为开头和结尾的双向链表
43     this.size = 0;
44     this.capacity = capacity;
45     head = new DLinkedNode();
46     tail = new DLinkedNode();
47     head.next = tail;
48     tail.prev = head;
49   }
50 
51   public int get(int key) {
52     DLinkedNode node = cache.get(key);
53     if (node == null) return -1;
54     moveToHead(node);  // 将节点移动到缓存的前面
55     return node.value;
56   }
57 
58   public void put(int key, int value) {
59     DLinkedNode node = cache.get(key);
60     if(node == null) {  // 如果没有的话，添加到里面，注意缓存是否满了
61       DLinkedNode newNode = new DLinkedNode();
62       newNode.key = key;
63       newNode.value = value;
64       cache.put(key, newNode);
65       addNode(newNode);
66       ++size;
67       if(size > capacity) {
68         DLinkedNode tail = popTail();
69         cache.remove(tail.key);
70         --size;
71       }
72     } else {
73       node.value = value;
74       moveToHead(node);
75     }
76   }
77 }