LinkedHashMap Structure for LRU Cache

Viewed 5376

I am a little confused about how to build a LRU cache by using LinkedHashMap (How would you implement an LRU cache in Java 6?), and I want to make sure I understand how it work internally behind the scene.

Lets say I define a class LRUMap that extends the LinkedHashMap and override the removeEldestEntry(final Map.Entry<A, B> eldest) just like the way it is.

Then I construct the data structure and insert 4 items into the map

    LRUMap<String,String> map = new LRUMap<String,String>(3); //capacity 3
    map.put("a", "a");
    map.put("b", "b");
    map.put("c", "c");
    map.put("d", "d");

and interally LinkedHashMap uses an Entry object called header as a starting node to link with all the items that you add to the map. So in this case it will be

   [header] ->  ["a"] -> ["b"] -> ["c"] -> ["d"] -> [header]

The header Entry object is both the start and the end of the doubly linked list since header.before = header.after = header when it initially constructs.

And lets say the map reaches the maximum Entries (3 items) that I want it to be, and from

    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
         removeEntryForKey(eldest.key);
    }
    .....

So does that mean it will remove ["a"] first ?
And when we call get(Object key) does it rearrange the list order where it puts that key (lets say "b") before the header node, so it becomes

     [header] ->  ["c"] -> ["d"] -> ["b"] -> [header]

Just want to clarify that.

1 Answers
Related