AED3 08 01 Tabelas Hash

Videoaula da disciplina Algoritmos e Estruturas de Dados III no curso de Ciência da Computação da PUC Minas - 2018

----------------------
A tabela hash é uma estrutura de dados que associa chaves a valores. Cada par de chave e seu valor deve ser armazenado em um endereço (ou linha) específico dessa tabela. Esse endereço é determinado matematicamente por meio de uma função hash.
----------------------

As tabelas hash (ou tabelas de dispersão) são estruturas de dados em que os dados são armazenados em endereços determinados por uma função matemática, conhecida como função hash (ou função de dispersão).

Essa função hash recebe os dados que serão armazenados (um objeto ou uma entidade) e, a partir do processamento matemático desses dados, determina em que endereço esse objeto ou entidade será armazenado. Portanto, uma função hash normalmente tem a seguinte forma:

A = h(K),

em que A é o endereço em que o objeto será armazenado na tabela e K é o atributo (ou conjunto de atributos) que será usado como chave.

Uma boa função hash deve ter uma distribuição aleatória, ou seja, deve evitar a concentração de objetos em torno de um ou mais endereços. Porém, como você já sabe, é impossível se evitar que as colisões ocorram, isto é, que a função hash retorne o mesmo endereço para dois objetos diferentes. Quando isso acontece, precisamos adotar uma solução para o tratamento dessas colisões.

Na nossa disciplina, nós nos concentraremos no uso da tabela hash como uma estrutura de dados em memória secundária. Esse uso é chamado de hashing externo e uma das suas aplicações é o uso como índice em arquivos indexados.

Nesse caso, cada registro será representado na tabela hash, isto é, no índice, por meio de uma chave e de um endereço. A chave geralmente será um atributo da entidade (por exemplo, o ID dessa entidade) e o endereço será o endereço propriamente dito do registro no arquivo de dados.

Assim, durante uma busca, uma consulta ao índice usando a chave escolhida retornará o endereço e, com este endereço, poderemos localizar o registro no arquivo de dados.

A vantagem do uso de tabelas hash como índice é a velocidade com que retornam o endereço do registro. No entanto, os registros não são armazenados sequencialmente e, portanto, não é uma estrutura recomendada para acessos sequenciais.