Pesquisa em Memória Primária

Prof. Jonas Potros

Transformação de Chave (Hashing)

A transformação de chave difere-se dos métodos anteriores, porque osregistros são armazenados em uma tabela e são diretamenteendereçados a partir de uma transformação aritmética sobre a chavede pesquisa.

Um método de pesquisa com o uso da transformação de chave éconstituído de duas etapas principais:

1. Computar o valor da função de transformação ou função hashing, a qualtransforma a chave de pesquisa em um endereço da tabela.

2. Considerando que duas ou mais chaves podem ser transformadas em ummesmo endereço de tabela, é necessário existir um método para lidar comcolisões.

Transformação de Chave (Hashing)

Qualquer que seja a função de transformação, algumas colisões irãoocorrer fatalmente, e tais colisões têm de ser resolvidas de algumaforma.

Exemplo: Se por ventura as chaves fossem inteiras de 1 𝑎 𝑛, entãopoderíamos armazenar o registro com a chave 𝑖 na posição 𝑖 da tabela,e qualquer registro poderia ser imediatamente acessado e a partir dovalor da chave.

𝑏 = 0, 𝑙𝑜𝑔𝑜 𝐴[𝑏] = 0

A

[0] 0

[1] 1

[2] 2

Exemplo: Colisões

Vamos supor que uma tabela é capaz de armazenar 𝑀 = 97 chaves,em que cada chave pode ser um número decimal de quatro dígitos.Nesse caso, existe 𝑁 = 10.000 chaves possíveis, e a função detransformação não pode ser um para um, mesmo que o número deregistros a serem armazenados seja muito menor do que 97.

𝑏 = 0, 𝑙𝑜𝑔𝑜 𝐴[𝑏] ≠ 0

𝑥 = 1, 𝐴 1 = 2870, 𝑙𝑜𝑔𝑜 𝐴[𝑥] → 𝐴

A

[0] 1002

[1] 2870

[2] 8375

.... ....

[97] y

Qualquer que seja a função de transformação,algumas colisões irão ocorrer fatalmente, e taiscolisões têm de ser resolvidas de algumaforma.

Exemplo: Colisões

Vamos supor que uma tabela é capaz de armazenar 𝑀 = 97 chaves,em que cada chave pode ser um número decimal de quatro dígitos.Nesse caso, existe 𝑁 = 10.000 chaves possíveis, e a função detransformação não pode ser um para um, mesmo que o número deregistros a serem armazenados seja muito menor do que 97.

𝑏 = 0, 𝑙𝑜𝑔𝑜 𝐴[𝑏] ≠ 0

𝑥 = 1, 𝐴 1 = 2870, 𝑙𝑜𝑔𝑜 𝐴[𝑥] → 𝐴

A

[0] 1002

[1] 2870

[2] 8375

.... ....

[97] y

Mesmo que se obtenha uma função detransformação que distribua os registros deforma uniforme entre as entradas da tabela,existe uma alta probabilidade de havercolisões.

Funções de Transformação

Uma função de transformação deve mapear chaves em inteiros dentrodo intervalo [0. .𝑀 − 1], onde𝑀 é o tamanho da tabela.

A função de transformação ideal é aquela que:

1. Seja simples de ser computada.

2. Para cada chave de entrada, qualquer uma das saídas possíveis é igualmente provável de ocorrer.

Como as transformações sobre as chaves são aritméticas, deve-setransformar as chaves não-numéricas em números.

• Basta realizar uma conversão de cada caractere da chave não numérica paraum número inteiro.

Método mais usado

Usa o resto da divisão por M, onde K é um inteiro correspondente àchave:

ℎ(𝐾) = 𝐾 𝑚𝑜𝑑 𝑀

Cuidado na escolha do valor de M. M deve ser um número primo, masnão qualquer primo: devem ser evitados os números primos obtidos apartir de:

𝑏𝑖 ± 𝑗

onde 𝑏 é a base do conjunto de caracteres (geralmente 𝑏 = 64 paraBCD, 128 para ASCII, 256 para EBCDIC, ou 100 para alguns códigosdecimais), e 𝑖 e 𝑗 são pequenos inteiros.

Transformação de Chaves – não numéricas

As chaves não numéricas devem ser transformadas em números:

𝐾 =

𝑖=0

𝑛−1

𝑐ℎ𝑎𝑣𝑒 𝑖 × 𝑝[𝑖]

𝑛 é o número de caracteres da chave;

𝑐ℎ𝑎𝑣𝑒[𝑖] corresponde à representação ASCII ou Unicode do 𝑖 − é𝑠𝑖𝑚𝑜 caractere da chave;

𝑝[𝑖] é um inteiro de um conjunto de pesos gerados randomicamente para 0 ≤ 𝑖 ≤ 𝑛 − 1;

Vantagem de se usar pesos: Dois conjuntos diferentes de pesos 𝑝1[𝑖] e 𝑝2[𝑖], 0 ≤ 𝑖 ≤ 𝑛 − 1,

levam a duas funções de transformação ℎ1(𝐾) 𝑒 ℎ2(𝐾) diferentes;

Transformação de Chaves – não numéricas

Programa que gera um peso para cada caractere de uma chave constituída de n caracteres:

GeraPesos (int n) {

int p[n];

for (int i = 0; i < n; i ++) p[i] = random(M) + 1;

return p;

}

Transformação de Chaves – não numéricas

Implementação da função de transformação:

hashing (String chave, int[ ] pesos) {

int soma = 0;

for ( int i = 0; i < chave.length ( ) ; i++)

soma = soma + (chave(i)) ∗ pesos[ i ];

return soma mod M;

}

Listas Encadeadas

Uma das formas de resolver as colisões é simplesmente construir umalista linear encadeada para cada endereço da tabela.

• Assim, todas as chaves com mesmo endereço são encadeadas emuma lista linear.

Exemplo: Se a 𝑖 − é𝑠𝑖𝑚𝑎 letra do alfabeto é representada pelonúmero 𝑖 e a função de transformação:

ℎ(𝐶ℎ𝑎𝑣𝑒) = 𝐶ℎ𝑎𝑣𝑒 𝑚𝑜𝑑 𝑀

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

ℎ 𝑃 = ℎ 2 = 2

P

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5

S

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3

S

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3

S

Q

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0

S

Q

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0

S

Q

U

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0ℎ 𝐼 = ℎ 23 = 2

S

Q

U

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0ℎ 𝐼 = ℎ 23 = 2

S

Q

U

I

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0ℎ 𝐼 = ℎ 23 = 2ℎ 𝑆 = ℎ 47 = 5

S

Q

U

I

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0ℎ 𝐼 = ℎ 23 = 2ℎ 𝑆 = ℎ 47 = 5

S

Q

U

I

S

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0ℎ 𝐼 = ℎ 23 = 2ℎ 𝑆 = ℎ 47 = 5ℎ 𝐴 = ℎ 1 = 1S

Q

U

I

S

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E

ℎ 𝑃 = ℎ 2 = 2ℎ 𝐸 = ℎ 19 = 5ℎ 𝑆 = ℎ 5 = 5ℎ 𝑄 = ℎ 17 = 3ℎ 𝑈 = ℎ 7 = 0ℎ 𝐼 = ℎ 23 = 2ℎ 𝑆 = ℎ 47 = 5ℎ 𝐴 = ℎ 1 = 1S

Q

U

I

S

A

Exemplo: Listas Encadeadas

Inserção das chaves 𝑃 𝐸 𝑆 𝑄 𝑈 𝐼 𝑆 𝐴, sendo𝑀 = 7.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

P

E S

Q

U

I

S

A

nil

nil

nil

nil

nil

nil

nil

Endereçamento Aberto

Quando o número de registros a serem armazenados na tabela puderser previamente estimado, então não haverá necessidade de usar listasencadeadas para armazenar os registros.

Existem vários métodos para armazenar 𝑁 registros em uma tabela detamanho 𝑀 > 𝑁, os quais utilizam os lugares vazios na própria tabelapara resolver as colisões.

No Endereçamento aberto todas as chaves são armazenadas naprópria tabela, sem o uso de listas encadeadas em cada entrada dela.

Endereçamento Aberto

Existem várias propostas para a escolha de localizações alternativas. Amais simples é chamada de hashing linear, onde a posição ℎ𝑗 na tabelaé dada por:

ℎ𝑗 = (ℎ(𝑥) + 𝑗) 𝑚𝑜𝑑 𝑀, 𝑝𝑎𝑟𝑎 1 ≤ 𝑗 ≤ 𝑀 − 1.

Exemplo: Se a 𝑖 − é𝑠𝑖𝑚𝑎 letra do alfabeto é representada pelonúmero 𝑖 e a função de transformação:

ℎ(𝑐ℎ𝑎𝑣𝑒) = 𝑐ℎ𝑎𝑣𝑒 𝑚𝑜𝑑 𝑀

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0]

[1]

[2]

[3]

[4]

[5]

[6]

ℎ(𝐿) = ℎ(19) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0]

[1]

[2]

[3]

[4]

[5] L

[6]

ℎ(𝐿) = ℎ(19) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0]

[1]

[2]

[3]

[4]

[5] L

[6]

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1]

[2]

[3]

[4]

[5] L

[6]

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1]

[2]

[3]

[4]

[5] L

[6]

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2]

[3]

[4]

[5] L

[6]

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2]

[3]

[4]

[5] L

[6]

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2]

[3]

[4]

[5] L

[6]

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2]

[3]

[4]

[5] L

[6] E

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2]

[3]

[4]

[5] L

[6] E

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5ℎ(𝐸) = ℎ(19) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2]

[3]

[4]

[5] L

[6] E

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5ℎ(𝐸) = ℎ(19) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2] S

[3]

[4]

[5] L

[6] E

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5ℎ(𝑆) = ℎ(19) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2] E

[3]

[4]

[5] L

[6] E

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5ℎ(𝑆) = ℎ(19) = 5

Endereçamento Aberto

Inserção das chaves 𝐿 𝑈 𝑁 𝐸 𝑆 na tabela, usando hashing linear pararesolver colisões.

A

[0] U

[1] N

[2] E

[3]

[4]

[5] L

[6] E

ℎ 𝐿 = ℎ 19 = 5ℎ(𝑈) = ℎ(21) = 0ℎ(𝑁) = ℎ(14) = 0ℎ(𝐸) = ℎ(5) = 5ℎ(𝐸) = ℎ(19) = 5

Vantagens e Desvantagens

Vantagens:• Alta eficiência no custo de pesquisa, que é O(1) para o caso médio.

• Simplicidade de implementação.

Desvantagens:• Custo para recuperar os registros na ordem lexicográfica das chaves é alto;

• Pior caso é O(N).

Atividade

Apresente a implementação da função hashing, de modo a tratar ascolisões pelos dois métodos: Listas Encadeadas e Endereçamento Aberto.