В задаче можно несколькими путями решить проблему несортированной мапы. Я выбрала такой 
for (Character c:
             alphabet) {
            System.out.println(c + " " + map.get(c));
        }
Но почему это работает? Почему alphabet выводится по алфавитному порядку, это ведь List, который может выводить элементы не по порядку добавления? 
List<Character> alphabet = Arrays.asList(
                'а', 'б', 'в', 'г', 'д', 'е', 'ё', 'ж',
                'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о',
                'п', 'р', 'с', 'т', 'у', 'ф', 'х', 'ц',
                'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я');