HashMap не отсортированы почти по определению; хорошая хеш-функция создаст, казалось бы, случайное распределение ключей.
Если вы хотите использовать Map в Java, который хранит свои элементы в отсортированном порядке, рассмотрите TreeMap, который поддерживается отсортированным двоичным деревом поиска.
Если вы хотите что-то, что можно отсортировать по ключу или по значению, возможно, вы ищете двунаправленную карту или «двуногую карту». В стандартных библиотеках Java нет, и самая близкая из известных мне реализаций - Google BiMap. Однако, как отметил Pangea, он не поддерживает элементы в отсортированном порядке. Вы можете легко создать свою собственную реализацию, просто используя два TreeMap s, один из которых - от ключей к значениям, а другой - от значений до ключей.
Надеюсь, это поможет!