Tabela hash

Prévia do material em texto

Tabela Hash
emanoelim@utfpr.edu.br
Tabela Hash
• Muitos métodos de busca baseiam-se em comparação de 
chaves para encontrar um algum dado. 
• Se os dados estiverem ordenados, este tipo de busca pode 
ter um custo O(log n). 
• Seria possível encontrar um dado sem a necessidade de 
comparar chaves, ou com custo constante - O(1)?
Tabela Hash
• Sabemos que em vetores, conseguimos acessar um dado 
de forma direta através de um índice, com custo O(1).
• Entretanto, como não temos como saber em qual índice 
cada dado está, normalmente precisamos fazer uma 
busca sequencial, que tem custo O(n).
Tabela Hash
• As tabelas de hash (tabelas de espalhamento, tabelas de 
dispersão) são uma solução para este problema. Uma 
tabela hash associa chaves e valores:
• Chave: uma parte da informação que compõe o item a 
ser inserido ou buscado.
• Valor: posição onde o item deve estar no vetor.
Tabela Hash
• A tabela hash usa uma função que tem como entrada a chave. 
• Com base na chave, a função calcula um valor que será a 
posição onde o item deve ser inserido. 
• Chamamos esta função de função de hashing.
• Este processo chama-se “espalhar”, pois os itens não serão 
inseridos de forma ordenada. 
• Hash, em inglês, quer dizer “confusão”.
Tabela Hash
Fonte: https://commons.wikimedia.org/w/index.php?curid=6471238
A função de hashing é usada tanto para 
calcular a posição onde um item deve 
ser inserido, quanto para buscar um 
item: a partir da chave do item, será 
possível calcular a posição onde ele foi 
guardado, recuperando-o a um custo 
constante.
Funções de hashing
• Vimos que uma função de hashing tem como objetivo 
pegar uma chave e mapear esta chave em uma posição.
• Existem diferentes possibilidades para implementar a 
função de hashing. 
• Algumas das funções mais conhecidas são:
Funções de hashing
• Método da divisão: encontra-se o resto da divisão da 
chave pelo tamanho máximo da tabela, usando este resto 
como posição. Ex.: 
• tamanho da tabela = 50
• chave = 92
• o item será guardado na posição: 92 % 50 = 42
Funções de hashing
• Método da multiplicação: a chave é multiplicada por uma 
constante c, tal que 0 < c < 1. 
• Multiplica-se a chave por esta constante;
• Seleciona-se a parte fracionária desta multiplicação;
• A parte fracionária é multiplicada pelo tamanho da tabela;
• A parte inteira desta multiplicação é usada como posição.
Funções de hashing
• Método da multiplicação: 
Exemplo:
• tamanho da tabela = 50, chave = 92, c = 0,321
• chave * c = 29,523
• parte fracionária = 0,523
• tamanho da tabela * parte fracionária = 26,600
• parte inteira = 26 (o item de chave 92 será guardado em na 
posição 26)
Funções de hashing
• Método da dobra: a chave é 
interpretada como uma sequência de 
dígitos escrita em um papel. Enquanto a 
chave for maior que o tamanho da 
tabela, o papel vai sendo dobrado ao 
meio e os dígitos que se sobrepõe são 
somados sem levar em consideração o 
“vai um”. A soma final é usada como 
chave. Fonte: http://www.lcad.icmc.usp.br/~nonato/ED/Hashing/node36-b.html
Funções de hashing
• Hashing com strings: é possível usar uma string como chave para 
gerar uma posição. Intuitivamente, poderíamos pensar em somar os 
códigos ASCII de cada caractere da string. O problema é que chaves 
como “cama” e “maca” teriam a mesma soma e, consequentemente, 
a mesma posição. Por isso, temos que fazer uma abordagem um 
pouco diferente.
Funções de hashing
• Hashing com strings: uma ideia seria pegar o código ASCII de cada 
caractere e multiplicá-lo por um número inteiro na base 256. Por 
exemplo, para mapear a string “abcd”, teríamos:
97 * 256^3 + 98 * 256^2 + 99 * 256^1 + 100 * 256^0 =
1633837924
Em seguida, encontra-se o resto do resultado pelo tamanho da 
tabela.
Funções de hashing
• Obs.: se a ideia da tabela hash é acessar os itens através de posições, 
com um custo constante, então as funções que geram estas posições 
devem ser simples e rápidas. 
Colisões
• Qualquer função de hashing está sujeita a gerar a mesma posição para 
chaves diferentes. Este fenômeno é chamado de colisão.
• Considere, por exemplo, o método da divisão para uma tabela hash de 
tamanho = 50.
• A chave 60 irá ser mapeada para a posição 10 (60 % 50 = 10)
• A chave 110 também será mapeada para a posição 10 (110 % 50 = 10)
• Este tipo de situação precisa ser tratado, para que um item não 
sobrescreva outro.
Funções perfeitas / imperfeitas
• Dizemos que uma função de hashing é perfeita quando chaves 
diferentes sempre são mapeadas para posições diferentes. Ou 
seja, nunca acontecem colisões.
• Este tipo de função se encaixa em aplicações muito específicas, 
geralmente quando já se conhece previamente todas as chaves 
que podem ser inseridas.
Funções perfeitas / imperfeitas
• Uma função de hashing é imperfeita quando podem acontecer 
colisões, e é neste tipo de situação que irão se encaixar a 
maioria dos problemas.
• Isso quer dizer que será necessário utilizar alguma abordagem 
para fazer o tratamento de colisões.
Implementação
• Inicialmente será analisada uma implementação que não faz o 
tratamento de colisões. 
• Na sequência, esta implementação será aprimorada para que as 
colisões sejam tratadas.
Implementação
• Será usada a seguinte estrutura:
Obs.: código no github.
Referências
• Ziviani, N. “Projeto de algoritmos com implementações em C e Pascal”, 
Cengage Learning, 3ª ed., 2010.
• Notas de aula Prof. Luis Gustavo Nonato:
http://www.lcad.icmc.usp.br/~nonato/ED/Hashing/node33.html
• Vídeo aulas sobre tabela hash:
https://www.youtube.com/watch?v=njkANXEMHTY