Ordem de iteração do Java HashMap - o comportamento parece consistente apesar da documentação declarar o contrário [duplicado]

O comportamento pode variar

tentando entender o comportamento real do HashMap

Você está tentando entender os detalhes de implementação interna de HashMap. Não faça isso.

Qualquer comportamento que você observe pode variar.

• O comportamento pode variar em tempo de execução . Os programadores de implementação podem ter escrito o comportamento para mudar dependendo da quantidade de elementos, ou seus tipos, ou seu conteúdo. A ordem de iteração pode até mudar cada vez que você faz um loop pelo mapa.
• O comportamento pode variar com qualquer nova versão . Os programadores são livres para alterar sua implementação a qualquer momento, desde que cumpram o contrato prometido no Javadoc.

O Javadoc é o contrato

Se o Javadoc disser que você não pode contar com uma ordem específica, então não dependa de uma ordem específica.

Se o Javadoc não promete segurança para threads, então não espere segurança para threads.

O Javadoc é o contrato formal, o acordo entre você e os programadores de implementação. Não faça suposições, não use sua intuição. O que você lê no Javadoc descreve o comportamento esperado. Qualquer coisa além do Javadoc pode existir, pode não existir ou pode variar, mas nunca deve ser esperado por você.

SequencedMap

Para uma ordem específica, use uma implementação de SequencedMap. Implementações agrupadas com Java: ConcurrentSkipListMap, LinkedHashMap, e TreeMap. Para saber mais sobre a API Sequenced Collections adicionada ao Java 21, leia JEP 431 e veja a excelente palestra de Stuart Marks .

Java oferece duas outras interfaces de mapa ordenado: NavigableMap(Java 6+) e SortedMap(Java 2+), ambas implementadas por duas das três classes nomeadas acima: ConcurrentSkipListMape TreeMap.

Considere usar TreeMapprimeiro, se thread-safety não for uma preocupação. Grandes quantidades de dados podem ter melhor desempenho com ConcurrentSkipListMap.

Codificação de sereia:

---
title: Java Map hierarchy
---
classDiagram
    Map <|-- SequencedMap
    SequencedMap <|-- SortedMap
    SortedMap <|-- NavigableMap
    NavigableMap <|-- ConcurrentNavigableMap
    NavigableMap <|.. TreeMap : implements
    ConcurrentNavigableMap <|.. ConcurrentSkipListMap : implements
    SequencedMap <|.. LinkedHashMap : implements
    class Map { <<interface>> }
    class SequencedMap { <<interface>> }
    class NavigableMap { <<interface>> }
    class SortedMap { <<interface>> }
    class ConcurrentNavigableMap { <<interface>> }
    class TreeMap { }
    class ConcurrentSkipListMap { }
    class LinkedHashMap { }

Terceiros

Você pode encontrar implementações de terceiros de mapas ordenados, como no Google Guava ou no Eclipse Collections .

Curiosidade

Se a curiosidade o levar a aprender sobre os detalhes da implementação do HashMap, aprenda os conceitos básicos como na Wikipedia e depois estude o código-fonte aberto no GitHub .

Isso é explicável. Primeiro, alguns fatos relevantes:

1. Você está usando um tipo de chave ( String) que tem um hashCodemétodo cujo algoritmo é especificado e que tem a garantia de fornecer o mesmo valor de hashcode para todas as execuções ¹ .

2. Você está inserindo os mesmos pares de chave/valor exatamente na mesma ordem todas as vezes.

Dado o acima, a implementação do HashMapque você está usando vai lhe dar uma ordem consistente para as chaves. Se você estivesse preparado para analisar o código-fonte, você seria capaz de ver o porquê.

No entanto, isso é um artefato da implementação atual... e da maneira como você a está usando.

• Se você alternar para uma JVM diferente com uma HashMapimplementação diferente, poderá obter uma ordenação diferente. (Especialmente se você inserir muito mais chaves distintas.)

• Se você alterasse a chave para um tipo que hashCodepudesse ser diferente para execuções diferentes, então a ordenação seria diferente. Por exemplo, se você usasse StringBufferem vez de String² .

O seu verdadeiro erro aqui é um mal-entendido do que o javadoc está dizendo. Quando ele diz "esta classe não dá garantias quanto à ordem do mapa", não está dizendo que a ordem SERÁ inconsistente. O que está dizendo é que PODERIA ser inconsistente.

Observe que "poderia ser inconsistente" implica logicamente "poderia ser consistente".

Então o fato de você ter encontrado um cenário onde você (parece ³ ) obtém uma ordem consistente não é surpreendente. E não contradiz o javadoc!

^{1 - De fato, o algoritmo é o mesmo para todas as versões do Java.
2 - Isso é apenas para fins de demonstração: é a coisa errada a fazer por outros motivos.
3 - Seu teste não é suficiente para mostrar que sua plataforma fornecerá ordenações consistentes se, por exemplo, as chaves forem dinâmicas, ou houver um grande número de pares de valores-chave, ou as inserções forem feitas em uma sequência diferente.}

Aqui estão algumas explicações sobre o que acontece nos bastidores.

1. A inserção de elementos em um HashMap não depende da ordem em que são adicionados. Em vez disso, depende do código hash da chave e da disponibilidade de slots no array interno do mapa.
2. Se o slot computado para uma chave já estiver ocupado (devido a uma colisão de hash), o HashMap resolve isso por encadeamento ou sondagem. Esse processo de resolução não preserva a ordem de inserção e pode envolver atravessar ou modificar vários slots.
3. Quando a capacidade do mapa é excedida, um novo mapa maior é criado, e todas as entradas existentes são rehashadas e redistribuídas. Esse processo de rehash ignora completamente a ordem de inserção original.

Primeiro de tudo, mapas hash são uma estrutura de dados padrão de ciência da computação. Há variações, mas vale a pena dar uma olhada na Wikipedia e coisas assim.

A estrutura de dados HashMap (em Java) usa buckets de tamanho fixo (arrays) nos quais os itens são armazenados por um índice sendo a chave hash do item módulo o tamanho do array. Quando dois itens diferentes colidem obtendo o mesmo índice, um novo hash deve ser feito, um próximo índice é obtido. Isso significa que com o crescimento dos mapas hash, a reestruturação dos buckets pode acontecer. Portanto:

Com o tempo o pedido não é garantido.

Você poderia continuar preenchendo um HashMap artificialmente até que a ordem dos itens comece a mudar. Depois de alguma adição, a ordem falhará.

Por exemplo (não testado):

List<String> order = new ArrayList<>();
Map<String, String> map = new HashMap<>();
for (;;) {
    key = ... read from dictionary 
    String oldKey = map.put(key, value):
    if (oldKey == null) {
        // Time to check the order:
        List<String> nextOrder = new ArrayList<>(map.keySet());
        for (int i = 0; i < nextOrder.size(); ++i) {
            if (i == order.size() || !order.get(i).equals(nextOrder.get(i)) {
                if (nextOrder.get(i).equals(key)) {
                    orders.add(i, key);
                } else {
                    System.out.println("Order changed");
                    return;
                }
            }
        }
    }
 }