LRU with LinkedHashMap – John Canessa

A day or so ago I saw the Twitter post 246 LRU Cache from LinkedHashMap by Dr. Heinz M. Kabutz. What called my attention was that a few weeks ago I was reading a paper on caching and spent some time (and generated some posts) on the subject LFU Cache I, LFU Cache II and LFU Cache III.

Based on the post by Heinz I wrote some code in Java 8 that generates the following output:

5
3 Three
9 Nine
1 One
6 Six
8 Eight

main <<< N: 5
main <<< i: 3 s ==>Three<==
main <<< i: 9 s ==>Nine<==
main <<< i: 1 s ==>One<==
main <<< i: 6 s ==>Six<==
main <<< i: 8 s ==>Eight<==
main <<< map: {3=Three, 9=Nine, 1=One, 6=Six, 8=Eight}
main <<< map.get(1) ==>One<==
main <<< map: {3=Three, 9=Nine, 6=Six, 8=Eight, 1=One}

removeEldestEntry <<< size(): 1 maxEntries: 5
removeEldestEntry <<< size(): 2 maxEntries: 5
removeEldestEntry <<< size(): 3 maxEntries: 5
removeEldestEntry <<< size(): 4 maxEntries: 5
removeEldestEntry <<< size(): 5 maxEntries: 5
removeEldestEntry <<< size(): 6 maxEntries: 5
removeEldestEntry <<< size(): 6 maxEntries: 5
removeEldestEntry <<< size(): 6 maxEntries: 5
removeEldestEntry <<< size(): 6 maxEntries: 5
removeEldestEntry <<< size(): 6 maxEntries: 5
main <<< cache: {5=some text, 6=some text, 7=some text, 8=some text, 9=some text}
main <<< cache: {5=some text, 6=some text, 8=some text, 9=some text, 7=some text}
removeEldestEntry <<< size(): 6 maxEntries: 5
main <<< cache: {6=some text, 8=some text, 9=some text, 7=some text, 10=Ten}

The code takes as input a count of key – value pair entries. The actual pairs follow. The code displays the entries as they are being received and then entered into a LinkedHashMap data structure which is instantiated with an accessCode set to true. You can read more about it on Class LinkedHashMap<K,V>. Of interest is the description of the accessCode parameter and the removeEldestEntry() method of the class.

The code for the LFUCache class that follows is almost identical to the one generated by Heinz on his post:

package canessa.john.lru;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

	/**
	 * 
	 */
	private final int	maxEntries;
	
	/**
	 * 
	 */
	private static final int	DEFAULT_INITIAL_CAPACITY	= 20;
	private static final float	DEFAULT_LOAD_FACTOR			= 0.75f;
	
	/**
	 * Constructor
	 */
	public LRUCache(int initialCapacity, float loadFactor, int maxEntries) {
		super(initialCapacity, loadFactor, true);
		this.maxEntries = maxEntries;
	}
	
	/**
	 * Constructor
	 */
	public LRUCache(int initialCapacity, int maxEntries) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR, maxEntries);
	}
	
	/**
	 * Constructor
	 */
	public LRUCache(int maxEntries) {
		this(DEFAULT_INITIAL_CAPACITY, maxEntries);
	}
	
	/**
	 * Returns true if this map should remove its eldest entry.
	 * This method may be overridden to impose a policy for removing stale
	 * mappings automatically when new mappings are added to the map.
	 */
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		System.out.println("removeEldestEntry <<< size(): " + size() + " maxEntries: " + this.maxEntries); return size() > maxEntries;
	}
}

Note that only one of the constructors is used in the actual test code that follows:

package canessa.john.lru;

import java.util.LinkedHashMap;
import java.util.Scanner;

/**
 *
 */
public class Solution {

	/**
	 * Test code. 
	 */
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		// **** initialCapacity - the initial capacity
		//  	loadFactor - the load factor
		//		accessOrder - the ordering mode - TRUE for access-order, false for insertion-order ****
			
		LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>(3, 0.75f, true);
		
		// **** number of pairs to read ****
		
		Integer N = sc.nextInt();
		System.out.println("main <<< N: " + N);
		sc.nextLine();
		
		// **** read and insert elements into the map ****

		for (int n = 0; n < N; n++) {
			Integer i 	= sc.nextInt();
			String s 	= sc.nextLine().trim();
			System.out.println("main <<< i: " + i + " s ==>" + s + "<==");
			map.put(i, s);
		}
		
		// **** close scanner ****
		
		sc.close();
		
		// **** display the map ****
		
		System.out.println("main <<< map: " + map.toString());
		
		// **** get element by key ****
		
		System.out.println("main <<< map.get(1) ==>" + map.get(1) + "<==");
		
		// **** display the map ****
		
		System.out.println("main <<< map: " + map.toString() + "\n");
		
		// **** instantiate the LRU cache ****
		
		LRUCache<Integer, String> cache = new LRUCache<Integer, String>(5);
		
		// **** populate the cache ****
		
		for (int i = 0; i < 10; i++) {
			cache.put(i, "some text");
		}
		
		// **** display the cache ****
		
		System.out.println("main <<< cache: " + cache.toString());
		
		// **** get the K,V value with K = 7 ****
		
		cache.get(7);
		
		// **** display the cache ****
		
		System.out.println("main <<< cache: " + cache.toString());
		
		// **** put a new K,V pair ****
		
		cache.put(10, "Ten");
		
		// **** display the cache ****
		
		System.out.println("main <<< cache: " + cache.toString());
	}

}

The first part of the test illustrates the use of the LinkedCacheMap class. A set of five entries are made. The map is displayed. The key with value one (1) is accessed. That changes the position of the key – value pair to be at the end of the map.

An LRUCache is instantiated. The cache can only hold five (5) entries. Ten (10) entries are inserted. After each entry the removeEldestEntry() method that has been overwritten is called. When the count of elements exceeds the count of five (5) specified when the cache was instantiated, the LRU element is removed. You can read all the details in the Oracle web site.

I have subscribed to Heinz’s web site and am following him on Twitter.

If you have comments or questions regarding this or any other post in this blog please leave a note at the end of this post. I will reply as soon as possible.

Enjoy;

John

Follow me on Twitter: @john_canessa

Leave a Reply Cancel reply