|
| 1 | +packagecom.caching; |
| 2 | + |
| 3 | + |
| 4 | +importjava.util.LinkedHashMap; |
| 5 | +importjava.util.Map; |
| 6 | +importjava.util.NoSuchElementException; |
| 7 | + |
| 8 | +/** |
| 9 | + * Your LRUCache can be instantiated and called as such: |
| 10 | + * LRUCache lruCache = new LRUCache(capacity); |
| 11 | + * lruCache.put(key,value); |
| 12 | + * int param_1 = lruCache.get(key); |
| 13 | + */ |
| 14 | + |
| 15 | +publicclassLRUCache<T> { |
| 16 | +/** |
| 17 | + * The class LinkedHashMap,is a subclass of HashMap that preserves the insertion order. |
| 18 | + * We can take advantage of this class to avoid having to implement the linked list. |
| 19 | + * A special constructor is provided to create a linked hash map whose order of |
| 20 | + * iteration is the order in which its entries were least-recently (access-order). |
| 21 | + */ |
| 22 | +privatefinalLinkedHashMap<Integer,T>cache; |
| 23 | +privatefinalintcapacity; |
| 24 | + |
| 25 | +/** |
| 26 | + * @param capacity - Instantiates LRUCache with the given capacity. |
| 27 | + */ |
| 28 | +publicLRUCache(intcapacity) { |
| 29 | +this.capacity =capacity; |
| 30 | + |
| 31 | +/* |
| 32 | + @param loadFactor Load Factor is a measure, which decides when exactly to resize the |
| 33 | + * HashMap. By default capacity = 16 and loadFactor = 0.75f. This means |
| 34 | + * that reisze when HashMap reaches 75% of its capacity. For we will |
| 35 | + * remove an element only if the cache reaches 100% capacity (1.0f). |
| 36 | + * |
| 37 | + * @param accessOrder - Set to true if ordering mode is specified (removeEldestEntry). |
| 38 | + */ |
| 39 | +this.cache =newLinkedHashMap<>(capacity,1.0f,true) { |
| 40 | +/** |
| 41 | + * @param eldest - The least recently accessed entry This is the entry that will |
| 42 | + * be removed if the method returns {@code true}. |
| 43 | + * returns {@code false} if it should be retained. |
| 44 | + */ |
| 45 | +@Override |
| 46 | +protectedbooleanremoveEldestEntry(Map.Entryeldest) { |
| 47 | +returnthis.size() >capacity; |
| 48 | + } |
| 49 | + }; |
| 50 | + } |
| 51 | + |
| 52 | + |
| 53 | +/** |
| 54 | + * To put a value in LRU cache with corresponding key |
| 55 | + * We add the value for key only if the key is not present. |
| 56 | + * We don't update existing values, only access-order is updated. |
| 57 | + * |
| 58 | + * @param key The key (int) |
| 59 | + * @param value The value to be cached |
| 60 | + */ |
| 61 | +publicvoidput(intkey,Tvalue) { |
| 62 | +if (capacity ==0) { |
| 63 | +System.out.println("Cache set to 0 capacity. No elements will be cached"); |
| 64 | + } |
| 65 | + |
| 66 | +TcurrentValue =cache.get(key); |
| 67 | +if (!cache.containsKey(key)) { |
| 68 | +cache.put(key,value); |
| 69 | +System.out.println("Adding new key:" +key +" to cache"); |
| 70 | + }else { |
| 71 | +System.out.println("Key:" +key +" already present in cache. Access order will be updated."); |
| 72 | + } |
| 73 | + } |
| 74 | + |
| 75 | + |
| 76 | +/** |
| 77 | + * To get the cached value for given key |
| 78 | + * |
| 79 | + * @param key The key (int) of the expected value |
| 80 | + * @return corresponding value for input key |
| 81 | + * @throws NoSuchElementException if key is absent |
| 82 | + */ |
| 83 | +publicTget(intkey) { |
| 84 | +// cache hit condition |
| 85 | +if (cache.containsKey(key)) { |
| 86 | +Tvalue =cache.get(key); |
| 87 | +System.out.println("Returning value from cache:" +value); |
| 88 | +returnvalue; |
| 89 | + } |
| 90 | +// cache miss condition |
| 91 | +thrownewNoSuchElementException("No element found for key:" +key); |
| 92 | + } |
| 93 | +} |
