De que componentes é composta uma tabela hash?

Uma tabela de hash consiste em:

1. Array (ou lista): A estrutura de dados principal onde os elementos são armazenados. Às vezes chamados de "baldes" (buckets) ou "slots".
2. Função de hash: Função que recebe uma chave como entrada e retorna um índice (número inteiro) no array. Uma boa função de hash garante uma distribuição uniforme das chaves pelo array, minimizando colisões.
3. Mecanismo de tratamento de colisões: Método para resolver a situação quando a função de hash gera o mesmo índice para diferentes chaves. Dois métodos principais:
   • Encadeamento (Separate Chaining): Cada elemento do array armazena um ponteiro para uma lista (lista ligada, árvore B, etc.) de elementos que foram hashados nesse índice.
   • Endereçamento aberto (Open Addressing): Em caso de colisão, procura-se outro espaço livre no próprio array para colocar o elemento. Estratégias de busca:
     • Probing linear (Linear Probing)
     • Probing quadrático (Quadratic Probing)
     • Double hashing (Double Hashing)
4. Operações: Implementação das operações principais: inserção (insert), busca (search), remoção (delete). Essas operações usam a função de hash para determinar a localização dos elementos no array e o mecanismo de tratamento de colisões, se necessário.