You are right, SortedMap
sorts entries according its keys on inserts. And the most known implementation of SortedMap
is TreeMap
, which stores entries as balanced binary tree.
From their javadoc:
A {@link Map} that further provides a total ordering on its keys. The map is ordered according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). Several additional operations are provided to take advantage of the ordering.
Even though entries and keys are returned in sorted ascending order from SortedMap
, it also has methods firstKey()
and lastKey()
, which might be helpfull as well.
Particularly for LRU: the most common way in Java is to use LinkedHashMap
, which has method removeEldestEntry(Map.Entry)
. By default it does nothing, but you can easily extend class and implement that method. More information you may find here.