54
Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Embed Size (px)

Citation preview

Page 1: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Organização e Recuperação da Informação - Hashing

Ednaldo Pizzolato

Page 2: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Proposta– Em lugar de organizarmos a tabela segundo o

valor relativo de cada chave em relação às demais, a tabela hash leva em conta somente seu valor absoluto, interpretado como um valor numérico. Através de uma função conveniente, a chave é transformada em um endereço de uma tabela.

Page 3: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Princípio de Funcionamento– Suponha que existam n chaves a serem

armazenadas em uma tabela T, seqüêncial e de dimensão m (i.e. [0..m-1]). Cada posição corresponde a um endereço e pode armazenar r nós distintos.

– Obs.: quando a tabela se encontra em memória, é comum que cada endereço armazene um único nó. Já quando a tabela está em disco a organização pode ser diferente.

Page 4: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Acesso Direto– Quando possuímos uma tabela de tamanho

m e o número de chaves é n, tal que n ≤ m e mais, cada chave x é armazenada na posição x da tabela, dizemos que x serve de índice para sua busca, e que o acesso à informação é direto.

Page 5: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

01 03 00 02 05 04

chaves

Tabela Problema ?

Page 6: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

01 03 00 02 05 04

chaves

Tabela

Como seria o armazenamentode chaves cujos valores esti-vessem entre 1 e 999999?

Page 7: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Função Hash– Nem sempre as chaves estão no intervalo

[0..m-1], mesmo sendo o número de chaves menor que m. Por isso, devemos transformar, de alguma forma, nossa chave x para um valor no intervalo [0..m-1]. A função h(x), qual que 0 ≤ h(x) ≤ m-1, responsável por esta transformação é chamada de função hash.

Page 8: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Colisão– Infelizmente, a função h(x) não pode garantir

injetividade... Isso significa que podem existir chaves x e y (onde x ≠ y), tal que h(x) = h(y). Este fenômeno é chamado colisão. Dizemos que x e y são sinônimas em relação a h.

Page 9: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Custo– Pelo fato de não conhecermos

profundamente a função h e, principalmente, não conhecermos previamente as chaves que serão inseridas em uma tabela, podemos apenas determinar limites inferiores e superiores para a complexidade da busca. Estes limites são O(1) (acesso direto) para o melhor caso, sendo o pior caso, porém O(n).

Page 10: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Propriedades da Função Hash– Produzir um número baixo de colisões;– Ser facilmente computável;– Ser uniforme (distribuição equilibrada de

probabilidade)

Page 11: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Caso 1 – Melhor caso.– A função hash é

perfeita.

A

B

C

D

E

F

G

1

2

3

4

5

6

7

8

9

10

Page 12: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Caso 2 – Pior caso.– A função hash

apresenta muitas colisões.

A

B

C

D

E

F

G

1

2

3

4

5

6

7

8

9

10

Page 13: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Caso 3 – Aceitável.– A função hash

apresenta algumas colisões.

A

B

C

D

E

F

G

1

2

3

4

5

6

7

8

9

10

Page 14: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Funções HASH– Método da divisão : divide-se a chave x pelo

tamanho da tabela e o resto da divisão é usado como endereço-base.

• H(x) = x % m

Page 15: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Funções HASH– Método da dobra (XOR) : Este método transforma uma

chave de k bits (2k > m) em uma chave de j elementos, tal que 2j ≤ m. Para isso pegamos os k/2 bits da esquerda e realizamos um XOR com os k/2 bits da direita, resultando em uma nova chave de k/s bits. Repetimos o processo até que a chave gerada tenha j bits.

Exemplo: m = 32, chaves de 10 bits (quanto vale j neste caso?)

71 = 00010 00111 00010 XOR 00111 = 00101 = 5

46 = 00001 01110 00001 XOR 01110 = 01111 = 15

Page 16: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Funções HASH– Método da análise de dígitos;– Método do meio do quadrado;

Page 17: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Tratamento de Colisão Como já vimos, anteriormente, é impossível

evitar que ocorram colisões. Um método para diminuir o número de colisões é diminuir o fator de carga da tabela, que é definido por

α = n/mEssa preocupação deve ser tomada quando o número de colisões cresce rapidamente quando o fator de carga aumenta. No entanto, tal providência não é suficiente.

Page 18: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Encadeamento exterior Cada endereço guarda um ponteiro para uma

lista (inicialmente vazia). Cada entrada é colocada na posição final da fila referente a seu endereço. Algoritmos de inserção, remoção e busca são semelhantes aos de uma lista comum.

Page 19: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Encadeamento exterior Custo médio de busca sem sucesso

m

nL

mCM

m

ii

1

1

Onde |Li| é o comprimento da fila i

Page 20: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Encadeamento exterior Custo médio de busca com sucesso

mnm

nn

m

j

nCM

n

j 2

1

21

2

)1(11

1 1

0

Page 21: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Encadeamento interior Em algumas aplicações, não é desejável a

manutenção de uma estrutura exterior à tabela hash. Neste caso podemos implementar listas encadeadas, desde que estas compartilhem o mesmo espaço de memória da tabela hash. Desta forma, dividimos a tabela T em uma área de endereços, de tamanho p, e uma área de sinônimos, de tamanho s (s+p = m). Assim, a função h deve gerar valores em [0..p-1] e n/m deve ser menor ou igual a 1. Problema ?

Page 22: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Encadeamento interior Em algumas aplicações, não é desejável a

manutenção de uma estrutura exterior à tabela hash. Neste caso podemos implementar listas encadeadas, desde que estas compartilhem o mesmo espaço de memória da tabela hash. Desta forma, dividimos a tabela T em uma área de endereços, de tamanho p, e uma área de sinônimos, de tamanho s (s+p = m). Assim, a função h deve gerar valores em [0..p-1] e n/m deve ser menor ou igual a 1. Overflow

Page 23: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Encadeamento interior Outra forma de utilizarmos o

encadeamento interno é através da não reserva de nenhuma área para sinônimos. Esta técnica elimina a ocorrência de overflow (uma vez que n/m < 1), mas produz um efeito indesejado que é a possibilidade de colisão de duas chaves x e y onde h(x) ≠ h(y). Este tipo de colisão é chamado de colisão secundária.

Page 24: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Remoção Outro problema sério em uma

tabela hash é a remoção de uma chave. Neste método, sentiremos ainda mais os efeitos da eliminação de uma chave da tabela. Notem que não podemos simplesmente abrir um buraco na lista encadeada, o que criaria problemas (quais?). Como resolver?

Page 25: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Endereçamento aberto Neste método, as colisões da tabela

não são encadeadas como no método de encadeamento interior... Não há ponteiros. Quando houver alguma colisão, determina-se, através de uma nova função, qual o próximo endereço a ser examinado. Desta forma, teremos uma função h que leva em conta qual tentativa estamos realizando:

h(x,k)onde k indica a k-ésima tentativa.

K = 0

Page 26: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Endereçamento aberto Para encontrar a chave x, deve-se

tentar o endereço-base h(x,0). Caso esteja ocupado por alguma outra chave, calcula-se o endereço h(x,1), e assim por diante, até que a chave seja encontrada ou h(x,k) aponte para uma posição vazia.

K = 1

Page 27: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Endereçamento aberto - remoção A remoção de chaves da tabela exige

cuidados especiais. No método do endereçamento aberto, a remoção apresenta um problema semelhante àquele do método do encadeamento interior. Uma chave não pode ser removida, de fato, da tabela, pois faria romper a seqüência de tentativas. A solução é semelhante à empregada no método anterior.

K = 2

Page 28: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Endereçamento aberto – tentativa linear A idéia consiste em tentar armazenar a nova chave x

no endereço-base h’(x). Se não for possível, tenta-se no endereço consecutivo h’(x) + 1. Se este já estiver ocupado, tenta-se h’(x) + 2... Até que uma posição vazia seja obtida ou ...(???) Lembre-se que devemos simular uma lista circular.

h(x,k) = (h’(x) + k) mod m

Problema : longos trechos consecutivos de memória ocupados, o que se denomina agrupamento primário.

Page 29: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Endereçamento aberto – tentativa quadrática A idéia consiste em se obter seqüências de endereços

distantes para endereços-base próximos. Para isso, utilizamos como incremento, uma função quadrática em k:

h(x,k) = (h’(x) + c1k + c2k2) mod m

Problema: Consegue evitar os agrupamentos primários da tentativa linear, mas não impede agrupamentos de chaves com mesma tentativa inicial. Os agrupamentos obtidos neste caso são chamados de secundários.

Page 30: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Endereçamento aberto – double hashing O método calcula a seqüência de tentativas, de

acordo com a seguinte equação:

h(x,k) = (h’(x) + k.h’’(x)) mod m

Esse método tende a distribuir as chaves na tabela de forma mais conveniente do que os dois anteriores. Se x e y são duas chaves distintas, tais que h’(x) = h’(y), então as seqüências de tentativas obtidas pelos métodos da tentativa linear e quadrática são necessariamente idênticas, o que ocasiona agrupamentos.

Page 31: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

Load

Factor

%

SUCESSO FRACASSO

Linear Quad Doubl Linear Quad Double

25 1.17 1.16 1.15 1.39 1.37 1.33

50 1.50 1.44 1.39 2.50 2.19 2.00

75 2.50 2.01 1.85 7.50 4.64 4.00

90 5.50 2.85 2.56 50.50 11.40 10.00

95 10.50 3.52 3.15 200.5 22.04 20.00

Page 32: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

Tam.

Tabela

SUCESSO FRACASSO

Linear Quad Double Linear

100 6.60 4.62 4.12 50.50

500 14.35 6.22 5.72 250.50

1000 20.15 6.91 6.41 500.50

5000 44.64 7.52 7.02 2500.50

10000 63.00 7.21 7.71 5000.50

Page 33: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Quando projetamos uma tabela hash, devemos ter

conhecimento estatístico prévio sobre alguns dados como:

a) prob. de um dado endereço não ser preenchido;

b) prob. de um dado endereço conter exatamente uma chave;

c) prob. de um dado endereço conter mais de uma chave.

Page 34: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática A probabilidade de um evento ocorrer exatamente x

vezes num total de r tentativas é dada por:

onde a é a probabilidade do evento ocorrer uma vez.

xrx aax

rxp

1..)(

Page 35: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Quando relacionamos este tipo de evento a endereços

em uma tabela hash, podemos dizer que a = 1/m, onde m é o tamanho da tabela. Desta forma, podemos calcular a probabilidade de um certo endereço conter x chaves em uma tabela com r chaves e tamanho m:

xrx

mmx

rxp

11.

1.)(

Page 36: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Entretanto, quando m e r são grandes, dizemso que

p(x) tende a:

Que é conhecida como distribuição de Poisson.

!

.)(

/

x

emr

xp

mrx

Page 37: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Exemplo: Suponhamos que existam 1000 endereços

(m=1000) e 500 chaves (r = 500). Se multiplicarmos 1000 pela probabilidade de um dado endereço conter x chaves associadas a si, teremos o valor esperado do número de endereços com x chaves (E(x)). Portanto, E(X) = m.p(x)

!

.)(

/

x

emr

xp

mrx

Page 38: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Com 1000 endereços

(m=1000) e 500 chaves (r = 500). Quantos endereços devem estar desocu-pados?

R.: 607

!

.)(

/

x

emr

xp

mrx

!0

.1000500

.1000)0(.1000

1000/5000

e

p

Page 39: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Com 1000 endereços (m=1000) e 500 chaves (r =

500). Quantos endereços devem ter exatamente uma chave associada a si?

R.: 303

!

.)(

/

x

emr

xp

mrx

!1

.1000500

.1000)1(.1000

1000/5001

e

p

Page 40: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Com 1000 endereços (m=1000) e 500 chaves (r =

500). Quantos endereços devem ter mais de uma chave associada a si?

R.: 90 m [p(20 + p(3) + ... +p(m)]

= m. (1 – [p(0)+p(1)]) = 90

!

.)(

/

x

emr

xp

mrx

!1

.1000500

.1000)1(.1000

1000/5001

e

p

Page 41: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Abordagem Matemática Com 1000 endereços (m=1000) e 500 chaves (r =

500). Assumindo uma chave por endereço, quanto de overflow pode ser esperado?

R.: 107 m [1.p(2) + 2.p(3) + ...]

O que indica 107 / 500 = 21.4%

Page 42: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Buckets para tabelas hash Na maioria das vezes, quando estamos

trabalhando com arquivos, o número de acessos ao disco é fator crítico ao invés do custo computacional. Além disso, sempre que recuperamos alguma informação do disco, não lemos apenas o número de bytes correspondentes à informação desejada, mas sim um bloco (ou mesmo um conjunto de blocos). O bucket é uma estrutura capas de armazenar o máximo de chaves que podem ser recuperadas com um único acesso a disco. Assim, cada endereço da tabela hash corresponderá a várias chaves.

Page 43: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Eficiência dos buckets Quando tínhamos 1 chave

por endereço, havíamos definido o fator de carga como sendo α = r / m, onde r é o número de chaves e m o tamanho da tabela. Agora, seja b o número de chaves por bucket:

mb

r

.

Page 44: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Eficiência dos buckets Quando armazenamos 750 chaves em

1.000 endereços de tamanho 1 temos:

75.01000

750

Page 45: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Eficiência dos buckets Quando armazenamos 750 chaves em

500 endereços de tamanho 2 temos:

75.01000

750

Page 46: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Eficiência dos buckets O cálculo do overflow para o caso 1 é:

m . [1.p(2) + 2.p(3) + 3.p(4) + ...] = 222

O mesmo cálculo para o caso 2 é

m. [1.p(3) + 2.p(4) + ...] = 140

Enquanto o primeiro caso obteve um valor esperado de 222 chaves em overflow (29,6%), o segundo caso obteve 140 chaves (18.6%). Buckets maiores diminuem ainda mais a porcentagem de overflow.

Page 47: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

HashingCarga

%

Tamanho do bucket

1 2 5 10 100

70 28.1 17.0 7.1 2.9 0.0

75 29.6 18.7 8.6 4.0 0.0

80 31.2 20.4 10.3 5.3 0.1

90 34.1 23.8 13.8 8.6 0.8

100 36.8 27.1 17.6 12.5 4.0

Page 48: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Extendible hashing Arquivos que crescem ou diminuem muito

rapidamente causam, em tabelas hash estáticas (como as que vimos até o presente momento), uma queda significativa de desempenho tanto pelo alto custo computacional gasto com overflow (tabelas pequenas) quanto pelo alto número de acessos a disco (tabelas maiores). O extendible hashing é um tipo de hashing dinâmico capaz de se ajustar a tabelas que crescem ou diminuem rapidamente, mantendo as características de acesso “direto” do hashing, sem perder desempenho (CPU e disco).

Page 49: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Extendible hashing Definição : No extendible hashing, cada valor de

h(x) é interpretado como uma seqüência de dígitos binários que servirão de índice para a busca da chave x. As chaves, por sua vez, serão armazenadas em buckets. Todas as chaves de um bucket possuem os i primeiros bits iguais, onde i é chamado de profundidade do bucket.

Page 50: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Exemplo Suponhamos que haja um bucket A, cuja função

h(x) tenha gerado valores iniciados pelos bits 01; um bucket B cujos bits iniciais sejam 10 e um bucket C com bits iniciais 11. Poderíamos representar esta situação em uma árvore como a seguinte:

A

B

C

0

1

0

1

Page 51: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Exemplo Entretanto, uma estrutura de árvore não pode

prover acesso “direto” que é o que desejamos. Desta forma, devemos mapear nossa “árvore” para uma outra árvore completa e depois, para um array, cujo acesso será direto:

A

B

C

0

1

0

1

00

01

10

11

Page 52: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Crescimento

00

01

10

11

A

B

C

Page 53: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Crescimento

00

01

10

11

A

B

C

D

Page 54: Organização e Recuperação da Informação - Hashing Ednaldo Pizzolato

Hashing

• Crescimento

00

01

10

11

A

B

C