Pesquisa em memória
primária: hashing
Algoritmos e Estruturas de Dados II
Hashing Dinâmico

Lembre que hashing tem tempo O(1) em média só se
M = cN

Se N crescer demais, esta condição será violada e a
performance será afetada
2
Hashing Dinâmico

A solução é aumentar o tamanho da tabela por um
fator f > 1 e fazer um rehashing dos elementos
sempre que o fator de carga ultrapassar um limiar

Se a tabela aumenta por uma porcentagem fixa, é
possível mostrar que o tempo necessário para
redimensionamento, distribuído sobre as operações
de inserção, é uma constante
3
Hashing Dinâmico
void expande(TipoPesos p, TipoDicionario T) {
T2 = NovoHeap(f * 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 */
4
Hashing Dinâmico: Análise

Considere a inserção de N elementos

Os redimensionamentos ocorreram quando tínhamos
N/f, N/f2, N/f3... Elementos

O custo gasto no total foi N(1/f +1/f2 + ...), que
converge para N(f/(f-1))

Assim, para inserir N elementos, gastamos cN
operações no total, portanto o custo de inserção de
cada elemento foi constante na média
5
Hashing Duplo

Mecanismo para resolução de colisão

Endereçamento aberto apresenta o efeito de
agrupamento

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 é utilizada
Elementos inicialmente endereçados no mesmo local
terão diferentes sequências de tentativas de inserção
6
Hashing Duplo
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 */
}
7
Hashing Universal

Para qualquer função de transformação h, de modo geral,
existe um conjunto de N chaves que serão todas
mapeadas na mesma posição da tabela

Idéia: criar h com a introdução de elementos aleatórios

Toda vez que o algoritmo for executado para um
conjunto de inserções S, teremos uma função h diferente,
o que distribui o custo de um eventual pior caso

O valor esperado de colisões será de no máximo N/M
8
Hashing Universal

Uma família H de funções hashing é universal se para
quaisquer duas chaves, a probabilidade de colisão
entre as duas é de no máximo 1/M quando a função
for escolhida aleatoriamente em H

Se H for universal, o valor esperado de colisões entre
uma chave qualquer do conjunto de possíveis chaves
e chaves de um conjunto S de N chaves, para h’s
escolhidas aleatoriamente em H é de no máximo
N/M
9
Hashing Universal

Considere que as chaves têm u bits

Considere que o tamanho da tabela é uma potência
de 2, de maneira que os índices da tabela têm b bits e
M = 2^b

Gere aleatoriamente uma matriz b x u de 0’s e 1’s

h(x) será dado por Ax mod 2
10
Hashing Universal – Exemplo
11
Hashing Perfeito

Dado um conjunto fixo S de N elementos

Uma função de espalhamento h é perfeita se
h(xi) ≠ h(xj) para todo i ≠ j em S
Desta maneira, não haverá colisões de chaves.


h é perfeita mínima se mapeia os elementos de S nos
inteiros {0,...,N-1}
12
Hashing Perfeito – Estratégia 1

Crie uma tabela com M = N^2 entradas, retire uma
função h aleatoriamente de H

Existe 50% de chances de ser uma função perfeita!
13
Hashing Perfeito – Estratégia 2

Crie uma tabela de tamanho N

Sorteie uma função h aleatoriamente em H

Para cada posição i de T, crie um hash perfeito Ti
utilizando a estratégia 1, seja hi a função de
mapeamento daquele hash

Seja yi o número de elementos mapeados na posição i
de T, o hash Ti terá yi2 posições

Para acessar x, computamos i = h(x), depois Ti [hi (x)]
14
Hashing Perfeito – Estratégia 2
2 =
(𝑦
)
𝑖 𝑖

Existe uma grande probabilidade de que
𝑂 𝑁

Isto é, dado h sorteado aleatoriamente de um
conjunto universal H, a probabilidade de que 𝑖(𝑦𝑖 )2
seja maior que 4N é menor que 50%

Portanto, este método gasta O(N) de memória
15
Exercícios

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.
16