Do que é composta uma tabela hash?

Uma tabela de hash consiste numa matriz de tamanho fixo (balde ou slot) e numa função de hash.

• Matriz (Baldes/Slots): Representa uma sequência de células onde são armazenados pares "chave-valor". O tamanho da matriz determina o número de locais possíveis para armazenar elementos.

• Função de hash: Converte a chave num valor inteiro (código de hash), que é usado para determinar o índice da célula na matriz (balde), onde o valor correspondente será armazenado ou extraído.

Além disso, pode haver:

• Estratégia de resolução de colisões: Mecanismo para lidar com situações em que chaves diferentes geram o mesmo código de hash e apontam para a mesma célula da matriz. Estratégias comuns:
  • Método de encadeamento (Encadeamento separado): Cada célula da matriz armazena um ponteiro para uma lista ligada (ou outra estrutura de dados), contendo todos os pares "chave-valor" cujos códigos de hash apontam para essa célula.
  • Método de endereçamento aberto: Em caso de colisão, busca-se uma célula livre na matriz seguindo uma regra determinada (por exemplo, sondagem linear ou quadrática).