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.