A HashMap é uma das estruturas de dados mais comumente usadas em Java, e é conhecida por sua eficiência. Os dados em uma HashMap são armazenados na forma de pares de chave-valor.

Neste artigo, apresentarei a você o uso de HashMaps em Java. Vamos explorar as operações comuns de HashMap e depois mergulhar em como ela opera internamente. Você compreenderá a função de hash e como a cálculo do índice ocorre. Finalmente, analisaremos as complexidades de tempo das operações e mencionaremos o comportamento em um ambiente concorrente.

O que é uma HashMap em Java?

Uma HashMap implementa a interface Map, que é parte do framework de coleções Java. Ela se baseia no conceito de Hashing.

Hashing é uma técnica que transforma uma entrada de tamanho arbitrário em uma saída de tamanho fixo usando uma função de hash. A saída gerada é chamada de código hash e é representada por um valor inteiro em Java. Os códigos hash são usados para operações de pesquisa e armazenamento eficientes em uma HashMap.

Operações Comuns

Como discutimos acima, os dados em uma HashMap são armazenados na forma de pares de chave-valor. A chave é um identificador único, e cada chave está associada a um valor.

Abaixo estão algumas operações comuns suportadas por uma HashMap. Vamos entender o que esses métodos fazem com alguns exemplos de código simples:

Inserção

  • Este método insere um novo par chave-valor na HashMap.

  • A ordem de inserção dos pares chave-valor não é mantida.

  • Ao inserir, se a chave já existir, o valor existente será substituído pelo novo valor passado.

  • Você pode inserir apenas uma chave nula no HashMap, mas pode ter vários valores nulos.

A assinatura do método para esta operação está dada abaixo, seguida de um exemplo:

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

No código acima, temos um exemplo de HashMap onde adicionamos uma chave do tipo String e um valor do tipo Integer.

Recuperação:

  • Recupera o valor associado com uma chave dada.

  • Retorna null se a chave não existir no HashMap.

A assinatura do método para esta operação está dada abaixo, seguida de um exemplo:

public V get(Object key)

Integer value = map.get("apple"); // retorna 1

No código acima, estamos recuperando o valor associado à chave apple.

Outras operações comuns incluem:

  • remove: Remove o par chave-valor para a chave especificada. Retorna null se a chave não for encontrada.

  • containsKey: Verifica se uma chave específica está presente no HashMap.

  • containsValue: Verifica se o valor especificado está presente no HashMap.

Estrutura Interna de um HashMap

Internamente, um HashMap usa um array de buckets ou bins. Cada bucket é uma lista encadeada do tipo Node, que é usado para representar o par chave-valor do HashMap.

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Acima, você pode ver a estrutura da classe Node que é usada para armazenar os pares chave-valor do HashMap.

A classe Node possui os seguintes campos:

  • hash: Refere-se ao hashCode da chave.

  • key: Refere-se à chave do par chave-valor.

  • value: Refere-se ao valor associado à chave.

  • próximo: Age como uma referência ao próximo nó.

A HashMap é fundamentalmente baseada em uma implementação de tabela de hash, e seu desempenho depende de dois parâmetros chave: capacidade inicial e fator de carga. As javadocs originais da classe de tabela de hash definem esses dois parâmetros da seguinte forma:

  • A capacidade é o número de baldes na tabela de hash, e a capacidade inicial é simplesmente a capacidade no momento da criação da tabela de hash.

  • O fator de carga é uma medida de quão cheia a tabela de hash é permitida ficar antes que sua capacidade seja automaticamente aumentada.

Agora vamos tentar entender como as operações básicas, put e get, funcionam em uma HashMap.

Função Hash

Durante a inserção (put) de um par chave-valor, o HashMap primeiro calcula o código hash da chave. A função de hash então computa um número inteiro para a chave. As classes podem usar o método hashCode da classe Object ou sobrescrever esse método e fornecer sua própria implementação. (Leia sobre o contrato de código hash aqui). O código hash é então operado com XOR (OU Exclusivo) com seus 16 bits superiores (h >>> 16) para alcançar uma distribuição mais uniforme.

O XOR é uma operação bit a bit que compara dois bits, resultando em 1 se os bits são diferentes e 0 se forem iguais. Neste contexto, realizar uma operação de XOR bit a bit entre o código hash e seus 16 bits superiores (obtidos usando o operador de deslocamento para a direita sem sinal >>>) ajuda a misturar os bits, levando a um código hash mais uniformemente distribuído.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Aqui acima, você pode ver o método de hash estático da classe HashMap.

A ideia é ter um código hash único para cada chave, mas a função de hash pode produzir o mesmo código hash para chaves diferentes. Isso leva a uma situação conhecida como colisão. Veremos como lidar com colisões na próxima seção.

Cálculo do Índice

Uma vez que o código hash para uma chave é gerado, o HashMap calcula um índice dentro do array de baldes para determinar onde o par chave-valor será armazenado. Isso é feito usando uma operação de AND bit a bit, que é uma forma eficiente de calcular o módulo quando o comprimento do array é uma potência de dois.

int index = (n - 1) & hash;

Segue a tradução para o Português do Brasil:

Aqui, estamos calculando o índice onde n é o comprimento do array de baldes.

Uma vez que o índice é calculado, a chave é armazenada neste índice no array de baldes. No entanto, se várias chaves acabam tendo o mesmo índice, isso causa uma colisão. Nesse cenário, o HashMap trata isso de uma das duas formas:

  • Encadeamento/Linkagem: Cada balde no array é uma lista encadeada de nós. Se uma chave já existe em um índice particular e outra chave é hasheada para o mesmo índice, ela é anexada à lista.

  • Arborização: Se o número de nós excede um determinado limite, a lista encadeada é convertida em uma árvore (isto foi introduzido no Java 8).

static final int TREEIFY_THRESHOLD = 8;

Este é o limite que determina a arborização.

Portanto, é essencial ter uma boa função de hash que distribua uniformemente as chaves entre os baldes e minimize as chances de colisões.

As operações de recuperação (get) e remoção (remove) funcionam de forma semelhante à operação de inserção (put). Eis como:

  • Recuperação (get): Calcula o código hash usando a função de hash -> calcula o índice usando o código hash -> percorre a lista encadeada ou árvore para encontrar o nó com a chave correspondente.

  • Exclusão (remove): Computa o código de hash usando a função de hash -> calcula o índice usando o código de hash -> remove o nó da lista encadeada ou árvore.

Complexidade Temporal

As operações básicas de um HashMap, como put, get, e remove, normalmente oferecem desempenho de tempo constante de O(1), assumindo que as chaves estão distribuídas uniformemente. Em casos onde a distribuição das chaves é pobre e muitos colisões ocorrem, essas operações podem degringar para uma complexidade de tempo linear de O(n).

sob a árvore, onde longas cadeias de colisões são convertidas em árvores balanceadas, as operações de busca podem melhorar para a mais eficiente complexidade de tempo logarítmico de O(log n).

Sincronização

A implementação de HashMap não é sincronizada. Se várias threads acessam uma instância de HashMap concorrentemente e iteram sobre o mapa, e se alguma das threads realizar uma modificação estrutural (como adicionar ou remover um mapeamento de chave-valor) no mapa, isso resulta em uma ConcurrentModificationException.

Para evitar isso, você pode criar uma instância thread-safe usando o método Collections.synchronizedMap.

Conclusão

Em resumo, compreender o funcionamento interno de uma HashMap é crucial para que os desenvolvedores tomem decisões informadas. Saber como uma chave é mapeada, como ocorrem colisões e como elas podem ser evitadas ajuda você a usar a HashMap de forma eficiente e eficaz.