Java collections has LinkedHashMap which is a combination of a HashMap and a linked list which allows for predictable iteration order. There are two options for iteration - Based on insertion order, or based on Access order.
Now to create a Least Recently Used cache, the implementation need to use the access order for iteration and override the hook method removeEldestEntry() which should check the required size of the map to remove entries. I've posted the code in the example below.
Also present in the example is how you should *not* use the map in an multithreaded fashion. The class is not thread-safe and you end up with non deterministic behavior and the size invariant and probably other things go wrong.
