LinkedHashMap removeEldestEntry: How many elements

Question

LinkedHashMap looks brilliant to implement LRU Cache. It has some overheads in terms of linked list management and not thread safe but then it simplifies the implementation and I can take care of these in my code.

The question I have, which I don't find answer so far about is how many elements LinkedHashMap removes from the list if removeEldestEntry is implemented and put finds the list full.

Does it remove just one element? or some percentage of the total size. My concern is if it removes just one element to put new element then its a real performance issue. As I see the rehash operations are very costly.

Please someone suggest how it works and If I can manage these to be removed elements count using InitialCapacity, LoadFactor or any other way.

Answer 1

LinkedHashMap looks brilliant to implement LRU Cache. It has some overheads in terms of linked list management

This is true of all LRU caches.

and not thread safe

You can use Collections.synchronizedMap()

The question I have, which I don't find answer so far about is how many elements LinkedHashMap removes from the list if removeEldestEntry is implemented and put finds the list full.

It removes the eldest entry. I.e. one and only one.

From the source for LinkedHashMap

    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);

My concern is if it removes just one element to put new element then its a real performance issue.

It isn't.

As I see the rehash operations are very costly.

Rehashing only occurs when the capacity grows, not when an entry is removed.

Answer 2

LinkedHashMap is good to implement the most trivial cache, but for more advanced requirements it's probably not ideal.

Returning true from removeEldestEntry will cause the single, eldest entry to be removed, there's no way to tweak this to multiple elements.

Maybe something like the Guava CacheBuilder might be what you're looking for.