O que é uma tabela hash?

Uma tabela hash é uma estrutura de dados que implementa um array associativo (dicionário). Ela armazena pares de "chave-valor", onde as chaves são únicas.

Princípios básicos:

• Função hash: Converte a chave em um número (código hash ou índice). Este índice indica o local de armazenamento do valor na matriz (cesto).
• Matriz (cestos): Armazenamento real dos pares "chave-valor".
• Colisões: Situação em que chaves diferentes geram o mesmo código hash.

Solução para colisões:

• Método de encadeamento (Separate chaining): Cada cesto armazena uma lista (ou outra estrutura de dados) de elementos com o mesmo código hash.
• Endereçamento aberto (Open addressing): Em caso de colisão, a busca por um cesto livre é feita usando diferentes estratégias (sondagem linear, sondagem quadrática, duplo hashing).

Características:

• Acesso rápido: No caso ideal O(1) para operações de inserção, busca e remoção.
• Dependência da função hash: A qualidade da função hash e a estratégia de resolução de colisões influenciam bastante o desempenho.
• Uso de memória: Requer memória adicional para a matriz de cestos.

Uso em QA:

• Armazenamento de dados de teste (chave - nome do parâmetro, valor - valor esperado ou real).
• Verificação da unicidade dos elementos (por exemplo, IDs de usuários).
• Implementação de caches.