Simple LRU or FIFO Cache

There is a very simple way to make a FIFO or LRU cache with the existing LinkedHashMap implementation of the default Java VM made by Joshua Bloch.

The LinkedHashMap already has a method you can override, which defines when to remove the “oldest” entry. With the default constructor this is already a FIFO cache, because it is internal sorted after the insertion order.

To Change to LRU cache you have to change the order of the LinkedHashMap to use the access order. You do this with the other constructor new LinkedHashMap(MAX, 0.75, true). ‘0.75’ is the default value taken from the LinkedHashMap code itself.

The serialVersionUID is only a proposal of FindBugs, because it is a anonymous inner class now with a changed behavior.

    private static final int MAX = 50;

    private final Map cache = Collections.synchronizedMap(
            new LinkedHashMap(MAX) {

                /** Serial UID. */
                private static final long serialVersionUID = 2546245625L;

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

BEWARE of MULTITHREADING
LinkedHashMap is not multithreaded itself. If you use it as a FIFO cache you only need to synchronize all threads for writing. BUT if you are using it as a LRU read (get(), iterating) access is also NOT THREAD SAFE! Even with Collections.synchronizedMap iterating is not handled and therefore not thread safe.

Otherwise a ConcurrentModificationException occurs or in the worst case the cache is in an inconsistent state.

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *