AEDSII_aula_022_hashing2

Prévia do material em texto

Pesquisa em memória 
primária: hashing 
Algoritmos e Estruturas de Dados II 
Hashing Dinâmico 
2 
}  Evita que o fator de carga fique muito alto (N/M) 
}  Ideia: dobra o tamanho da tabela 
hashing quando fator de carga passa 
de um limiar. 
α = N / M C(n) 
0.1000 1.0556 
0.2000 1.1250 
0.3000 1.2143 
0.4000 1.3333 
0.5000 1.5000 
0.6000 1.7500 
0.7000 2.1667 
0.8000 3.0000 
0.9000 5.5000 
0.9500 10.5000 
0.9800 25.5000 
0.9900 50.5000 
void expande(TipoPesos p, TipoDicionario T) { 
 
 T2 = NovoHeap(2 * M); 
 for (i = 0; i < M; i++) 
 if (((strcmp(T[i].Chave, Vazio) != 0) && 
 (strcmp(T[i].Chave, Retirado) != 0) 
 InsereHashing(T[i].Chave,p,T2); 
} 
 
/* libera a memória para T */ 
Hashing Duplo 
3 
}  Mecanismo para resolução de colisão 
}  Endereçamento aberto apresenta o efeito de 
agrupamento 
}  Agrupa chaves próximas a um endereço, mesmo que a 
função de espalhamento não a coloque lá. 
}  Solução: hashing duplo 
}  Ao invés de examinar cada uma das posições sucessivas 
após uma colisão, uma segunda função de hashing é aplicada. 
Hashing Duplo 
4 
Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T)‏ { 
unsigned int i=0, count = 0; 
unsigned int Inicial, segundo; 
 
 Inicial = h(Ch, p); /* transforma a chave */ 
 segundo = h2(Inicial); /* h2(x) = ((x%97)+1) */ 
 
 while ((strcmp(T[(Inicial + i) % M].Chave, Vazio) != 0) && 
 (strcmp(T[(Inicial + i) % M].Chave, Ch) != 0) && 
 (count < M)) { 
 i += segundo; count++; 
 } 
 
 if (strcmp(T[(Inicial + i) % M].Chave, Ch) == 0) 
 return ((Inicial + i) % M); 
 else 
 return M; /* Pesquisa sem sucesso */ 
} 
Hashing Duplo: Análise 
5 
α = N / M C(n) 
0.1000 1.0536 
0.2000 1.1157 
0.3000 1.1889 
0.4000 1.2771 
0.5000 1.3863 
0.6000 1.5272 
0.7000 1.7200 
0.8000 2.0118 
0.9000 2.5584 
0.9500 3.1534 
0.9800 3.9919 
0.9900 4.6517 
⎟
⎠
⎞
⎜
⎝
⎛
−
=
α
ln
α
)n(C
1
11
Hashing Duplo: Análise 
6 
Hashing 
duplo 
Endereçamento 
aberto linear 
α = N / M C(n) C(n) 
0.1000 1.0536 1.0556 
0.2000 1.1157 1.1250 
0.3000 1.1889 1.2143 
0.4000 1.2771 1.3333 
0.5000 1.3863 1.5000 
0.6000 1.5272 1.7500 
0.7000 1.7200 2.1667 
0.8000 2.0118 3.0000 
0.9000 2.5584 5.5000 
0.9500 3.1534 10.5000 
0.9800 3.9919 25.5000 
0.9900 4.6517 50.5000 
⎟
⎠
⎞
⎜
⎝
⎛
−
+=
α1
11
2
1)(nC
Endereçamento aberto: 
Hashing duplo: 
⎟
⎠
⎞
⎜
⎝
⎛
−
=
α
ln
α
)n(C
1
11
Hashing Perfeito 
7 
}  Uma função de espalhamento h é perfeita se 
 h(xi) ≠ h(xj) para todo i ≠ j 
}  Desta maneira, não haverá colisões de chaves. 
}  Problema: 
}  Quando chaves adicionais foram adicionadas, colisões 
poderão ocorrer. 
}  Indicações de uso: 
}  Conjunto de chaves seja estático e frequentemente 
pesquisado. Exemplo: palavras-chave de um compilador 
Hashing Perfeito 
8 
}  Definição anterior permite que tabelas grandes sejam 
utilizadas (M >> N), o que não economiza muito 
espaço de armazenamento. 
}  Além de perfeita, idealmente uma função de 
espalhamento deve ser mínima. Se há N chaves, 
tem-se uma tabela de espalhamento com N posições. 
Hashing Perfeito 
9 
}  Encontrando uma função de hashing perfeita 
}  Abordagens: 
}  Funções de espalhamento perfeitas por redução do 
quociente 
}  h(x) = (x + s) / d (para inteiros s e d) 
}  Funções de espalhamento perfeitas por redução de resto 
}  h(x) = ((r + s * x) % z) / d 
}  Espalhamento recíproco – espalhamento perfeito e mínima 
}  h(x) = (c / (d * x + e)) % M 
}  Quando chaves são primos entre si: h(x) = (c / x) % M 
Exercícios 
10 
}  Mostre	
  o	
  estado	
  final	
  de	
  um	
  dicionário	
  com	
  resolução	
  de	
  
conflitos	
   por	
   encadeamento	
   depois	
   da	
   inserção	
   das	
  	
  
chaves	
  q	
  u	
  e	
  s	
  t	
  a	
  o	
  f	
  c	
  i	
  l.	
  Considere	
  que	
  o	
  dicionário	
  não	
  
armazena	
   chaves	
   duplicadas,	
   que	
   o	
   valor	
   de	
   cada	
  
caractere	
   é	
   sua	
   ordem	
   no	
   alfabeto	
   e	
   que	
   o	
   dicionário	
  
possui	
  uma	
  tabela	
  com	
  5	
  listas	
  (isto	
  é,	
  M	
  =	
  5).	
  
}  Mostre o conteúdo de um dicionário com resolução de 
conflitos com endereçamento aberto depois da inserção 
das chaves q u e s t a o f c i l. Considere que a tabela do 
dicionário tem 17 posições e que o valor de cada 
caractere é sua ordem no alfabeto.