Tabela de Hash (Hash Table)

Na ciência da computação, uma tabela de hash (hash table) é uma estrutura de dados pela qual implementa um tipo de dado abstrado de array associativo, uma estrutura que pode mapear chaves para valores. Uma tabela de hash utiliza uma função de hash para calcular um índice em um array de buckets ou slots, a partir do qual o valor desejado pode ser encontrado.

Idealmente, a função de hash irá atribuir a cada chave a um bucket único, mas a maioria dos designs de tabela de hash emprega uma função de hash imperfeita, pela qual poderá causar colisões de hashes onde a função de hash gera o mesmo índice para mais de uma chave. Tais colisões devem ser acomodados de alguma forma.

Colisão de hash resolvida por encadeamento separado.

Made with okso.app

Referências

• Wikipedia
• YouTube