Em entrevistas técnicas, o domínio dos detalhes de implementação de estruturas de dados frequentemente determina a impressão deixada no entrevistador. O HashMap, embora aparente simplicidade, contém nuances técnicas profundas que, mesmo sem abordar explicitamente árvores rubro-negras, oferecem amplo material para discussão.

Conceitualmente, o HashMap no Java é fundamentado em um array de buckets. Cada par chave-valor é encapsulado em um nó, que é armazenado em uma lista encadeada dentro do bucket correspondente. A posição no array é determinada por uma operação bit a bit entre o código hash da chave e o comprimento do array menos um. Quando ocorrem colisões de hash, os nós são encadeados. A leitura envolve calcular a posição a partir do hash da chave e, em seguida, percorrer a lista encadeada naquele bucket.

Duas características cruciais não representadas no diagrama conceitual básico são: primeiro, a operação de redimensionamento (resize), que ocorre quando o número de elementos excede o produto da capacidade do array pelo fator de carga, visando reduzir colisões; segundo, a conversão de uma lista encadeada em uma árvore rubro-negra quando o número de nós em um único bucket ultrapassa um limiar, uma otimização introduzida no Java 8.

Os quatro pilares para compreender o design do HashMap são: a inicialização, o cálculo de hash (método hash), a inserção de dados (método put) e o redimensionamento (resize).

Inicialização e Tamanho do Array

Ao instanciar um HashMap no JDK 8, o array de buckets subjacente não é alocado imediatamente. A alocação de memória real ocorre na primeira chamada ao método put. O construtor apenas valida os parâmetros e calcula o limite inicial (threshold) para um valor que é a menor potência de 2 maior ou igual à capacidade inicial especificada. A garantia de que o tamanho do array seja sempre uma potência de 2 é fundamental para a eficiência das operações de hashing.

// Exemplo simplificado do cálculo do tamanho inicial
private static int nextPowerOfTwo(int initialCapacity) {
    int n = initialCapacity - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Função de Hash e Endereçamento

A função de hash é crucial para distribuir uniformemente as entradas e minimizar colisões. No Java 8, o hash da chave é calculado, e seus 16 bits superiores são combinados com os 16 bits inferiores através de uma operação XOR. Isso visa incorporar informações de bits mais significativos (que seriam perdidos no cálculo do índice) ao valor final, melhorando a dispersão.

// Cálculo do hash no Java 8
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// O índice no array é então calculado como:
// index = (array.length - 1) & hash;

O motivo para o tamanho do array ser potência de 2 é duplo: permite que o cálculo do índice seja feito com uma operação AND bit a bit eficiente (length - 1 resulta em uma máscara como 00001111), e facilita a reorganização durante o redimensionamento.

Inserção de Elementos (put)

O processo de inserção (put) segue uma lógica hierárquica: após calcular o hash e o índice correspondente, ele verifica se o bucket está vazio. Se não estiver, percorre a estrutura existente (lista ou árvore) para localizar um nó com a mesma chave. Se encontrá-lo, atualiza o valor. Se não, insere um novo nó. Se a lista encadeada resultante atingir um comprimento crítico (geralmente 8), ela é convertida em uma árvore rubro-negra para otimizar buscas futuras. Após a inserção, se o número total de elementos exceder o limite, uma operação de redimensionamento é acionada.

// Lógica simplificada de inserção
public V insertarClaveValor(K clave, V valor) {
    int hashCalculado = calcularHash(clave);
    int indice = (capacidadArray() - 1) & hashCalculado;
    
    // Lógica para encontrar ou criar nó, lidando com listas e árvores
    // ...
    
    // Após inserção bem-sucedida
    tamanoActual++;
    if (tamanoActual > limiteDeCarga) {
        redimensionarArray();
    }
    return valorInsertado;
}

Redimensionamento (resize)

O redimensionamento é a operação mais complexa. Quando acionado, um novo array com o dobro do tamanho do anterior é criado. Os elementos do array antigo precisam ser reindexados. Graças à propriedade do tamanho ser potência de 2, a redistribuição é eficiente: para cada nó, basta verificar um bit específico do seu hash. Se esse bit for 0, o nó permanece no mesmo índice relativo. Se for 1, seu novo índice será o índice antigo somado ao tamanho do array original.

// Lógica de redistribuição durante o redimensionamento (simplificada)
for (int j = 0; j < capacidadVieja; j++) {
    Nodo<k> nodoActual = arrayViejo[j];
    if (nodoActual != null) {
        arrayViejo[j] = null; // Limpa a referência antiga
        if (nodoActual.siguiente == null) {
            // Nó único: reindexar diretamente
            arrayNuevo[(capacidadNueva - 1) & nodoActual.hash] = nodoActual;
        } else {
            // Lista encadeada: redistribuir usando a regra do bit
            Nodo<k> cabezaBaja = null, colaBaja = null;
            Nodo<k> cabezaAlta = null, colaAlta = null;
            Nodo<k> siguienteNodo;
            do {
                siguienteNodo = nodoActual.siguiente;
                if ((nodoActual.hash & capacidadVieja) == 0) {
                    // Permanece no bucket de mesmo índice relativo
                    // ... (encadeia em cabezaBaja/colaBaja)
                } else {
                    // Move para o novo bucket (índice + capacidadVieja)
                    // ... (encadeia en cabezaAlta/colaAlta)
                }
                nodoActual = siguienteNodo;
            } while (nodoActual != null);
            
            if (colaBaja != null) {
                colaBaja.siguiente = null;
                arrayNuevo[j] = cabezaBaja;
            }
            if (colaAlta != null) {
                colaAlta.siguiente = null;
                arrayNuevo[j + capacidadVieja] = cabezaAlta;
            }
        }
    }
}</k></k></k></k>

Conceitos Chave e Design Decisions

• Tamanho Potência de 2: Permite indexação eficiente via operação AND e simplifica o redimensionamento.
• Limite de Fator de Carga (0.75): Equilibrio entre uso de memória e probabilidade de colisão. O redimensionamento ocorre quando tamanho > capacidade * fatorDeCarga.
• Conversão para Árvore (Threshold = 8): Transforma uma lista encadeada em árvore rubro-negra quando o número de elementos em um bucket excede 8, elevando a complexidade das operações de O(n) para O(log n) naquele bucket, protegendo contra performance degenerada em caso de hash codes ruins. A reversão para lista ocorre quando o número de nós cai para 6 ou menos.
• Chave Nula: É tratada de forma especial e sempre mapeada para o bucket de índice 0.