LeetCode 之 LRU Cache Java实现

 1 import java.util.LinkedHashMap;
 2 import java.util.Map.Entry;
 3 
 4 /**
 5  * Problem: LRU Cache
 6  * Description: Design and implement a data structure for Least Recently Used
 7  * (LRU) cache. It should support the following operations: get and set.
 8  * get(key) - Get the value (will always be positive) of the key if the key
 9  * exists in the cache, otherwise return -1.
10  * set(key, value) - Set or insert the value if the key is not already present.
11  * When the cache reached its capacity, it should invalidate the least recently
12  * used item before inserting a new item.
13  * Date: Aug 4 , 2014
14  * 
15  * @author Chyace
16  * 
17  */
18 public class LRUCache {
19 // 用来装item的LinkedHashMap子类对象
20     CacheMap cache;
21 
22     public LRUCache(int capacity) {
23         cache = new CacheMap(capacity);
24     }
25 /**
26  * 每次get容器中的值，都将相应元素删除重新插入，这时它就会位于最新的位置
27  * @param key
28  * @return
29  */
30     public int get(int key) {
31         if (cache.containsKey(key)) {
32             int value = cache.get(key);
33             cache.remove(key);
34             set(key, value);
35             return value;
36         }
37         return -1;
38     }
39 
40     public void set(int key, int value) {
41         if (cache.containsKey(key)) cache.remove(key);
42         cache.put(key, value);
43     }
44 }
45 
46 /**
47  * LinkedHashMap只能实现最旧移除而不会更新
48  * 
49  * @author Chyace
50  * 
51  */
52 class CacheMap extends LinkedHashMap<Integer, Integer> {
53 
54     private static final long serialVersionUID = 3240765461462956414L;
55 
56     private int MAX;
57 
58     CacheMap(int max) {
59         this.MAX = max;
60     }
61 
62     protected boolean removeEldestEntry(Entry<Integer, Integer> eldest) {
63         return size() > MAX;
64     }
65 
66 }