Для
Map можно
привести ключи/значения к виду Collection, переложить в новый
List и отсортировать с помощью
Collections.sort. То же делается с
Set. Этот метод конечно же неэффективный, так как потребует полного копирования содержимого.
Эффективный способ – хранить данные уже отсортированными. Для таких реализаций созданы интерфейсы-наследники
SortedSet и
SortedMap.
Реализации
SortedSet дают
линейный порядок множества. Элементы упорядочены по возрастанию. Порядок либо
натуральный (элементы реализуют интерфейс
Comparable), либо его определяет переданный в конструктор
Comparator.
Этот интерфейс добавляет методы получения подмножества от указанного элемента (
tailSet), до элемента (
headSet), и между двумя (
subSet). Подмножество включает нижнюю границу, не включает верхнюю.
SortedSet расширяется интерфейсом
NavigableSet для итерации по порядку, получения ближайшего снизу (
floor), сверху (
ceiling), большего (
higher) и меньшего (
lower) заданному элемента.
Все те же правила применяются к элементам
SortedMap/
NavigableMap относительно их ключей.
Основными реализациями являются
TreeSet и
TreeMap. Внутри это
самобалансирующиеся красно-чёрные деревья. Их структура и способ балансировки – вопрос достойный отдельного поста. Другая любопытная реализация из
java.util.concurrent –
ConcurrentSkipListMap.