11
\$\begingroup\$

I have a simple implementation for a LRU cache using LinkedHashMap.

  • I want it to be as generic as possible.
  • This is not for production use, just practice, so I don't care if its thoroughly robust as far as it is correct. However, I will welcome any comments, especially the ones which might make this better with simple changes :)
  • Are there any other ways of doing this?
class LRUCache<E> {

    @SuppressWarnings("unchecked")
    LRUCache(int size)
    {
        fCacheSize = size;

        // If the cache is to be used by multiple threads,
        // the hashMap must be wrapped with code to synchronize 
        fCacheMap = Collections.synchronizedMap
        (
            //true = use access order instead of insertion order
            new LinkedHashMap<Object,E>(fCacheSize, .75F, true)
            {                                
                @Override
                public boolean removeEldestEntry(Map.Entry eldest)  
                {
                    //when to remove the eldest entry
                    return size() > 99 ;   //size exceeded the max allowed
                }
            }
        );
    }

    public void put(Object key, E elem)
    {
        fCacheMap.put(key, elem);
    }

    public E get(Object key)
    {
        return fCacheMap.get(key);
    }

    private Map<Object,E> fCacheMap;
    private int fCacheSize;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Instead of using a synchronized wrapper for the internal map you could synchronize all methods of LRU cache itself, as shown here: source-code.biz/snippets/java/6.htm \$\endgroup\$ – Landei Jun 27 '11 at 17:25
  • \$\begingroup\$ There is a similar question in StackOverflow: stackoverflow.com/questions/221525/… \$\endgroup\$ – palacsint Oct 31 '11 at 18:30
  • \$\begingroup\$ My only concern would be violation of dependency injection concept. \$\endgroup\$ – JavaDeveloper Oct 12 '13 at 17:19
10
\$\begingroup\$

First, use generics properly.

Second, why do you track the cache size if when you need it, you get a hardcoded 99? I will assume that was some sort of mistake.

Third, if you really want to annoy most truely professional java developers and course instructors (i.e, not these that write Java code as if they were programming in C#, C++ or Pascal), prefix your class and variable names. If you don't want to do so, do not make this.

Fourth, I would personally prefer to handle synchronization myself. This way, if the class is expanded to include some method that makes two or more operations in the map, I will not break it. I added the atomicGetAndSet method to show this. If I relied in the synchronization provided by the Collections.synchronizedMap instead of my own, the atomicGetAndSet method would not be atomic and it would break if LRUCache instances are used concurrently.

With this in mind, your code became this:

public class LRUCache<K, V> {

    private final Map<K, V> cacheMap;

    public LRUCache(final int cacheSize) {

        // true = use access order instead of insertion order.
        this.cacheMap = new LinkedHashMap<K, V>(cacheSize, 0.75f, true) {                                
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                // When to remove the eldest entry.
                return size() > cacheSize; // Size exceeded the max allowed.
            }
        };
    }

    public synchronized void put(K key, V elem) {
        cacheMap.put(key, elem);
    }

    public synchronized V get(K key) {
        return cacheMap.get(key);
    }

    public synchronized V atomicGetAndSet(K key, V elem) {
        V result = get(key);
        put(key, elem);
        return result;
    }
}
\$\endgroup\$
  • \$\begingroup\$ one improvement of above code from Victor is using lock instead of synchronized methods. Using lock will improve concurrency, e.g., get operations won't block each other. \$\endgroup\$ – Eric Mar 14 '13 at 15:55
  • \$\begingroup\$ @Eric While non-blocking method calls are preferable, it does require that the caller handles situations where the lock isn't obtained. Furthermore, calls to the methods Victor describes are very short-lived (get, or put something on a LinkedHashMap), so I doubt it will ever be a problem with synchronized. Do you see any other advantages of using locks? \$\endgroup\$ – zpon Oct 24 '13 at 5:48
  • \$\begingroup\$ But this is not a true LRUCache. LRU = Least recently used. I don't see that the get method updates something in the cache. It should, because the get method to the last inserted object should be the youngest object in the cache. \$\endgroup\$ – x-man Dec 6 '13 at 10:29
  • \$\begingroup\$ @x-man the get method calls cacheMap.get(key) which in its implementation (inside LinkedHashMap) takes care of the LRU functionality. \$\endgroup\$ – SwapnilS Aug 8 '14 at 15:54
3
\$\begingroup\$

Note from LinkedHashMap's javadoc:

Note that insertion order is not affected if a key is re-inserted into the map

So this will not be an LRU map unless you make sure that all keys are unique.

Further in the documentation, however:

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

\$\endgroup\$
1
\$\begingroup\$

From having implemented an LRU cache in production code using LinkedHashMap, I would say: why not go ahead and implement the full Map interface? At some point you may realize that you need a size() method and an entrySet() method, and maybe some other Map-like methods, so it might be good to go ahead and make LRUCache a facade to the contained fCacheMap by passing through all the other common Map methods. This opens up a whole world of utility classes that can be used to inspect or manipulate Maps, if desired.

Like so:

public class LRUCache<E> implements Map<Object, E> {
    // ...

    public int size()
    {
        return fCacheMap.size(key);
    }

    // etc...
}

Of course, you may decide that a subset of the Map interface is sufficient and perhaps use something like Collection instead. It really all depends on how you envision your LRUCache being used.

\$\endgroup\$

protected by Jamal Jan 23 '15 at 13:37

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.