Tabela Hash

Prévia do material em texto

ESTRUTURA DE DADOS: TABELA HASH
Nesse tipo de estrutura de dados, os valores são armazenados de maneira dispersa
e estão “linkados” a uma chave, pela qual é possível acessar os dados. Para a construção
da tabela, o desenvolvedor deve escrever uma função que determine o espaço em que os
dados serão armazenados na memória do computador.
Exemplo de função usando Folding:
Caso queira armazenar, por exemplo, um número de telefone como "(54)
1122-3344", será necessário separar o número de dois em dois e somá-los, após realizar
seu módulo. 54 + 11 + 22 + 33 + 44 = 164 % 12 = 8. No espaço 8 da tabela, ficará
armazenado o número de telefone.
A Tabela Hash permite armazenar grande volume de informações e acessá-los com
facilidade, garantindo uma complexidade O(1) quando bem implementada. Dessa forma,
esse deve ser o algoritmo escolhido nos casos em que essas características são relevantes,
como bases de dados.
Colisões nessa estrutura de dados ocorrem quando uma mesma chave leva a dois
dados diferentes, ou seja, a função que construiu a tabela possui falhas. As colisões são
ruins, pois atrapalham o desempenho do algoritmo e, no caso de Tabelas que recebem
itens criptografados, devem ser evitadas por comprometerem a segurança das
informações.
Em uma rede social, cada hashtag funciona como uma chave dentro de uma Tabela
Hash, cada qual apontando para uma lista de posts associados àquela hashtag.
Hashtag = hash + tag (rótulo/etiqueta)