Na resolução de colisões por encadeamento interno cada posição da tabela guarda no máximo um elemento e, portanto, é necessário conhecer o número máximo de elementos à priori por forma a garantir o espaço necessário na tabela aquando da sua inicialização. Vamos ver agora duas estratégias diferentes para resolver colisões neste caso.
Resolução por procura linear
Se a posição $k$ da tabela estiver ocupada, então guardamos o elemento na posição seguinte livre (linear probing).
Exemplo:
/** * Ordem de insercao: 707, 72, 14, 70, 76, 20 * hash(k) = k mod 7 * * Inserir 707: h(707) = 0 * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | | | | | | | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 * * Inserir 72: h(72) = 2 * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | | 72 | | | | | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 * * Inserir 14: h(14) = 0 * Posicao 0 ocupada, proxima livre: 1 * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | 14 | 72 | | | | | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 * * Inserir 70: h(70) = 0 * Posicao 0 ocupada, proxima livre: 3 * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | 14 | 72 | 70 | | | | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 * * Inserir 76: h(76) = 6 * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | 14 | 72 | 70 | | | 76 | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 * * Inserir 20: h(20) = 6 * Posicao 6 ocupada, proxima livre: 4 * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | 14 | 72 | 70 | 20 | | 76 | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 */
Portanto, em resumo, na resolução de conflitos: se a posição correspondente ao índice devolvido pela função de dispersão estiver ocupada, incrementar o índice até encontrar a primeira posição livre.
No caso da remoção de um elemento, após encontrar o mesmo, colocamos a posição a NULL e reinserimos todos os elementos que se seguem até à próxima posição vazia.
Exemplo:
/** * Remover o 14 em: * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | 14 | 72 | 70 | 20 | | 76 | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 * * hash(14) = 0, mas o 14 esta na posicao 1 (procura linear) * Colocar a posicao 1 a NULL: * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | | 72 | 70 | 20 | | 76 | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 * * Reinserir 72, 70, e 20: * +-----+-----+-----+-----+-----+-----+-----+ * | 707 | 70 | 72 | 20 | | | 76 | * +-----+-----+-----+-----+-----+-----+-----+ * 0 1 2 3 4 5 6 */
Implementação
#include <stdlib.h>
#include "Item.h"
#define null(A) (key(st[A]) == key(NULLitem))
static int N, M;
static Item *st;
void STinit(int max) {
int i;
N = 0;
M = 2 * max;
st = (Item*)malloc(M*sizeof(Item));
for (i = 0; i < M; i++)
st[i] = NULLitem;
}
void STinsert(Item item) {
Key v = key(item);
int i = hash(v, M);
while (!null(i)) i = (i+1) % M;
st[i] = item;
N++;
}
Item STsearch(Key v)
{
int i = hash(v, M);
while (!null(i))
if (eq(v, key(st[i]))
return st[i];
else
i = (i+1) % M;
return NULLitem;
}
void STdelete(Item item)
{
int j, i = hash(key(item), M);
Item v;
while (!null(i))
if (eq(key(item), key(st[i])) break;
else i = (i+1) % M;
if (null(i)) return;
st[i] = NULLitem;
N--;
for (j = (i+1) % M; !null(j); j = (j+1) % M, N--) {
v = st[j];
st[j] = NULLitem;
STinsert(v);
}
}Análise
Notar que a taxa de ocupação $\alpha = \frac{N}{M}$ tem de ser menor do que $1$ quando utilizamos resolução por encadeamento interno.
O número de operações para encontrar um elemento é dado por:
- no caso de sucesso (hit): $\frac{1}{2}\left(1+\frac{1}{1-\alpha}\right)$
- no caso de insucesso (miss): $\frac{1}{2}\left(1+\frac{1}{(1-\alpha)^2}\right)$
Notar que o número de operações cresce rapidamente quando $\alpha \rightarrow 1$:
| $\alpha$ | 0.5 | 0.667 | 0.75 | 0.9 |
|---|---|---|---|---|
| hit | 1.5 | 2.0 | 3.0 | 5.5 |
| miss | 2.5 | 5.0 | 8.5 | 55.5 |
Exercício
Considere a seguinte função de dispersão:
int hash(int value, int M) {
return value % M;
}Dada uma tabela de dispersão com resolução de colisões por encadeamento linear (linear probing) para guardar elementos com as seguintes chaves
int w[8] = {13, 11, 10, 2, 22, 34, 45, 1};e a função de dispersão definida em cima, em que M = 10, qual é o índice da entrada da tabela do último elemento? E qual é a distribuição das chaves na tabela se removermos o elemento 22?
Resolução por double hashing
Neste caso guardamos os elementos numa tabela tal como no caso anterior, mas utilizamos outra técnica para resolver colisões. Em vez de procurar em sequência, utiliza-se uma segunda função de dispersão para determinar o incremento, que deve ser maior que 0 e primo relativamente ao tamanho da tabela. Esta técnica permite diminuir o número de operações relativamente à procura linear, em que as operações de inserção e procura só se tornam demasiado lentas quando o factor de carga, ou taxa de ocupação, atinge um valor de 90% a 95%.
Implementação
void STinsert(Item item) {
Key v = key(item);
int i = hash(v, M);
int k = hashtwo(v, M);
while (!null(i)) i = (i+k) % M;
st[i] = item; N++;
}
Item STsearch(Key v) {
int i = hash(v, M);
int k = hashtwo(v, M);
while (!null(i))
if eq(v, key(st[i])) return st[i];
else i = (i+k) % M;
return NULLitem;
}Análise
Tal como no caso anterior, a taxa de ocupação $\alpha = \frac{N}{M}$ tem de ser menor do que $1$.
O número de operações para encontrar um elemento é dado por:
- no caso de sucesso (hit): $\frac{1}{\alpha} \log\left(\frac{1}{1-\alpha}\right)$
- no caso de insucesso (miss): $\frac{1}{1-\alpha}$
Notar que o número de operações continua crescer quando $\alpha \rightarrow 1$, mas de forma bastante mais lenta do que no caso anterior:
| $\alpha$ | 0.5 | 0.667 | 0.75 | 0.9 |
|---|---|---|---|---|
| hit | 1.4 | 1.6 | 2.8 | 2.6 |
| miss | 1.5 | 2.0 | 3.0 | 5.5 |
Tabelas de dispersão dinâmicas
Quando a carga da tabela aumenta, o custo de inserção e procura aumenta também como vimos. Ainda que em tabelas esparsas ou em tabelas com encadeamento externo o aumento seja gradual, quando temos uma tabela não esparsa o aumento é incomportável. Este facto tem particular relevância quando utilizamos encadeamento interno, como no caso da procura linear ou da dispersão dupla, uma ver que a carga da tabela de dispersão pode ser no máximo 1. tabela esparsa (ou encadeamento externo) - aumento é gradual
A solução para resolver o problema passa por duplicar o tamanho da tabela quando a carga da mesma atinge valores de carga elevados. Como vimos este valor limite depende da estratégia utilizada na resolução de conflitos, no caso da dispersão dupla podemos admitir valores de carga superiores em comparação com a procura linear.
Notar no entanto que, em geral e ainda que seja pouco frequente, a expansão de uma tabela de dispersão tem um custo elevado, uma vez que é necessário reintroduzir todos os elementos de novo na tabela de dispersão após a duplicação da mesma.
Solução dinâmica com procura linear:
void expand();
void STinsert(Item item) {
Key v = key(item);
int i = hash(v, M);
while (!null(i))
i = (i+1) % M;
st[i] = item;
if (N++ > M/2)
expand();
}
void expand() {
int i;
Item *t = st;
init(M+M);
for (i = 0; i < M/2; i++)
if (key(t[i]) != key(NULLitem))
STinsert(t[i]);
free(t);
}Notas finais
Vantagens:
- concretizam operações de inserção e procura em tempo constante (caso médio);
- procura linear permite operações mais rápidas (tabela esparsa);
- dispersão dupla garante um melhor compromisso entre tempo e memória;
- encadeamento externo é mais fácil de concretizar, admite maior carga, mas é pior no uso de memória.
Inconvenientes:
- não há garantia de desempenho (embora se consigam derivar limites probabilísticos que nos dão alguma confiança);
- o custo de calcular uma função de dispersão pode ser alto se as chaves forem longas;
- as tabelas de dispersão podem ocupar mais memória do que o necessário;
- as tabelas de dispersão não suportam eficientemente as operações de ordenação e selecção.