Listas encadeadas fornecem uma forma de armazenamento de
dados na memória quando não se consegue antecipar uma quantidade de itens de
informação. Um dos pontos negativos para listas encadeadas é que sua construção
obriga a acessar sequencialmente os nós de informação. Ou seja, para chegar a
qualquer nó, é necessário acessar cada nó que o antecede na lista. Varias
técnicas tais como ordenação de nós ou posicionar os mais acessados no inicio,
reduzem o tempo requerido pelas buscas sequenciais, mas nenhuma destas
alternativas elimina o mecanismo que procura item a item.
Para fornecer acesso rápido a itens aleatórios de dados
salvos na memória, uma solução elegante é a tabela de dispersão (Hash) ou
tabela espalhada. Tabelas comuns em C, tais como vetores de estruturas,
necessitam que se especifique o numero de elementos antecipadamente na tabela,
entretanto a tabela de dispersão permite ter um numero indeterminados de itens
em uma tabela sem abrir mão de um rápido acesso a qualquer item aleatoriamente.
Tabela de Dispersão suportam um dos mais eficientes
tipos de busca: espalhamento (hashing). Uma tabela de dispersão consiste em um
vetor no qual os dados são acessados através de um índice denominado chave.
A ideia primaria por trás de uma tabela de dispersão é
estabelecer um mapeamento entre um conjunto de todas as chaves possíveis e
posições no vetor, o segredo é a forma com que descobre onde irá armazenar na
tabela uma porção especifica da informação.
Espalhamento
Está descoberta é feita pela função de espalhamento que
aceita uma parte dos dados a serem armazenados na tabela como entrada
denominada chave e retorna na saída um índice que especifica a posição da
tabela, denominado codificação hash ou valor do espalhamento. Chaves podem
variar quanto ao tipo, mas a codificação hash sempre será um número inteiro.·.
Como exemplo, uma tabela com 26 posições, é simples
compor uma função de espalhamento que permite colocar palavras na tabela
utilizando a primeira letra do alfabeto:
A = table[0]
|
à
|
Absinto
|
B = table[1]
|
à
|
Batida
|
C = table[2]
|
à
|
Conhaque
|
D = table[3]
|
à
|
Destilado
|
. . .
|
. . .
|
|
Z = table[25]
|
à
|
Zero
|
Tanto o calculo do valor da codificação hash como da
indexação dentro do vetor pode ser feita em tempo fixo, o destaque do
espalhamento é realizar buscas também em tempo fixo. Quando uma função de
espalhamento consegue garantir que duas chaves não irão gerar a mesma
codificação, a tabela de dispersão resultante é nomeada de endereçamento
direto, apesar de este ser o modelo ideal, está longe de ser possível na
pratica. No código abaixo tem a implementação de uma função de espalhamento com
endereçamento direto que utiliza a data de aniversario, e sempre fornece um
valor único para cada entrada.
#include <stdio.h>
#define SIZE 366 // Numero maximo
de dias
typedef struct tagNameDay
{
char strName[64];
char strDate[6];
} sNameDay;
sNameDay Table[SIZE];
int hash( char * );
int
InsertTable(sNameDay *);
int main(int argc, char
*argv[])
{
int i;
sNameDay
sDummy1 = { "Vanusa" , "31/12" };
sNameDay
sDummy2 = { "Roberto", "14/02" };
sNameDay
sDummy3 = { "Mariana", "06/11" };
sNameDay
sDummy4 = { "Laura", "28/10" };
sNameDay
sDummy5 = { "Bianca", "27/10" };
sNameDay
sDummy6 = { "Clone", "14/02" };
for ( i = 0; i < SIZE; i++ )
Table[i].strName[0]
= '\0';
InsertTable(&sDummy1);
InsertTable(&sDummy2);
InsertTable(&sDummy3);
InsertTable(&sDummy4);
InsertTable(&sDummy5);
InsertTable(&sDummy6);
return 0;
}
int Hash(char *strDate)
{
const int
iTotalDays[12] = {0, 31, 60,
91,
121,
152, 182, 213,
244,
274, 305, 335 };
int iMonth, iDay;
iMonth =
atoi ( strDate + 3 );// Converte o mesh em int
strDate[2] = '
\0'; // marca o local que acaba o dia
iDay
= atoi ( strDate ); // Converte o dia em int
return (
iTotalDays[iMonth - 1] + iDay );
}
int
InsertTable(sNameDay *pVal)
{
int iHashValue;
iHashValue =
Hash(pVal->strDate);
if ( Table[iHashValue].strName[0] == '\0' ) { // vazio
strcpy(Table[iHashValue].strName,
pVal->strName);
strcpy(Table[iHashValue].strDate,
pVal->strDate);
}
else // duplicado,
printf ( "collision\n");
}
|
Endereçamento
direto se torna inviável conforme a quantidade de informação aumenta, nos
exemplos dados a tabela mudou de 26 para 366 posições, mesmo aumentando o armazenamento,
esse tipo de solução deixa de ser pratica, imagine um sistema que aceite como
entrada os oitos primeiros caracteres de um nome e o use para encontrar
informações desta pessoa, utilizando um endereçamento direto teríamos a
combinação de oito caracteres das 26 letras do alfabeto que resultaria num
total de 208.827.064.576 entradas, com uma grande maioria sem uso, pois a maior
parte de combinações de letras não resulta em nomes, ex.: “zzzzzzaz”.
Colisão
O numero de entrada de uma tabela de dispersão é pequeno
em relação à quantidade de todas as chaves possíveis, como consequência, a
maioria das funções de espalhamento endereçam duas chaves para a mesma posição,
ocorrendo uma colisão.
Devem-se evitar
sempre as colisões, entretanto se tem de estar preparado para lidar com as
mesmas, um dos problemas imediato é resolver duas entradas no qual o valor de
espalhamento direcionou para a mesma posição da tabela, nos exemplos acima, as
palavras conhaque e cachaça seriam colocadas na mesma posição da tabela
(table[18]), com o mesmo ocorrendo com as datas de aniversário duplicadas. Para
a colisão ser solucionada, existem varias alternativas, todavia as diferentes
abordagens se resumem a duas categorias:
TABELA DE DISPERSÃO
|
|
No qual o elementos que colidem são armazenados na
tabela através de uma lista encadeada. Que irá crescer o necessário para
acomodar as colisões
|
|
Endereçamento aberto
|
Refazer espalhamento computando um novo valor para a
chave usando vários métodos de sondagem na tabela.
|
Saber qual método
melhor se encaixa para uma determinada situação depende de duas analises:
1)
Escolher a função de espalhamento:
O principal assunto do
espalhamento, ao distribuir chaves aleatoriamente pela tabela, colisões tendem
a ser minimizado, motivo que aumenta a importância de fazer a opção pela função
de espalhamento que melhor atinja este objetivo.
2)
Determinar colisões:
Métodos para tratar o mapeamento de
varias chaves para o mesmo índice. Tabelas de dispersão encadeadas possuem o
formato inerente para solucionar colisões, enquanto que tabelas de dispersão
com endereçamento aberto utilizam várias formas para examinar a tabela.
Aplicações para tabelas de
dispersão
Banco de dados
|
Especificamente, aquele que requerem acesso aleatório
(isto é, a qualquer dado) eficiente, geralmente a sistemas de banco de dados
aperfeiçoam através de dois métodos de acesso: sequencial e aleatório. Tabelas
de dispersão é uma parte importante para o acesso aleatório eficiente devido
à forma com que localizam dados em taxas de tempo regulares
|
Tabelas de símbolos
|
Tabelas usadas pelos compiladores para manter
informações sobre os símbolos do programa. Compiladores acessam informação
sobre símbolos constantemente, portanto é importante que o acesso seja
implementado de forma eficiente.
|
Cachê de marcações
|
Um mecanismo para armazenar e recuperar dados de uma
maneira independente da maquina. Cada membro de dados reside em uma posição
fixa dentro do deslocamento do cachê. Uma tabela de dispersão é armazenada no
buffer para que a localização de cada membro marcado possa ser apurada
rapidamente.
|
Dicionário
|
Estruturas de dados que suportam adição, exclusão e
busca de dados. Devido às semelhanças entre as operações de uma tabela de
dispersão e de um dicionário, ao programar um dicionário de dados, uma tabela
de dispersão é particularmente eficiente.
|
Vetores associativos
|
Usados de forma bastante comum pelas linguagens que não
suportam a criação de um tipo estruturado como o dicionário, vetores
associativos consistem em dados arranjados em pares (chave, valor). Uma tabela de dispersão ajuda a encontrar de forma
efetiva a chave em cada vetor.
|
