Hashing

• Teoricamente, técnicas de hashing permitem acesso dinâmico aos dados (inserção/remoção/recuperação) numa complexidade que independe do número N de registros do arquivo O(1)

Hashing estático

- para arquivos que não variam de tamanho

Função de hashing

• Função que gera um endereço aleatório a partir de uma dada chave.

• Duas chaves podem definir dois endereços idênticos COLISÃO

h(k)h(k)

chavek = Adão

Registros

Adãoendereço 4

0

1

2

3

4

5

6

Exemplo simples

• 75 registros de nomes de pessoas devem ser armazenados num espaçode memória disponível para 1000 destes registros

função: transforme os dois primeiros caracteres dos nomes em inteiros, relativos a sua posição na tabela ASCII, multiplique estes valores e utilize os três dígitos menos significativos como endereço.

Nome ASCII das duas Produto Endereçoprimeiras letras

---------------------------------------------------------------------------------------------------------------BALL 66 65 66x65=4290 290LOWELL 76 79 76x79=6004 004TREE 84 82 84x82=6888 888

Colisões

• Funções de hashing devem gerar poucas colisões

Algumas ideias:

• distribuir o máximo possível os registros a serem armazenados, no arquivo, de tal formaque dois ou mais registros não sejam atribuídos a um mesmo endereço.

• considerar uma grande quantidade de espaço disponível (memória) em relação aonúmero de registros a serem armazenados (perda de espaço!!)

• associar mais de um registro a um único endereço (buckets)

Exemplo de um algoritmo de hashing

1. represente a chave numericamente2. subdivida-a e adicione os diferentes subconjuntos3. divida o resultado por um número primo (distribuição mais aleatória do resto) e use o resto da divisão como endereço.

Para LOWELL:

1. L O W E L L _ _ _ _ _ _ 76 79 87 69 76 76 32 32 32 32 32 32

2. | 76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32 | 7679 + 8769 + 7676 + 3232 + 3232 + 3232 = 33820

Para limitar o resultado a um valor máximo, x, e inserir mais aleatoriedade, podemos utilizar o operador mod:

Ex.: x = 19937 número primo distribuição mais aleatória do resto da divisão

Assim:

7679 + 8769 = 16448; 16448 mod 19937 = 1644816448 + 7676 = 24128; 24128 mod 19937 = 41874187+ 3232 = 7419; 7419 mod 19937 = 74197419 + 3232 = 10651; 10651 mod 19937 = 1065110651 + 3232 = 13883; 13883 mod 19937 = 13883

3. Objetivo: limitar a faixa de endereço resultante ao número de endereços disponíveis.

Seja s a soma obtida no passo 2 anterior e n o número de endereços disponíveis noarquivo. O endereço resultante, a, pode ser dado por:

a = s mod nque gera um valor entre 0 e n-1

Assim:

arquivo com 75 registros e n=101 endereços disponíveis: n = 101 primo !!!s = 13883 (LOWELL)

a = 13883 mod 101 = 84

75/101 = 0,743 = 74% do espaço utilizado84 LOWELL

int hash(char *v, int M) { int h = 0, a = 127 ; for (; *v != ‘\0’; v++) h = (a*h + *v) % M ; return ;}

Números primos e função de hashing

Funções de Hashing

abcdefg

12345678910

abcdefg

abcdefg

12345678910

12345678910

ideal (uniforme) ruim aceitável

Mais exemplos de funções

• “Mid-square”: transforma a chave num grande número decimal, eleva-oao quadrado e extrai dígitos do meio desta representação, proporcional aonúmero de casas decimais do maior endereço disponível

Ex.: endereços entre 0-99 chave = 341, 2chave = 116281

endereço da chave = 62

• Transformação de base: converte a representação numérica decimal dachave para outra base; calcula o mod deste resultado com o máximo ende-reço disponível.

Ex.: Endereços entre 0 – 99

453 chave10

382chave11 382 mod 100 = 82

)3( 0113

)8( 31141

)2( 4111453

resto

resto

resto

Conversão para a base 11:

Análise da distribuição dos registros no arquivo

• Calcula as diversas probabilidades de distribuição dos registros nos endereçosdisponíveis

• Baseia-se na distribuição de Poisson

!

)/()(

)/(

x

eNrxp

Nrx

Função de Poisson

!

)/()(

)/(

x

eNrxp

Nrx

Função de Poisson

N = número de endereços disponíveis

r = número total de registros a serem armazenados

x = número de registros atribuídos a um dado endereço

p(x) = probabilidade de a um dado endereço serem atribuídos x registros

com uma função de hashing sobre r registros.

Exemplo:

N = 1000 endereços disponíveis r = 1000 registros a serem armazenados

colisões) de adeprobabilid (grande 1N

r

• Probabilidade de um dado endereço receber x = 0 registro:

%79,363679,0!0

1)0(

10

e

p

• Probabilidade de um endereço receber x = 1 registro:

%79,363679,0!1

1)1(

11

e

p

• Probabilidade de um endereço receber x = 2 registros:

%4,18184,0!2

1)2(

12

e

p

• Probabilidade de um endereço receber x = 3 registros:

%1,6061,0!3

1)3(

13

e

p

Predições de colisão

Pela teoria das probabilidades temos que, para N endereços disponíveis,o número de endereços do arquivo contendo x registros é dado por:

)(xpN

Assim, para

N = r = 1000 r/N = 1

Podemos estimar o número de endereços com:

• x = 0 registro: 1000 x p(0) = 367,9 endereço sem registros

• x = 1 registro: 1000 x p(1) = 367,9 nenhuma colisão

• x = 2 registros: 1000 x p(2) = 183,9 183,9 registros com um sinônimo

• x = 3 registros: 1000 X p(3) = 61,3 61,3 registros com 2 sinônimos

(2 x 61,3 = 122,6 overflows)

Problema: Reduzir o número de colisões e tratar os casos de overflow !!

- Redução do número de colisões:

• boa função de hashing• uso de endereços extras

- Fator de carga D:

N

rD

sdisponívei endereços de número

registros de número

Exemplo:

%505.01000

500

N

rdo espaço utilizado no arquivo

Questões:

1- Para este fator de carga, quantos endereços ficarão sem registrosassociados?

607607.01000!0

)5.0(1000)0(

5.00

e

pN

2- Quantos endereços devem receber exatamente 1 registro?

303303.01000!1

)5.0(1000)1(

5.01

e

pN

3- Quantos endereços devem receber um registro mais um ou maissinônimos?

] ...)5()4()3()2([ ppppN0

= 1000[0.0758 + 0.0126 + 0.0016 + 0.002 + 0] = 90= 1000 – [607 + 303] = 90

4- Considerando-se apenas um registro/endereço, quantos overflows ocorrem no arquivo?

p(2) 1 overflowp(3) 2 overflowp(4) 3 overflows...

Nx1xp(2) + Nx2xp(3) + Nx3xp(4) + Nx4xp(5) + … = 1000 x [1x0.0758 + 2x0.0126 + 3x.0016 + 4x0.0002 + 0]= 107 overflows

5- Qual a porcentagem de overflows?

%4,21214,0500

107

Conclusão: Para um fator de carga igual a 50%, e cada endereço comum único registro, podemos obter 21% de todos os registros originandocolisões no arquivo.

Fator de carga (%) % de sinônimos10 4.820 9.430 13.640 17.650 21.460 24.870 28.180 31.290 34.1

100 36.8

Relação entre fator de carga e overflows

Redução de colisões por overflow progressivo

• Em casos de overflows, a lista de endereços é percorrida sequen-cialmente, até que uma área livre seja encontrada. Esta área repre-senta o endereço destino do registro.

NovakRosen

Jasper

Moreley

YORK

hash(YORK)

York

Procurando um registro que não existe:

Jello

.

.

.hash(Blue)

Blue

área vázia Blue não existeno arquivo

Se arquivo cheio, a busca sequencial retorna ao ponto de partida (ciclo completo) a busca se torna inviável!

Número Médio de Busca (NMB)

registros de totalnúmero

busca de totalnúmeroNMB

Chave Endereço

Adams 20

Bates 21

Cole 21

Dean 22

Evans 20

Exemplo:

Chave Endereço

Adams 20

Bates 21

Cole 21

Dean 22

Evans 20

Adams

Bates

Cole

Dean

Evans

20

21

22

23

24

número de busca

1

1

2

2

5

2.25

52211

NMB

NMB versus fator de carga para uma função de hashing com um registro porendereço e overflow progressivo empregado no caso de colisões

Fator de carga D

NMB

Abordagem de colisões por buckets

• Buckets: conjunto de registros associado a um mesmo endereço.

Green 30Hall 30Jenks 32King 33Land 33Marx 33Nutt 33

chave endereço

Green Hall

Jenks

King Land Marks

30

31

32

33Nutt é umoverflow

cada endereço pode conter 3 registros

Densidade de armazenamento por buckets

• Considera o número de endereços, N, e o número de registros,b, possíveis de serem armazenados em cada endereço (tamanho dosbuckets):

bN

rDB

Ex.:

r = 750N = 1000b = 1 750/1000 = 75%

r = 750N = 500b = 2 750/1000 = 75%

r/N = 0.75 r/N = 1.5

p(x) Sem buckets Com buckets(r/N=0.75) (r/N=1.5)

p(0) 0.472 0.223p(1) 0.354 0.335p(2) 0.133 0.251p(3) 0.033 0.126p(4) 0.006 0.047p(5) 0.001 0.014p(6) -- 0.004p(7) -- 0.001

Distribuição de Poisson para os dois tipos de arquivos

p(x) Sem buckets Com buckets(r/N=0.75) (r/N=1.5)

p(0) 0.472 0.223p(1) 0.354 0.335p(2) 0.133 0.251p(3) 0.033 0.126p(4) 0.006 0.047p(5) 0.001 0.014p(6) -- 0.004p(7) -- 0.001

Comparação de performance:

• Para o caso de b=1, r/N=0.75 e N = 1000, o número de overflows é:

1000 x [1xp(2) + 2xp(3) + 3xp(4) + 4xp(5) + 0 ] = 222 registros de overflow

222/750 = 29,6% de overflows

• Para o caso de b = 2, r/N = 1.5 e N = 500, o número de overflows é:

500 x [ 1xp(3) + 2xp(4) + 3xp(5) + 4xp(6) + 0 ] = 140 registros de overflow

140/750 = 18,7% de overflows

Fator decarga

Tamanho do bucket

Porcentagem de overflows

Overflow de registros em função de diferentes tamanhos de bucketse fator de carga

Supressão de registros

• a supressão não deve comprometer novas buscas.

• o espaço liberado deve poder ser reutilizado, por exemplo, no caso de um overflow progressivo

chaves hash(chaves) End. real

Adams 5 5Jones 6 6Morris 6 7Smith 5 8

Adams

Jones

Morris

Smith

4

5

6

7

8

chaves hash(chaves) End. real

Adams 5 5Jones 6 6Morris 6 7Smith 5 8

Adams

Jones

Morris

Smith

4

5

6

7

8

Apagando-se Morris

Adams

Jones

Smith

4

5

6

7

8

Smith está no arquivo?

Adams

Jones

########

Smith

4

5

6

7

8

observe que Smith não se encontra na melhor posição

após a supressão

Overflow progressivo encadeado

• Os sinônimos são encadeados a partir de apontadores

cada endereço contém um apontador para o próximo registro de

mesmo endereço

- vantagem: apenas os sinônimos são acessados numa determinada busca.

- desvantagem: temos campo de apontadores a mais; é preciso garantir a

busca correta aos sinônimos a partir do primeiro registro.

Exemplo 1: Overflow progressivo

Adams 20 20 1Bates 21 21 1Cole 20 22 3Dean 21 23 3Evans 24 24 1Flint 20 25 6

Chave hash(chave) End. real Comprimento de busca

NMB = (1 + 1 + 3 + 3 + 1 + 6)/6 = 2.5

- Overflow progressivo encadeadoAdams 22

Bates 23

Cole 25

Dean -1

Evans -1

Flint -1

20

21

22

23

24

25

NMB = (1 + 1 + 2 + 2 + 1 + 3)/6 = 1.7

Adams 20 Bates 21 Cole 20 Dean 22 Evans 24 Flint 20

Chave hash(chave)

- Overflow progressivo encadeadoAdams 22

Bates -1

Cole

Dean -1

Evans -1

Flint -1

20

21

22

23

24

25

Exemplo 2:

?

Área separada de overflow

• Objetivo: evitar que registros de overflow ocupem endereços errados.

Assim:

- área principal de dados contém registros com endereços “corretos”.

- área de overflow contém registros de overflows.

• Vantagens: os endereços da área principal de dados ficam livres para as novas adições de registros; o espaço no arquivo de overflow é alocado quando necessário; o processamento é simplificado

• Desvantagem: se overflow encontra-se em outro cilindro no disco maior tempode seek

Adams 0

Bates 1

Evans -1

20

21

22

23

24

Adams 20 Bates 21 Cole 20 Dean 21 Evans 24 Flint 20

Chave hash(chave)

Exemplo:

Cole 2

Dean -1

Flint -1

0

1

2

3

NMB = (1 + 1 + 2 + 2 + 1 + 3)/6 = 1.7

Tabela de Índices

• ideia: definir uma função de hashing que consulte um arquivo (tabela)de índices apontando para registros.

- Vantagem: a consulta aos índices se dá num único passo.

- Desvantagem: necessita de um acesso a mais na estrutura de hashing

h(K)

K

20

21

22

23

24

25

Adams Cole Flint -1

Bates Dean -1

Evans -1

Análise da frequência de aparição dos dados

• Baseia-se na frequência de ocorrência das chaves para decidir

quais devem ser armazenadas inicialmente no arquivo (aquelas de

maior fdp).

Bibliografia:

-- Michael J. Folk e Bill Zoellick. File Structures, Adisson-Wesley, 1992