Estruturas de Dados - Tabela de Dispersão

Prévia do material em texto

116319 - Estruturas de Dados
Tabela de Dispersa˜o
Guilherme N. Ramos
gnramos@cic.unb.br
Departamento de Cieˆncia da Computac¸a˜o
Universidade de Bras´ılia
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 1/19
Tabela de Dispersa˜o
(Tabela de Espalhamento / Tabela Hash)
Uma estrutura que trabalhe na ordem de log(n) e´ muito eficiente, mas o
que seria melhor?
O(1)
Isto significa que:
- A ordem de inserc¸a˜o dos elementos na˜o teˆm influeˆncia.
- O nu´mero de elementos na˜o tem influeˆncia.
- Na˜o ha´ comparac¸o˜es desnecessa´rias.
Mas como?
- O acesso direto implica a utilizac¸a˜o de uma vetor (tabela).
- Se cada chave precisa ser recuperada em um u´nico acesso, a posic¸a˜o
do elemento depende da somente da chave.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 2/19
Tabela de Dispersa˜o
Exemplo: inventa´rio de 100 itens:
- Itens identificados por uma chave de 2 d´ıgitos.
- Vetor de 100 elementos onde o ı´ndice i e´ a pro´pria chave.
E se forem menos de 100 itens? O mesmo vetor tambe´m resolve.
E se os itens forem identificados por uma chave de 7 caracteres?
ı´ndice ← func¸a˜o de dispersa˜o(chave)
A func¸a˜o de dispersa˜o associa chaves de pesquisa a uma posic¸a˜o.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 3/19
Tabela de Dispersa˜o
Vantagens:
- Utilidade
- Velocidade
Desvantagens:
- Coliso˜es
- Na˜o permite:
- ordenac¸a˜o
- recuperar o elemento antecessor/sucessor
- chaves duplicadas
- Pode necessitar de redimensionamento
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 4/19
Tabela de Dispersa˜o
Exemplo: inventa´rio de 100 itens:
- Itens identificados por uma chave de 7 d´ıgitos.
- Vetor de 100 elementos onde o ı´ndice i e´ composto pelos 2 u´ltimos
nu´meros da chave.
- Elementos com chaves bem diferentes podem estar pro´ximos no
vetor.
- Elementos com chaves bem diferentes podem estar associadas ao
mesmo ı´ndice (colisa˜o).
Chave 4967000 8421002 · · · 1234598 1234599
Posic¸a˜o 0 1 2 · · · 97 98 99
Chave 1234500? Colisa˜o...
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 5/19
Colisa˜o
A colisa˜o e´ um problema se´rio?
Problema do Aniversa´rio
Dado um grupo de 23 (ou mais) pessoas escolhidas aleatoriamente, a
chance de que duas pessoas tera˜o a mesma data de aniversa´rio e´ de mais
de 50%. Para 57 ou mais pessoas, a probabilidade e´ maior do que 99%.
Uma aplicac¸a˜o com 2500 chaves uniformemente distribu´ıdas, a serem
armazenadas em um vetor de tamanho 106 tem 95% de chance de
colisa˜o.
A colisa˜o pode ser evitada conhecendo-se todas as chaves → escolhe-se a
func¸a˜o de dispersa˜o ideal para obter a indexac¸a˜o perfeita.
Como isto na˜o e´ pra´tico, outras te´cnicas sa˜o utilizadas.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 6/19
Colisa˜o
Fator de Carga
Load Factor: raza˜o entre o nu´mero de chaves e o tamanho da tabela
- Geralmente < 0.7 (com uma boa func¸a˜o de dispersa˜o)
- Fator de carga alto indica que a memo´ria esta´ sendo bem utilizada,
mas implica em maior probabilidade de colisa˜o.
- Fator de carga baixo implica em menor probabilidade de colisa˜o mas
indica que a memo´ria esta´ sendo desperdic¸ada.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 7/19
Colisa˜o
Reespalhamento / Enderec¸amento Aberto
A maneira mais simples de lidar com a colisa˜o e´ colocar o registro na
pro´xima soluc¸a˜o dispon´ıvel.
void ht insert (dado t dado) {
int i = funcao de dispersao(dado.chave);
while(tabela [ i ] && tabela[i]−>chave != dado.chave)
i = reespalha(i);
if (! tabela [ i ])
tabela [ i ] = novo registro (dado);
// else OPS!
}
E´ preciso verificar se foi poss´ıvel inserir (a tabela pode estar cheia, ou a
func¸a˜o de reespalhamento ser inadequada). Geralmente,
int reespalha(int i ){
return ( i+c)%TAM VETOR; // c e TAM VETOR sao primos entre si
}
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 8/19
Colisa˜o
Reespalhamento / Enderec¸amento Aberto
A informac¸a˜o e´ armazenada na pro´pria tabela.
chave func¸a˜o de dispersa˜o 0 - dado1
1 - dado 2
... - dado 2
n - dado X
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 9/19
Colisa˜o
Enderec¸amento Aberto
- Reespalhamento Linear: o intervalo entre os ı´ndices e´ linear.
- (i + c)%N
- Reespalhamento Quadra´tico: o intervalo entre os ı´ndices e´
- (i + i2)%N
- Reespalhamento Duplo: o intervalo entre os ı´ndices e´ func¸a˜o de
outra dispersa˜o.
- (i + funcao de dispersao 2(i))%N
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 10/19
Colisa˜o
Espalhamento Combinado (Geral)
- As posic¸o˜es na tabela sa˜o usadas como no´s de
listas (no caso de coliso˜es).
- Estrate´gia eficiente, eficaz, e de fa´cil
implementac¸a˜o.
- Pode exigir mais memo´ria.
- Evita agrupamentos:
prima´rio : duas chaves (com ı´ndices diferentes) competem
entre si em sucessivos reespalhamentos.
secunda´rio : chaves diferentes (com o mesmo ı´ndice) seguem
o mesmo percurso de reespalhamento.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 11/19
Colisa˜o
Outros espalhamentos
- Robin Hood: uma nova chave toma o lugar de
outra se seu nu´mero de provas (testes) e´ maior
que o da que esta´ armazenada.
- Melhora o pior caso.
- Cuckoo (cuco): usa 2 ou mais func¸o˜es de
dispersa˜o. Uma nova inserc¸a˜o substitui o registro
existente, que e´ deslocado para a segunda posic¸a˜o
(e assim sucessivamente).
- Garante busca em tempo constante e amortiza
inserc¸a˜o/remoc¸a˜o.
- Hopscotch (“amarelinha”): busca em uma regia˜o
pro´xima ao ı´ndice. Se na˜o houver espac¸o para
inserc¸a˜o, acha um espac¸o pro´ximo e desloca os
itens fora da regia˜o ate´ ele (efetivamente levando
o espac¸o para dentro da vizinhanc¸a).
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 12/19
Colisa˜o
Encadeamento Separado
- Cada elemento da tabela e´ uma lista simplesmente encadeada de
todos os itens com o mesmo ı´ndice.
- Durante a busca, a lista e´ percorrida.
- Possibilita que o nu´mero de registros seja maior que o nu´mero de
posic¸o˜es na tabela (possivelmente com fator de carga aceita´vel).
- A lista pode ser ordenada dinamicamente pela chave (facilitando a
busca).
- Exige espac¸o adicional para armazenar os registros.
- Buscar na lista [ordenada] pode ser mais eficiente que mu´ltiplos
reespalhamentos (e pode na˜o ser).
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 13/19
Colisa˜o
Encadeamento
A informac¸a˜o e´ armazenada em estruturas encadeadas fora da tabela.
chave func¸a˜o de dispersa˜o 0 - dado1
1 - dado 2
... - dado 2
n - dado X
?
? ? · · ·
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 14/19
Colisa˜o
Encadeamento
Ale´m do espac¸o adicional, ha´ o custo de busca/inserc¸a˜o/remoc¸a˜o.
Mas pode-se utilizar qualquer estrutura de dados:
O(n) Lista simplesmente encadeada
O(log(n)) A´rvore AVL
O(log(n)) A´rvore Rubro-Negra
O(1) Tabela de Dispersa˜o
O(?) ?
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 15/19
Colisa˜o
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 16/19
Considerac¸o˜es sobre a Tabela de Dispersa˜o
- Teˆm tempo me´dio de busca constante.
- Custo de desenvolvimento e´ significativo.
- Avaliac¸a˜o de uma boa func¸a˜o de espalhamento e´ complexa.
- Os dados na memo´ria ficam aleatoriamente distribu´ıdos
(sobrecarrega o sistema)
- O tempo gasto na depurac¸a˜o e remoc¸a˜o de erros e´ maior do que nas
a´rvores balanceadas, que tambe´m podem ser levadas em conta para
soluc¸a˜o do mesmo tipo de problema.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 17/19
Considerac¸o˜es sobre a Tabela de Dispersa˜o
Limitac¸o˜es:
-- Estrutura de dados do tipo diciona´rio, que na˜o permite
1 armazenar elementos repetidos;
2 recuperar elementos sequencialmente (ordenac¸a˜o);
3 recuperar o elemento antecessor/sucessor.
- Para otimizar a func¸a˜o de dispersa˜o e´ necessa´rio conhecer a
natureza da chave a ser utilizada.
- no pior caso, a ordemdas operac¸o˜es pode ser O(n)
- Podem necessitar de redimensionamento.
- O custo da func¸a˜o de dispersa˜o pode ser proibitivo.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 18/19
Considerac¸o˜es sobre a Tabela de Dispersa˜o
Aplicac¸o˜es:
- Vetor associativo (cujos ı´ndices sa˜o strings arbitra´rias),
especialmente em linguagens interpretadas (AWK, Perl, e PHP).
- Indexac¸a˜o de bancos de dados (embora a´rvores sejam mais comuns).
- Cache de memo´ria: memo´ria auxiliar para acelerar o processamento.
- Conjuntos (indica a existeˆncia e recupera rapidamente)
- Representac¸a˜o de objetos em linguagens de programac¸a˜o dinaˆmicas
(Perl, Python, JavaScript, e Ruby).
- Representac¸a˜o u´nica de dados (em LISP, para evitar a criac¸a˜o
strings repetidas).
- etc.
gnramos (CIC/UnB) ED - Tabela de Dispersa˜o 19/19
	Tabela de Dispersão
	Colisão
	Considerações sobre a Tabela de Dispersão