Java 6 is no longer the newest version and the answers are still valid for current versions

Link

edited May 15, 2016 at 7:46

Mifeet

13.7k
6
62
110

How would you implement an LRU cache in Java 6?

Update links to go to the docs.oracle site since the sun links error out

Source Link

edit approved Feb 5, 2014 at 9:17

Puneet

746
10
17

Please don't say EHCache or OSCache, etc. Assume for purposes of this question that I want to implement my own using just the SDK (learning by doing). Given that the cache will be used in a multithreaded environment, which datastructures would you use? I've already implemented one using LinkedHashMap LinkedHashMap and [Collections#synchronizedMap](http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#synchronizedMap(java.util.Map)Collections#synchronizedMap, but I'm curious if any of the new concurrent collections would be better candidates.

UPDATE: I was just reading through Yegge's latest when I found this nugget:

If you need constant-time access and want to maintain the insertion order, you can't do better than a LinkedHashMap, a truly wonderful data structure. The only way it could possibly be more wonderful is if there were a concurrent version. But alas.

I was thinking almost exactly the same thing before I went with the LinkedHashMap + Collections#synchronizedMap implementation I mentioned above. Nice to know I hadn't just overlooked something.

Based on the answers so far, it sounds like my best bet for a highly concurrent LRU would be to extend ConcurrentHashMap ConcurrentHashMap using some of the same logic that LinkedHashMap uses.

Please don't say EHCache or OSCache, etc. Assume for purposes of this question that I want to implement my own using just the SDK (learning by doing). Given that the cache will be used in a multithreaded environment, which datastructures would you use? I've already implemented one using LinkedHashMap and [Collections#synchronizedMap](http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#synchronizedMap(java.util.Map), but I'm curious if any of the new concurrent collections would be better candidates.

UPDATE: I was just reading through Yegge's latest when I found this nugget:

If you need constant-time access and want to maintain the insertion order, you can't do better than a LinkedHashMap, a truly wonderful data structure. The only way it could possibly be more wonderful is if there were a concurrent version. But alas.

I was thinking almost exactly the same thing before I went with the LinkedHashMap + Collections#synchronizedMap implementation I mentioned above. Nice to know I hadn't just overlooked something.

Based on the answers so far, it sounds like my best bet for a highly concurrent LRU would be to extend ConcurrentHashMap using some of the same logic that LinkedHashMap uses.

Please don't say EHCache or OSCache, etc. Assume for purposes of this question that I want to implement my own using just the SDK (learning by doing). Given that the cache will be used in a multithreaded environment, which datastructures would you use? I've already implemented one using LinkedHashMap and Collections#synchronizedMap, but I'm curious if any of the new concurrent collections would be better candidates.

UPDATE: I was just reading through Yegge's latest when I found this nugget:

If you need constant-time access and want to maintain the insertion order, you can't do better than a LinkedHashMap, a truly wonderful data structure. The only way it could possibly be more wonderful is if there were a concurrent version. But alas.

I was thinking almost exactly the same thing before I went with the LinkedHashMap + Collections#synchronizedMap implementation I mentioned above. Nice to know I hadn't just overlooked something.

Based on the answers so far, it sounds like my best bet for a highly concurrent LRU would be to extend ConcurrentHashMap using some of the same logic that LinkedHashMap uses.