Espalhamento

O objetivo de uma função de espalhamento é distribuir seus elementos na tabela de forma uniforme e de maneira aleatória para evitar aglomeração de valores semelhantes, sem perder a eficiência e rapidez, sempre gerando o mesmo índice na tabela para a mesma chave de entrada. Teremos a função espalhamento denominada hash que irá mapear a chave k para a posição x na tabela, formalmente definido:

hash(k) = x

Quando apresentado a rotina de espalhamento de datas de aniversário na introdução a Tabela de Dispersão, foi apresentado um caso especial conhecido como espalhamento perfeito, no sentido de que duas datas jamais irão gerar o mesmo valor, para criar uma rotina assim, devem-se conhecer todas as entradas possíveis e ser capaz de gerar um valor único para cada uma delas, objetivo alcançado de forma simples no exemplo de aniversários quando se tem a conhecimento da faixa de datas e como obter um valor único da mesma.

Em situações práticas, o algoritmo de espalhamento perfeito é impossível de se obter, a dificuldade se deve a um fator, não é possível prever o conjunto completo de dados que será disperso na tabela, como resultado desenvolve-se soluções de caso geral.

 Qualquer que seja o método para conversão de chaves, lembre-se de que o mais importante é a distribuição uniforme e aleatória de posições na tabela, dois métodos simples podem ser usados:

Divisão: Tendo k como um inteiro, uma das formas mais simples de espalhamento é mapear a posição na tabela é dividir o inteiro pelo tamanho da tabela e utilizar o valor de modulo (resto da divisão):

hash(k) = k mod m

Como exemplo, uma tabela tem m = 1.000 posições, e a chave k = 31.415.926:

31.415.926 mod 1.000 = 926.

Apesar do valor de tabela exemplo ser simples, deve-se evitar utilizar tamanhos de tabelas cujo valor seja potência de 2 que gera repetição de índices em determinadas faixas, note que no exemplo acima o valor de índice termina por ser os ultimo dígitos da chave de entrada, na computação a potência de 2 são os bits de baixa ordem, o que torna irrelevante o processo de obter o modulo da chave, se para isso basta pegar apenas os dígitos finais, como solução, utiliza-se para tamanho da tabela um numero primo, permitindo maior aleatoriedade.

Troca-se m de 1000 por 997, por ser um valor próximo ao da tabela exemplo, a rotina de espalhamento resulta no valor:

31.415.926 mod 997 = 456.

Multiplicação: Como alternativa para a divisão, ao multiplicar o inteiro k por uma constante A na faixa 0 < A < 1; para o exemplo utilizamos a proporção áurea menos 1, com A = 0.618, após essa multiplicação, extrai a parte fracionária fazendo modulo do resultado com 1 e multiplica pelo numero de posições na tabela:

hash(k) = m ( k * A mod 1)

No método da divisão havia a preocupação em ter um tamanho de tabela de valor primo, a vantagem da multiplicação é tornar a escolha do tamanho da tabela independente do calculo, com a tabela podendo assumir um valor de potência de 2, tendo 1000 posições, temos:

1000 * ((31.415.926 * 0,618) mod 1)

1000 * (19.415.042,268 mod 1)

1000 * 0,268

268

Apesar da vantagem na escolha da tabela em relação ao método da divisão, tem como ponto negativo uma quantidade maior de calculo necessário, tornando o método da multiplicação lento quando comparado ao da divisão.

#include <stdio.h> #include <math.h> #define TABLE_PRIME_SIZE   997 #define TABLE_SIMPLE_SIZE  1000 typedef unsigned char      BYTE; typedef unsigned short int WORD; typedef unsigned long int  DWORD; WORD HashDiv(DWORD dwKey) {        return (WORD) (dwKey % TABLE_PRIME_SIZE); } WORD HashMul(DWORD dwKey) {        double dFrac;        dFrac = fmod(dwKey * 0.618, 1);        return (WORD) (TABLE_SIMPLE_SIZE * dFrac); } void main(void) {        WORD wIndex;        wIndex = HashDiv(31415926); printf("indice: %d\n", wIndex);        wIndex = HashMul(31415926); printf("indice: %d\n", wIndex); }

Vale observar que apesar do método ser nomeado de multiplicação, pode-se contestar o conceito, afinal multiplicar por um fracionário, equivale a dividir, ambos os métodos acabam utilizando o valor do modulo de diferentes maneiras para obter um valor dentro da faixa de índices da tabela.

Grande parte das rotinas de espalhamento utiliza a entrada k como sendo um inteiro, tornando simples para alterar matematicamente o valor de k dentro da rotina de espalhamento para retornar uma posição na tabela.

Quando a chave k não é inteiro, precisa ser feita a conversão, como converter um conjunto de chaves depende das características da mesma, é importante obter o conhecimento da aplicação em particular para evitar modelos pobres de conversão de palavras em chaves que podem se basear apenas nos caracteres do inicio ou do fim, que acabará por gerar uma quantidade de resultados iguais.  Como alternativa, seleciona-se varias posições, fazendo arranjos e substituições para tornar o elemento ainda mais aleatório e transpor esses caracteres em um numero inteiro.

Um dos criadores da linguagem AWK, Peter J. Weinberger desenvolveu um excelente algoritmo para transformar chaves de variados tipos em inteiros, uma variante de sua versão foi utilizada no UNIX para espalhamento quando se gera o arquivo executável no formato ELF, esse mesmo algoritmo foi publicado no famoso livro do dragão sobre compiladores.

DWORD HashPjw ( const char *strData ) {        DWORD dwKey = 0, dwTmp;        while ( *strData )        {              dwKey = ( dwKey << 4 ) + *strData++;              if ( dwTmp = dwKey & 0xF0000000 )                     dwKey ^= dwTmp >> 24;              dwKey &= ~dwTmp;        }        return dwKey; }

Como exemplo, observe como a rotina transforma a string “Roberto Bauer” em um valor numérico, em um loop seleciona-se sequencialmente o valor de byte para somar na chave e desloca o resultado em 4 bits para a esquerda.

while ( *strData )              dwKey = ( dwKey << 4 ) + *strData++; . . .

Para evitar o descartar o estouro das operações de soma e deslocamento feitas no calculo da chave no instante em que a mesma esteja preste a romper o limite da Double Word, utiliza-se a condicional abaixo para armazenar o valor dos 4 bits mais significativos da chave até o momento em dwTmp.

. . .              if ( dwTmp = dwKey & 0xF0000000 ) . . .

Por fim, realizam mais duas operações com os 4 bits, uma operação OU EXCLUSIVO (^) com os bits 4 a 7 e um E LOGICO com COMPLEMENTO A UM (& ~) com os bits de 28 a 31.

. . .                     dwKey ^= dwTmp >> 24;              dwKey &= ~dwTmp; . . .

Segue na tabela a simulação completa, os valores se apresentam em hexadecimal para facilitar a interpretação das operações bit a bit.

Data	K << 4	K + Data	Tmp >> 24	K^=Tmp>>24	~Tmp	K &= ~Tmp
R - 52	00000000	00000052	00000000	00000052	FFFFFFFF	00000052
o - 6F	00000520	0000058F	00000000	0000058F	FFFFFFFF	0000058F
b - 62	000058F0	00005952	00000000	00005952	FFFFFFFF	00005952
e - 65	00059520	00059585	00000000	00059585	FFFFFFFF	00059585
r - 72	00595850	005958C2	00000000	005958C2	FFFFFFFF	005958C2
t - 74	05958C20	05958C94	00000000	05958C94	FFFFFFFF	05958C94
o - 6F	5958C940	5958C9AF	00000050	5958C9FF	AFFFFFFF	0958C9FF
- 20	958C9FF0	958CA010	00000090	958CA080	6FFFFFFF	058CA080
B - 42	58CA0800	58CA0842	00000050	58CA0812	AFFFFFFF	08CA0812
a - 61	8CA08120	8CA08181	00000080	8CA08101	7FFFFFFF	0CA08101
u - 75	CA081010	CA081085	000000C0	CA081045	3FFFFFFF	0A081045
e - 65	A0810450	A08104B5	000000A0	A0810415	5FFFFFFF	00810415
r - 72	08104150	081041C2	00000000	081041C2	FFFFFFFF	081041C2

Ao fim da rotina o resultado tem de ser aplicado ao método da divisão ou multiplicação sobre o tamanho da tabela para obter o índice.

. . .       WORD wIndex;       wIndex = HashDiv(HashPjw("Roberto Bauer"));       printf("indice: %d\n", wIndex); . . .

Como em todas as abordagens, é possível que um algoritmo genérico de espalhamento como o HashPjw não seja tão eficiente como um criado para determinado problema em particular, entretanto percebem-se que aplicações gastam muito pouco tempo processando as rotinas de espalhamento, os pontos necessários para o calculo da chave em índice ser eficientes são:

·         Conter no máximo uma divisão, de preferência a operação de modulo.

·         Gerar uma longa faixa de índices

·         Não usar atributos da informação que tendem a ser comum

A menos que surja alguma necessidade especifica, as rotinas genéricas para espalhamento acima mostradas devem ser suficientes, recomenda-se não perder tempo buscando aperfeiçoar seu desempenho uma vez que menos de 2% de todo o processamento será feito pela função.