RE: Tabelas de espalhamento e Hashing

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Silvio Rodrigues de Faria Junior writes:
 > A ultima aula (22/09/98) sobre tabelas de espalhamento e hashing ficou um
 > pouco obscura, mas como voce sugeriu eu procurei o assunto no Knuth apesar
 > de nao dominar bem o idioma ingles.
 > Portanto gostaria que me corrigisse se estiver errado:
 > 
 > 1-O objetivo da tabela de espalhamento e' de ordenar um conjunto de dados
 > de forma que eles fiquem distribuidos uniformemente para que a futura
 > busca desses dados seja mais eficaz.

Certo!

 > 2-Para tal, a ordenacao dos dados (no caso strings) por ordem alfabetica
 > nao e' recomendado, tao pouco a ordenacao de strings por tamanho, pois
 > podemos ter muito mais palavras que comecam com A, ou com 7 letras do que
 > palavras que comecem com Q ou tenham 13 letras.

Sim.

 > 3-A solucao para este problema e' entao uma funcao de hashing, que foram
 > analisadas estatisticamente e se mostraram muito mais eficientes para o
 > objetivo de alocar grupos de dados de tamanhos muito parecidos.

OK.

 > 4-Para isso as funcoes de hasning associam os caracteres da string a
 > numeros 

Sim, as funções de hashing são em geral funções aritméticas e para tanto
precisamos interpretar as nossas chaves como números de alguma forma, para
podermos fazer contas com eles.  O uso da tabela ASCII é uma forma natural de
atribuir valores numéricos a caracteres.

 > em uma base definida (128 ou 256 para caracteres ASCII). Mas a
 > representacao numerica de strings gera numeros muito grandes, 

Sim, se pensamos em strings como números em base 128 ou 256.

 > entao, utilizamos o resto desse numero na divisao por um numero primo
 > definido pois isso tem o mesmo efeito estatistico.

O fato de que esta função é uma boa função de hashing é um fato que tem
explicações teóricas e que também foi verificado experimentalmente em
contextos práticos.

Yoshi

 > Tudo isto esta' certo?
 > 
 >  Silvio Rodrigues de Faria Junior   <sjunior@linux.ime.usp.br>