LeetCode 之 LRU Cache Java实现

浏览数：20 / 时间：2015年06月08日

　　LeetCode刷了41道题了，流程是按照戴兄的小书，很多不会的是参考Kim姐的代码，自己用Java抠腚的。

　　前几天做到了LRU Cache：

　　C++的实现方法大同小异，大都用的是一个list加一个hash，hash中存储list节点地址，每次get从hash中寻key，有则将list相应节点放到链表头，没有则返回-1；每次set先判断hash中是否存在，存在则将相应节点移到表头，重置value值，如果不存在，判定长度是否达到预设的capacity，如果达到，删除表尾节点，新节点插入表头。

　　但是用Java如此实现的话就有点绕了，倒是也看到有同学用HashMap和自己定义的双向链表实现的。

　　之前用LikedHashMap不是很多，这次就用它实现LRU Cache。LikedHashMap中有一个方法叫removeEldestEntry，作用是判断map中的entry是否超了容量，超了的话会自动删掉最早插入的entry，其实功能已经很接近LRU了，但是不论访问还是set已有的元素，都不会对删除顺序有影响。实现如下：

 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 }