Tabelas de Dispersão (Hash Tables)

Objetivo

Buscas com Complexidade Média = O(1)

Função de Dispersão

Entrada: chave de busca
Saída: número inteiro no intervalo [0...m-1] (m é o tamanho de um vetor).

Endereço Base: número calculado pela função de dispersão.
Colisão: chaves diferentes com endereços base idênticos.

Método Direto	Problemas
m = maior_chave+1 int FuncDis(chave) { return(chave); }	Total de espaços vazios pode ser muito grande. (Chaves: 1,4,789560)

Método da Divisão

Problemas

int FuncDis(chave,m)
{
return(chave%m);
}

Para certos valores de m e certo conjuntos de chaves,
o número de colisões pode ser muito elevado.

Ex: m = 128 =2⁷ e chaves são datas na repres. abaixo

                      Dia   Mes    Ano
   8/4/67 -> 01000 0100 1000011
                                       \   resto /

FuncDis(67/4/8,128) = 67
FuncDis(67/12/3,128) = 67

!!! Todas as datas de um mesmo ano receberão o
mesmo índice !!!

Método da Dobra

Execução

t = Tamanho da Dobra
d = Total de 'dígitos' da chave

int FuncDis(char * chave, int t, int d)
{
     temp = chave // strcpy
     for( i = 0 ; i < (d/t)-1 ; ++i )
     {
        for( j = 0 ; j < t ; ++j )
        {
           temp[i*t+j+t] =
               soma(temp[i*t+j+t],temp[(i*t+j+t)-(2j+1)]);
        }
     }
     return(converte(temp[i*t ... i*t+t-1]));
}

char soma(char i, char j) // Soma ignorando vai-um
converte() // Transforma 'string' em inteiro.

Chave: 279384
t = 2
d = 6
Método da Dobra:

Dobra 27 em 93 e soma
descartando 'vai-um'

7 + 9 = 6 (16 descartando 1) , 2+3 = 5

Resultado Intermediário: 6584

Dobra 65 em 84 e soma ...

5+8 = 3, 6+4 = 0

Resultado Final: 30

FuncDis("279384",2,6) = 30;

Método da Análise dos Dígitos

Execução

Acesso prévio a todas as chaves (população conhecida):

Escolha, como endereço base, o valor do dígito
na posição que resulta na menor quantidade de colisões.

Acesso a uma amostra das chaves:

Métodos de estimativa estatística.

Chaves: 443 462 492 681 712 972

1os Digitos: { 4 4 4 6 7 9 }
       -> 3 quatros, 1 seis, 1 sete e 1 nove.
2os Digitos: { 4 6 9 8 1 7 }
       -> 1 um, 1 quatro, ... (adivinha o resto :-)
3os Digitos: { 3 2 2 1 2 2 }
       -> 1 um, 4 dois,...

Escolhendo o segundo dígito como endereço
base não teríamos nenhuma colisão em
uma tabela com 10 compartimentos [0..9]

Já com o terceiro, teríamos 3.

Tratamento de Colisões

Encadeamento Exterior - Chaves em colisão são armazenadas em uma lista encadeada, externa à tabela. Cada posição da tabela de dispersão armazena um ponteiro para o início desta lista.

Exemplo:
Suponha que m = 10 e que estejamos usando o método da divisão, como função de dispersão.
Considerando a inserção das chaves {5 8 35 38 91 61 63 28}, na tabela dispersão, teríamos a seguinte situação:

	Tabela	Listas Ligadas
0	NULL
1	--->	91 - 61
2	NULL
3	--->	63
4	NULL
5	--->	5 - 35
6	NULL
7	NULL
8	--->	8 - 38 - 28
9	NULL

Encadeamento Interior - As 'listas encadeadas', com chaves em colisão, são armazenas 'dentro da própria tabela'.

Exemplo: Utilizando as mesmas suposições do exercício anterior, e considerando a escolha da próxima posição disponível no vetor, depois do endereço base (com retorno ao início se necessário), para armazenar chaves em colisão.

	Tabela - chave (Prox.Elem.)
0	28 (EOL)
1	91 (2)
2	61 (EOL)
3	63 (EOL)
4	(NOK)
5	5 (6)
6	35 (EOL)
7	(NOK)
8	8 (9)
9	38 (0)

NOK = No Key = Nenhuma Chave (-1)
EOL = End of List = Fim da Lista (-2)

Considerações Importantes:

Colisões Secundárias: Tentativa de inserir chave em 'compartimento' ocupado por chaves que foram levadas a este compartimento devido a colisões.
Solução Simples: Fundir listas (acrescentar elemento ao final da lista). Por exemplo:
Se tentarmos inserir a chave 72 na tabela acima teremos colisão secundária na posição 2. Usando a solução simples a tabela sofreria as seguintes alterações:

2

61 (4)

3

63 (EOL)

4

72 (EOL)

Endereçamento Aberto: Exige uma função de dispersão que forneça valores alternativos (até m) quando ocorre uma colisão. Com isto, não precisamos manter uma lista encadeada (economia de espaço).

Exemplos de funções de dispersão para endereçamento aberto:

// Método da Tentativa Linear
// k - Número da tentativa. (0,1,...m)
int TentativaLinear(chave,m,k)
{
    Base = FuncDis(chave,m) // Uma função de dispersão qualquer.
    return( (Base + k ) % m ) // Para cada tentativa devolve um endereço diferente.
}

// Método da Tentativa Quadrática
// k - Número da tentativa. (0,1,...m)
// Vantagem: Melhor Distribuição
// Problema: Escolher c₁ e c₂ de forma que os valores sejam
//                  diferentes para cada k.
int TentativaQuadratica(chave,m,k)
{
    Base = FuncDis(chave,m) // Uma função de dispersão qualquer
    return( (Base + c₁*k + c₂*k² ) % m )
}

// Método da Dispersão Dupla
// k - Número da tentativa. (0,1,...m)
// Problema: Como garantir valores diferentes para cada k.
int DispersaoDupla(chave,m,k)
{
    Base1 = FuncDis1(chave,m)
    Base2 = FuncDis2(chave,m)
    return( ( Base1 + k*Base2 ) % m ) // Para cada tentativa devolve um endereço diferente.
}

Material de Apoio

http://www.gpec.ucdb.br/pistori/disciplinas/ed/fontes/hash.zip
Exemplo de implementação de endereçamento aberto por tentativa quadrática código Java produzido pela acadêmica Aline Elias Amaral, Engenharia de Computação, em 2006