Buckets hash

Tabelas hash [HashMaps] na computação são estruturas de dados que efetivamente permitem acesso direto a objetos com base em suas chaves [strings ou integer exclusivos]. Uma tabela hash usa uma função hash para indexar em uma matriz de buckets ou slots para encontrar o valor desejado. As principais características das chaves utilizadas são:

• As chaves usadas podem ser números de previdência social (SSN, na sigla em inglês), números de telefone, números de contas etc.
• As chaves devem ser exclusivas.
• Cada chave é associada (mapeada) a um valor.

Os buckets hash são usados para atribuir itens de dados para fins de classificação e pesquisa. O objetivo deste trabalho é enfraquecer a lista encadeada para que as buscas por itens específicos sejam acessíveis em um curto espaço de tempo. Uma tabela hash que usa buckets é, na verdade, uma combinação de uma matriz e uma lista encadeada. Cada elemento da matriz [tabela hash] é um cabeçalho de uma lista encadeada. Todos os elementos com hash para o mesmo local são armazenados na lista. A função hash atribui cada registro ao primeiro slot em um bucket. Se um slot estiver cheio, os slots de bucket serão pesquisados em ordem até que um slot vazio seja encontrado. Se o bucket estiver cheio, os registros serão armazenados em um bucket de overflow de capacidade infinita no final da tabela. Todos os buckets compartilham o mesmo bucket de overflow. No entanto, uma boa implementação usa uma função hash que distribui os registros de maneira uniforme pelos buckets para minimizar o máximo possível o número de registros no bucket de overflow.