Create least recently used (LRU) cache in java using LinkedHashMap

Leave a Comment / By /
  • LRU is one of the most popular caching algorithm.
  • The items, which are least recently used are removed from the cache, using eviction policy.

Types of iteration order in LinkedHashMap:

  1. Insertion order: This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map
  2. Access order:  Access order is the order of iteration in which its entries were last accessed, from least-recently accessed to most-recently .
    • LRU cache implementation will use access order of LinkedHashMap.
    • LinkedHashMap has removeEldestEntry method, which decides the eviction policy.

Program – Least recently used (LRU) cache in java using LinkedHashMap

package org.learn.collection.map.lhashmap;
 
import java.util.LinkedHashMap;
import java.util.Map;
 
class LRUCache<K, V> extends LinkedHashMap<K, V> {
 
    private static final long serialVersionUID = 1L;
    private int lruSize;
 
    public LRUCache(int lruSize) {
        super(16, 0.75f, true);
        this.lruSize = lruSize;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > lruSize;
    }  
}
 
public class LRUCacheClient {
    public static void main(String[] args) {
        int cacheSize = 5;
        Map<Integer, String> mapVehicleNoAndOwner = new LRUCache<>(cacheSize);
 
        mapVehicleNoAndOwner.put(1000, "Federer");
        mapVehicleNoAndOwner.put(2000, "Bradman");
        mapVehicleNoAndOwner.put(3000, "Jordan");
        mapVehicleNoAndOwner.put(4000, "Woods");
        mapVehicleNoAndOwner.put(5000, "Ali");
 
        System.out.println("1. Iterating initial cache of size = "+cacheSize);
        demoIterateCache(mapVehicleNoAndOwner);
         
        int key = 1000;
        System.out.printf("2. Accessting value at key: %d is %s\n",key,mapVehicleNoAndOwner.get(key));
         
        key = 3000;
        System.out.printf("3. Accessting value at key: %d is %s\n",key,mapVehicleNoAndOwner.get(key));
         
        System.out.println("4. Iterating cache after accessing its keys: ");
        demoIterateCache(mapVehicleNoAndOwner);
         
        key = 6000;
        String value = "Don";
        System.out.printf("5. Adding new entry to cache, key=%d, value=%s\n",key,value);
        mapVehicleNoAndOwner.put(6000, "Don");
        key = 7000;
        value = "Campbell";
        System.out.printf("6. Adding new entry to cache, key=%d, value=%s\n",key,value);
        mapVehicleNoAndOwner.put(7000, "Campbell");
 
        System.out.println("7. Iterating cache after adding entries beyond its size: ");
        demoIterateCache(mapVehicleNoAndOwner);
    }
 
    private static void demoIterateCache(Map<Integer, String> mapVehicleNoAndOwner) {
 
        mapVehicleNoAndOwner.forEach((key, value) -> {
            System.out.println("Key:" + key + ", Value:" + value);
        });
    }
}

Output – Least recently used (LRU) cache in java using LinkedhashMap

1. Iterating initial cache of size = 5
Key:1000, Value:Federer
Key:2000, Value:Bradman
Key:3000, Value:Jordan
Key:4000, Value:Woods
Key:5000, Value:Ali
2. Accessting value at key: 1000 is Federer
3. Accessting value at key: 3000 is Jordan
4. Iterating cache after accessing its keys:
Key:2000, Value:Bradman
Key:4000, Value:Woods
Key:5000, Value:Ali
Key:1000, Value:Federer
Key:3000, Value:Jordan
5. Adding new entry to cache, key=6000, value=Don
6. Adding new entry to cache, key=7000, value=Campbell
7. Iterating cache after adding entries beyond its size:
Key:5000, Value:Ali
Key:1000, Value:Federer
Key:3000, Value:Jordan
Key:6000, Value:Don
Key:7000, Value:Campbell

You may also like:

Access order in LinkedHashMap using java (with example)

Insertion order in LinkedHashMap using java (with example)

Insert elements to HashMap collection in java (example)

Iterate /loop HashMap collection having string objects (Java8/ example)

Remove elements/string objects from HashMap collection by key (Java/example)

Iterate/ loop TreeMap collection of String Objects before & after java8 (example)

Iterate or loop EnumMap using entrySet & forEach Java 8 (example)