Java: Least Recently Used (LRU) Cache

Least Recently Used or in short LRU is an performance optimizing algorithm. LRU algorithm is widely used in software programming as well as in hardware instructions (e.g. CPU).

In many case, in programming, we may want to cache some data from physical disk, for example database and files, but we cannot load all the data into memory due to the memory limitation on the server or PC. In those cases, you may want to consider to use LRU algorithm to solve the memory limitation problem.

The LRU algorithm is very simple, it keeps a list of read items in memory and discards the least recently used items first when the define LRU cache size is reach.

Java collections does not have a class for LRU but implementing a LRU by yourself is not difficult. You just need to declare a class the inherits LinkedHashMap and override its removeEldestEntry() function.

Here is the code that makes it works:

public class LeastRecentlyUsedCache<K,V> extends LinkedHashMap<K,V> {
    private int lrucSize;

    public LeastRecentlyUsedCache(int size) {
        lrucSize = size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > lrucSize;
    }
}

The following example show how you can use the LRU cache in your program or to solve your problem:

  // Create LRU cache of 500 customer
  LeastRecentlyUsedCache<Integer,Customer> lru =
    new LeastRecentlyUsedCache<Integer,Customer>(500);

  while (/* looping a big list of items */)

    // Need refer customer, so try to get
    // the customer from LRU cache
    customer = lru.get(id);

    // Customer not in LRU cache
    if (customer == null) {

      // Load customer from database
      customer = ...

      // Put it into LRU cache
      lru.put(customer.id, customer);
    }

    // Use the customer object
    ...
  }

Pretty simple right? From the above example, let say we are looping a big list of items (say one millions for sales records) and having 1000 of customer. Some customers have many sales records and some customers have no sales record. Instead of reading each customer record for each sales record from database (file access is slower than memory), by using LRU cache, it will reuse the loaded customer data in LRU cache whenever possible and therefore increase the overall performance.

This because a most recently used data will be likely to be used again and therefore will be stayed in cache;  and a least recently used item will not be used again and therefore will be unloaded when the cache reaches the maximum cache size.

Note: The is <K,V> (key and value) for generic declaration purpose.