How is removeEldestEntry implemented and what is the runtime/complexity of the method in LinkedHashMap?

Question

So I've looked around a little and couldn't really find any straight up answer for this. Personally I'm guessing Java probably manipulates timestamp on the items inserted into the LinkedHashMap, and possibly uses that in its ordering somehow.

I know that all the removeEldestEntry needs to do is simply returning true/false, but then when it gets to actually removing the eldest entry from the map, it would seem like the runtime would be O(n), what is it really?

Thanks.

Answer 1

Java does nothing. The JDK implementation of that method is:

return false;

It is there as an extension point for people who want to customize the behaviour of the map in their own sub-classes.

If you change it to return true, the runtime is still O(1). The list is maintained in insertion order. All it does is remove the head, which does not require any iteration. Just do the standard HashMap remove and then reassign two pointers.

// Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            //This is the standard HashMap remove, which then finishes by
            //calling Map.Entry#remove() on the removed entry.
            removeEntryForKey(eldest.key);
        }


private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

    /**
     * Removes this entry from the linked list.
     */
    private void remove() {
        before.after = after;
        after.before = before;
    }

Answer 2

from http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html

If you keep track of the oldest key inserted then the removal will be O(1), otherwise O(n).

You might also be able to take advantage of key insertion order. Keep in mind that even though a LinkedHashMap is ordered based on when a key was inserted it does not change the order if a key is reinserted (which may invalidate that key as the eldest).