[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: Tabelas de espalhamento e Hashing
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>