For a
Map you can
convert its keys or values into a Collection, transfer them into a new
List, and then sort using
Collections.sort. The same process applies to a
Set. Obviously, this method is inefficient as it requires a complete copy of the content.
A more efficient way is to store the data already sorted. For this purpose, the
SortedSet and
SortedMap interfaces were introduced.
SortedSet implementations provide a
total order for the set. Elements are ordered in ascending order. This order is either
natural (elements implement the
Comparable interface), or determined by a
Comparator constructor parameter.
This interface adds methods to get subsets from a specified element (
tailSet), up to an element (
headSet), and between two elements (
subSet). The subset includes the lower bound but not the upper bound.
SortedSet is extended by the
NavigableSet interface which allows for iterating in order, and retrieving the closest element below (
floor), above (
ceiling),
higher than, or
lower than a given element.
The same rules apply to the keys of a
SortedMap/
NavigableMap.
The primary implementations are
TreeSet and
TreeMap. Under the hood these are self-balancing
red-black trees. The structure and method of balancing of these trees merit a separate post. Another interesting implementation from
java.util.concurrent is the
ConcurrentSkipListMap.