LRU Cache

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

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

效率低了一点

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.List;
 4 
 5 public class LRUCache {
 6     List<Element> cache = new ArrayList<Element>();
 7     int capacity;
 8     HashMap<Integer, Boolean> isInCache = new HashMap<Integer, Boolean>();            //key是否in cache
 9     
10     public LRUCache(int capacity) {
11         this.capacity = capacity;
12     }
13     
14     public int get(int key) {
15         boolean isKeyInCache = false;
16         int indexOfKey = -1;
17         int value = -1;
18         Element element = null;
19         //查找cache中是否有key
20         if(isInCache.get(key) != null)
21             for(int i = 0; i < cache.size(); i++){
22                 element = cache.get(i);
23                 if(element.key == key){                                //cache中有key
24                     value = element.value;
25                     isKeyInCache = true;
26                     indexOfKey = i;
27                     break;
28                 }//if
29             }//for
30         
31         if(isKeyInCache == true){                                //cache中有key
32             cache.remove(indexOfKey);
33             cache.add(0, element);                                //更新key在cache中的位置
34         }//if
35         
36         return value;
37     }
38     
39     public void set(int key, int value) {
40         int valueOfCache = -1;
41         if((valueOfCache = get(key)) == -1){                                        //在cache中不存在
42             if(cache.size() < capacity)                                //cache没有满,在0号位置添加
43                 cache.add(0, new Element(key, value));
44             else{    
45                 isInCache.remove(cache.get(capacity - 1).key);        //移除在hash表中的数据
46                 cache.remove(capacity - 1);                            //cache满了,移除最后一个,在0位置添加                
47                 cache.add(0, new Element(key, value));
48             }
49         }else{                                                    //如果在cache中存在
50             if(valueOfCache != value){                            //更新cache的值
51                 cache.remove(0);
52                 cache.add(0, new Element(key, value));
53             }
54         }
55         
56         isInCache.put(key, true);
57     }
58 }
59 /**
60  * cache中的元素
61  * @author Administrator
62  *
63  */
64 class Element{
65     int key;
66     int value;
67     
68     public Element(int key, int value){
69         this.key = key;
70         this.value = value;
71     }
72 }