Pode explicar a estrutura interna e o funcionamento da tabela hash em Java?

Uma tabela de hash em Java (por exemplo, HashMap) é uma estrutura de dados que armazena pares chave-valor e fornece acesso rápido através da chave.

Estrutura interna:

• A base é um array de baldes (cestos).
• Cada balde contém ou null, ou uma lista ligada (ou uma árvore, se houver muitos elementos) de elementos com o mesmo código hash módulo do tamanho do array.

Mecanismo de funcionamento:

1. Ao adicionar um elemento, calcula-se o código hash da chave e determina-se o índice do balde.
2. Se o balde estiver vazio, o elemento é colocado lá.
3. Se o balde estiver ocupado, procura-se na lista ligada (ou árvore) para verificar se a chave já existe:
   • Se a chave for encontrada, o valor é atualizado.
   • Caso contrário, o elemento é adicionado à lista.
4. Quando um limite de preenchimento é atingido, ocorre uma expansão do array (rehash) para manter o desempenho.

Essa abordagem garante uma complexidade média de operações de inserção, busca e remoção próxima de O(1).

Exemplo de uso:

Map<String, Integer> map = new HashMap<>();
map.put("key1", 100);
Integer value = map.get("key1"); // acesso rápido pela chave