No diga EHCache u OSCache, etc. Suponga, a los fines de esta pregunta, que quiero implementar el mío usando solo el SDK (aprender haciendo). Dado que el caché se usará en un entorno multiproceso, ¿qué estructuras de datos usaría? Ya he implementado uno usandoLinkedHashMap yColecciones #chronizedMap, pero tengo curiosidad por saber si alguna de las nuevas colecciones concurrentes serían mejores candidatos.

ACTUALIZACIÓN: solo estaba leyendoLo último de Yegge cuando encontré esta pepita:

Si necesita acceso de tiempo constante y desea mantener el orden de inserción, no puede hacerlo mejor que LinkedHashMap, una estructura de datos realmente maravillosa. La única forma en que podría ser más maravilloso es si hubiera una versión concurrente. Pero Ay.

Estaba pensando casi exactamente lo mismo antes de ir con elLinkedHashMap + Collections#synchronizedMap implementación que mencioné anteriormente. Es bueno saber que no había pasado por alto algo.

Según las respuestas hasta ahora, parece que mi mejor apuesta para un LRU altamente concurrente sería extenderConcurrentHashMap usando algo de la misma lógica queLinkedHashMap usos.