Por favor, não diga EHCache ou OSCache, etc. Suponhamos, para os fins desta pergunta, que eu queira implementar o meu usando apenas o SDK (aprendendo fazendo). Dado que o cache será usado em um ambiente multithread, quais estruturas de dados você usaria? Eu já implementei um usandoLinkedHashMap eColeções # synchronizedMap, mas estou curioso para saber se alguma das novas coleções simultâneas seria melhor candidata.

UPDATE: Eu estava lendoO mais recente de Yegge quando eu encontrei essa pepita:

Se você precisa de acesso em tempo constante e deseja manter o pedido de inserção, não pode fazer melhor do que um LinkedHashMap, uma estrutura de dados verdadeiramente maravilhosa. A única maneira de ser mais maravilhoso é se houver uma versão simultânea. Mas infelizmente.

Eu estava pensando quase exatamente a mesma coisa antes de ir com oLinkedHashMap + Collections#synchronizedMap implementação que mencionei acima. É bom saber que eu não tinha apenas esquecido algo.

Com base nas respostas até agora, parece que minha melhor aposta para uma LRU altamente simultânea seria estenderConcurrentHashMap usando algumas das mesmas lógicas queLinkedHashMap usos.