Почему HashMap автоматически сортируется по ключу?

String givenString=in.nextLine();
char[] charArray = givenString.toCharArray();
double s=1;
double prom;
HashMap<Character, Double> probability2 = new HashMap<>();
for(int i=0;i<charArray.length;i++) {
    for(int j=1;j<charArray.length;j++) {
        if(charArray[i]==charArray[j]) s++;
    }
    if (!probability2.containsKey(charArray[i])) {
        prom=s/charArray.length;
        probability2.put(charArray[i],prom);
    }
    s=0;
}
for (Map.Entry entry : probability.entrySet()) {
    System.out.println("Key: " + entry.getKey() + " Value: "
    + entry.getValue());}
}

Это просто очень красивый edge case. Хэшкод Character - это непосредственно завернутое в него значение:

public int hashCode() {
    return Character.hashCode(value);
}
public static int hashCode(char value) {
    return (int)value;
}

Таким образом hashCode(a) = 97 или 0x61, b -> 0x62, c -> 0x63. HashMap же выбирает бакеты следующим образом:

 public V put(K key, V value) {
     return putVal(hash(key), key, value, false, true);
 }
 static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#610

XOR нужен для того, чтобы старшие биты тоже участвовали в выборе бакета, потому что иначе они игнорируются (n - количество бакетов):

tab[i = (n - 1) & hash]

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#629

Так как у нас хэш в данном примере лежит в 0x61..0x63, все старшие биты равняются нулю и не играют никакой роли при перемешивании хэша. Сама же операция выбора бакета состоит в простом отчекрыживании старших битов полученного значения. Таким образом при любом количестве бакетов > 2 данные хэшкоды гарантируют попадание в три последовательных бакета, потому что если мы посмотрим на последние четыре бита этих хэшкодов, то увидим следующую картину:

a 0001
b 0010
c 0011

если n >= 100 (четыре бакета и больше), то эти биты, отвечающие за распределение, всегда будут сохраняться. Количество бакетов по умолчанию - 16, что и приводит к описанной картине.

Повторюсь, что это edge case, и ожидать такого поведения в целом нельзя

HashMap хранит ключи в порядке, зависящем непосредственно от их хеш-кодов. Вполне вероятна ситуация, что ряд ключей будет отображаться в порядке возрастания или убывания, однако это лишь дело случая.

Чтобы выводить элементы в предсказуемом порядке используйте LinkedHashMap.

HashMap<Character, Double> probability2 = new LinkedHashMap<>();

Эта коллекция выводит элементы в том порядке, в каком они были добавлены:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.

Обратите внимание на последнюю строку: если элемент добавляется (с помощью put) несколько раз, то считается только первый.

HashMap не гарантирует порядка при выводе. Из документации:

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

То есть:

• Нет гарантии, что коллекция будет отсортирована по ключам.
• Нет гарантии, что коллекция не будет отсортирована по ключам.
• Нет гарантии, что порядок элементов будет сохраняться.

Например, для строки «dг» порядок будет обратным.

На практике, порядок элементов будет воспроизводим (потому что от HashMap не требуется случайного порядка), но и это нигде не гарантируется.