Como é que o hashCode é calculado ao usar uma coleção Map?

Na coleção Map em Java, o método hashCode é calculado com base nos pares chave-valor. Para cada par, chama-se hashCode na chave e no valor, e então esses valores são combinados (normalmente somados) para obter o hashCode final de toda a Map.

Mais ou menos assim:

int hash = 0;
for (Map.Entry<K, V> entry : map.entrySet()) {
    hash += (entry.getKey() == null ? 0 : entry.getKey().hashCode()) ^
            (entry.getValue() == null ? 0 : entry.getValue().hashCode());
}
return hash;

Assim, o hashCode da Map depende do conteúdo e não da ordem dos elementos. Isso é importante para o funcionamento correto com estruturas de hash e para comparar Map pelo conteúdo.