Como é que a estrutura de dados HashMap está…

HashMap em Java baseia-se em princípios de hashing. Armazena pares de "chave-valor".

Estrutura interna:

Array de buckets (contentores). Cada bucket é uma lista ligada (ou uma árvore, a partir do Java 8, quando há muitas colisões).
Ao adicionar um elemento (put):
1. Calcula-se o código hash da chave (key.hashCode()).
2. O código hash é modificado para uma melhor distribuição (hash).
3. Usando o hash modificado e o tamanho do array de buckets, calcula-se o índice do bucket onde o elemento será colocado (hash & (tamanho_do_array - 1)).
4. O elemento (par "chave-valor" na forma de objeto Node) é colocado nesse bucket. Se o bucket já contiver elementos, o novo elemento é adicionado ao início da lista ligada ou árvore.
5. Ao adicionar, verifica-se se a chave já existe: usa-se o método equals() para comparar as chaves dentro do bucket. Se a chave for encontrada, o valor é atualizado.
Ao obter um elemento (get):
1. Também se calcula o índice do bucket pela chave.
2. Dentro do bucket, procura-se o elemento pela chave, usando os métodos hashCode() e equals().
3. Retorna-se o valor associado.

Organização:

Colisões: Se várias chaves têm o mesmo código hash e caem no mesmo bucket, os elementos são armazenados como uma lista ligada. Desde o Java 8, quando o número de elementos num bucket ultrapassa um limiar (normalmente 8), a lista ligada é transformada numa árvore para buscas mais rápidas (O(log n) em vez de O(n)).
Redimensionamento: Quando o número de elementos ultrapassa o "fator de carga" (load factor * capacity), o HashMap aumenta o tamanho do array interno de buckets (normalmente ao dobro) e re-hash todos os elementos. É uma operação dispendiosa (O(n)).
Parâmetros:
- capacity: tamanho inicial do array de buckets (por padrão 16).
- load factor: limiar de carga (por padrão 0.75). Define quando ocorre o redimensionamento.

Porque hashCode() e equals() são importantes:

O funcionamento correto do HashMap depende da implementação correta desses métodos.
Se equals() devolve true para dois objetos, então hashCode() deve devolver o mesmo valor.
Uma implementação incorreta pode fazer com que os elementos não sejam encontrados (get retornará null), mesmo que tenham sido adicionados.

Exemplo de estrutura Node:

// Apenas interno
static class Node<K,V> implements Map.Entry<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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

O HashMap oferece inserção, obtenção e remoção rápidas (em média O(1)) quando a distribuição de hashes é uniforme. No pior caso (colisões fortes), a operação pode ser O(n) ou O(log n) com árvores.

Não é seguro para threads. Para uso em ambientes concorrentes, deve-se usar ConcurrentHashMap ou Collections.synchronizedMap(new HashMap<...>(...)).

Como é que a estrutura de dados HashMap está organizada em Java?