По чему будут отсортированы элементы, если получить entrySet

Элементы entrySet в HashMap не гарантируют никакого порядка, так как хэш-карта не поддерживает порядок элементов. В LinkedHashMap элементы будут отсортированы в порядке добавления. В TreeMap - согласно естественному порядку ключей или компаратору, если он задан.

Пример с TreeMap:

Map<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey()); // apple, banana, cherry
}