title: How would you implement an LRU cache in Java?
body: <p>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 <a href="http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html" rel="noreferrer">LinkedHashMap</a> and <a href="http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#synchronizedMap(java.util.Map)" rel="noreferrer">Collections#synchronizedMap</a>, but I'm curious if any of the new concurrent collections would be better candidates.</p>
  
  <p>UPDATE: I was just reading through <a href="http://steve-yegge.blogspot.com/2008/10/universal-design-pattern.html" rel="noreferrer">Yegge's latest</a> when I found this nugget:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>I was thinking almost exactly the same thing before I went with the <code>LinkedHashMap</code> + <code>Collections#synchronizedMap</code> implementation I mentioned above. Nice to know I hadn't just overlooked something.</p>
  
  <p>Based on the answers so far, it sounds like my best bet for a highly concurrent LRU would be to extend <a href="http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html" rel="noreferrer">ConcurrentHashMap</a> using some of the same logic that <code>LinkedHashMap</code> uses.</p>