Если вы думаете о производительности, тогда большие наборы результатов лучше сортировать в конце базы данных, особенно когда индексируемые столбцы сортируются.
Для небольших наборов данных разница в производительности может быть незначительной, но я думаю, что в большинстве случаев предложение SQL By Order By будет более простым подходом.
Кстати, вам все равно придется использовать LinkedHashMap вместо простого HashMap, если вы должны сохранить уже отсортированные данные на карте перед их использованием. Потому что LinkedHashMap будет хранить данные в порядке вставки, а HashMap - нет.
Если вы хотите, чтобы данные автоматически сортировались при их помещении в карту, вам потребуется TreeMap или другая реализация отсортированной карты.