Como o título sugere, essa é uma pergunta sobre um detalhe de implementação doHashMap#resize - é quando a matriz interna é dobrada em tamanho. É um pouco prolixo, mas eu realmente tentei provar que entendi melhor ...

Isso acontece em um momento em que as entradas neste depósito / compartimento específico são armazenadas em umLinked moda - tendo, assim, uma ordem exata e no contexto da perguntaIsso é importante.

Geralmente oresize pode ser chamado de outros lugares também, mas vamos ver apenas este caso.

Suponha que você coloque essas strings como chaves em umHashMap (à direita, há ohashcode depois de HashMap#hash - esse é o re-hash interno.) Sim, eles são cuidadosamente gerados, não aleatórios.

 DFHXR - 11111
 YSXFJ - 01111 
 TUDDY - 11111 
 AXVUH - 01111 
 RUTWZ - 11111
 DEDUC - 01111
 WFCVW - 11111
 ZETCU - 01111
 GCVUR - 11111 

Há um padrão simples a ser observado aqui - os últimos 4 bits são iguais para todos eles - o que significa que quando inserimos 8 dessas chaves (são 9 no total), elas terminam no mesmo balde; e no dia 9HashMap#put, aresize será chamado.

Portanto, se atualmente houver 8 entradas (com uma das teclas acima) noHashMap - significa que existem 16 buckets neste mapa e os últimos 4 bits da chave decidiram onde as entradas terminam.

Colocamos a chave nove. Neste pontoTREEIFY_THRESHOLD é atingido eresize é chamado. Os compartimentos são dobrados para32 e mais um bit das chaves decide para onde essa entrada irá (então, 5 bits agora).

Por fim, esse trecho de código é alcançado (quandoresize acontece):

 Node<K,V> loHead = null, loTail = null;
 Node<K,V> hiHead = null, hiTail = null;
 Node<K,V> next;
 do {
     next = e.next;
     if ((e.hash & oldCap) == 0) {
          if (loTail == null)
               loHead = e;
          else
               loTail.next = e;
          loTail = e;
     }
     else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
     }
 } while ((e = next) != null);



 if (loTail != null) {
     loTail.next = null;
     newTab[j] = loHead;
 }
 if (hiTail != null) {
     hiTail.next = null;
     newTab[j + oldCap] = hiHead;
 }

Na verdade, não é tão complicado ... o que faz, divide o compartimento atual em entradas quemoverá para outras posições e entradas quenão vai se mover para outras caixas - mas permanecerá nessa com certeza.

E é realmente muito inteligente como isso acontece - é através deste código:

 if ((e.hash & oldCap) == 0) 

O que isso faz é verificar se o próximo bit (o quinto no nosso caso) é realmente zero - se for, significa que essa entrada permanecerá onde está; caso contrário, ele se moverá com uma potência de dois desvios na nova lixeira.

E agora, finalmente, a pergunta: esse trecho de código no redimensionamento é feito com cuidado para quepreserva a ordem das entradas havia nessa lixeira.

Então, depois de colocar essas 9 teclas noHashMap o pedido será:

DFHXR -> TUDDY -> RUTWZ -> WFCVW -> GCVUR (one bin)

YSXFJ -> AXVUH -> DEDUC -> ZETCU (another bin)

Por que você deseja preservar a ordem de algumas entradas noHashMap. Ordem em umMap érealmente ruim como detalhadoaqui ouaqui.