In computers, cache memory provides fast access to processor by storing frequently used computer programs, data and applications; However size of cache memory is relatively small. Because of the size constraint, it is required to invalidate data from cache and store new data frequently when it is full.So, algorithms are required to decide which data should be removed from cache.
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.HashMap; import java.util.LinkedHashSet; public class LRUCache { private HashMap<Integer,Integer> valueDict; private LinkedHashSet<Integer> list; private int cap; public LRUCache(int capacity) { cap = capacity; valueDict = new HashMap<Integer,Integer>(); list = new LinkedHashSet<Integer>(); } public int get(int key) { if(valueDict.containsKey(key)) { list.remove(key); list.add(key); return valueDict.get(key); } return -1; } public void set(int key, int value) { if(valueDict.containsKey(key)) valueDict.put(key, value); else { if(valueDict.size() < cap) valueDict.put(key, value); else { int first = 0; for(int k : list) { first = k; break; } list.remove(first); valueDict.remove(first); valueDict.put(key, value); } } if(list.contains(key)) list.remove(key); list.add(key); } } |