Tabelas de espalhamento e Hashing

[Silvio Rodrigues de Faria Junior <sjunior@linux.ime.usp.br>]

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.

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.

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.

4-Para isso as funcoes de hasning associam os caracteres da string a
numeros em uma base definida (128 ou 256 para caracteres ASCII). Mas a
representacao numerica de strings gera numeros muito grandes, entao,
utilizamos o resto desse numero na divisao por um numero primo definido
pois isso tem o mesmo efeito estatistico.


Tudo isto esta' certo?

 Silvio Rodrigues de Faria Junior   <sjunior@linux.ime.usp.br>