Uma 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 chave-valor.

Neste artigo, eu vais apresentar-vos as HashMaps em Java. Vamos explorar as operações comuns de HashMap e depois mergulhar em como ela opera internamente. Você vai ganhar um entendimento da função de hash e do cálculo do índice. Finalmente, vamos olhar para as complexidades de tempo das operações e tocar na comportamento em um ambiente concorrente.

O que é uma HashMap em Java?

Uma HashMap implementa a interface Map, que faz parte do framework de coleções Java. Ela é baseada 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 de hash e é representada por um valor inteiro em Java. Os códigos de hash são usados para operações eficientes de busca e armazenamento em uma HashMap.

Operações Comuns

Como mencionado acima, os dados em uma HashMap são armazenados na forma de pares chave-valor. A chave é um identificador único, e cada chave está associada com 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.

  • Durante a inserção, se uma chave já estiver presente, o valor existente será substituído pelo novo valor que é 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 é dada a seguir, 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.

Retrieval:

  • Busca o valor associado a uma determinada chave.

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

A assinatura do método para esta operação é 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 a chave-valor com base na chave especificada. Retorna null se a chave não for encontrada.

  • containsKey: Verifica se a chave especificada 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 é usada 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;
    }
}

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

A classe Node tem os seguintes campos:

  • hash: Referência para o hashCode da chave.

  • key: Referência para a chave do par chave-valor.

  • value: Referência para o valor associado com a chave.

  • next: Age como uma referência para o 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 pode 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 hash então computa um número inteiro para a chave. As classes podem usar o método hashCode da classe Object ou sobrescrever este método e fornecer sua própria implementação. (Leia sobre o contrato de código hash aqui). O código hash é então feito um 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);
}

Above, 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 hash pode produzir o mesmo código hash para chaves diferentes. Isso leva a uma situação conhecida como colisão. Vamos ver 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;

Aqui, estamos calculando o índice onde n é a quantidade de caracteres no array da caixa.

Uma vez que o índice for calculado, a chave é armazenada nesse índice no array da caixa. No entanto, se múltiplas chaves acabarem tendo o mesmo índice, causa um conflito. Em tais situações, o HashMap trata-o de duas maneiras:

  • Cadeia/Ligação: Cada caixa no array é uma lista encadeada de nós. Se uma chave já existe em um determinado índice e outra chave é hashada para o mesmo índice, ela é acrescentada à lista.

  • Arvofication: Se o número de nós excede uma certa taxa, a lista encadeada é convertida em uma árvore (isto foi introduzido em Java 8).

static final int TREEIFY_THRESHOLD = 8;

Este é o limiar que determina a arvoficação.

Então, é essencial ter uma boa função de hash que distribui uniformemente as chaves entre as caixas e minimiza as chances de conflitos.

As operações de recuperação (get) e de exclusão (remove) funcionam de forma semelhante à operação de inserção (put). Aqui está como:

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

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

Complexidade de Tempo

As operações básicas de uma HashMap, como put, get e remove, geralmente oferecem desempenho de tempo constante O(1), assumindo que as chaves estejam distribuídas uniformemente. Em casos onde há má distribuição de chaves e muitas colisões ocorrem, essas operações podem degradar para uma complexidade de tempo linear de O(n).

Na transformação em árvore, onde cadeias longas de colisões são convertidas em árvores balanceadas, as operações de pesquisa podem melhorar para uma complexidade de tempo mais eficiente, logarítmica de O(log n).

Sincronização

A implementação de HashMap não é sincronizada. Se várias threads acessarem uma instância de HashMap concorrentemente e iterarem sobre o mapa, e se qualquer uma das threads executar uma modificação estrutural (como adicionar ou remover um mapeamento de chave-valor) no mapa, isso leva a uma ConcurrentModificationException.

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

Conclusão

Em resumo, entender os funcionamentos internos de um HashMap é crucial para que desenvolvedores tome decisões informadas. saber como uma chave é mapeada, como ocorrem colisões e como elas podem ser evitadas ajuda você a usar o HashMap de forma eficiente e eficaz.