首页 > 代码库 > LRU Cache

LRU Cache

2024-11-24 04:04:02   202人阅读

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 = http://www.mamicode.com/-1;18         Element element = null;19         //查找cache中是否有key20         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中有key24                     value =http://www.mamicode.com/ element.value;25                     isKeyInCache = true;26                     indexOfKey = i;27                     break;28                 }//if29             }//for30         31         if(isKeyInCache == true){                                //cache中有key32             cache.remove(indexOfKey);33             cache.add(0, element);                                //更新key在cache中的位置34         }//if35         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 Administrator62  *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 =http://www.mamicode.com/ value;71     }72 }

 

LRU Cache


联系
我们