175
Hashing Letícia Rodrigues Bueno UFABC

Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

  • Upload
    others

  • View
    2

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing

Letícia Rodrigues Bueno

UFABC

Page 2: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:

Page 3: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:

Page 4: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:1. fazer picadinho (de carne e vegetais);

Page 5: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:1. fazer picadinho (de carne e vegetais);2. fazer bagunça;

Page 6: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:1. fazer picadinho (de carne e vegetais);2. fazer bagunça;

• Através de uma função h(x), chave x é transformada emum endereço de uma tabela;

Page 7: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:1. fazer picadinho (de carne e vegetais);2. fazer bagunça;

• Através de uma função h(x), chave x é transformada emum endereço de uma tabela;

• Objetivo : atingir diretamente o local onde chave está;

Page 8: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:1. fazer picadinho (de carne e vegetais);2. fazer bagunça;

• Através de uma função h(x), chave x é transformada emum endereço de uma tabela;

• Objetivo : atingir diretamente o local onde chave está;

• Complexidade média por operação: O(1);

Page 9: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:1. fazer picadinho (de carne e vegetais);2. fazer bagunça;

• Através de uma função h(x), chave x é transformada emum endereço de uma tabela;

• Objetivo : atingir diretamente o local onde chave está;

• Complexidade média por operação: O(1);

• Complexidade pior caso: O(n);

Page 10: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing (Tabelas de Dispersão): Introdução

• hash:1. fazer picadinho (de carne e vegetais);2. fazer bagunça;

• Através de uma função h(x), chave x é transformada emum endereço de uma tabela;

• Objetivo : atingir diretamente o local onde chave está;

• Complexidade média por operação: O(1);

• Complexidade pior caso: O(n);

• Analogia: distribuição de correspondência em escaninhosrotulados;

Page 11: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Definição

Page 12: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Definição

• n chaves armazenadas em tabela T sequencial dedimensão m no intervalo [0,m − 1];

Page 13: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Definição

• n chaves armazenadas em tabela T sequencial dedimensão m no intervalo [0,m − 1];

• Duas etapas:

Page 14: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Definição

• n chaves armazenadas em tabela T sequencial dedimensão m no intervalo [0,m − 1];

• Duas etapas:1. Calcular valor da função de transformação ou função

hashing ;

Page 15: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Definição

• n chaves armazenadas em tabela T sequencial dedimensão m no intervalo [0,m − 1];

• Duas etapas:1. Calcular valor da função de transformação ou função

hashing ;2. Lidar com colisões ;

Page 16: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Transformações sobre chaves são aritméticas, portanto:

Page 17: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Transformações sobre chaves são aritméticas, portanto:

Primeiro passo: transformar chaves não-numéricas emnúmeros:

Page 18: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Transformações sobre chaves são aritméticas, portanto:

Primeiro passo: transformar chaves não-numéricas emnúmeros:

n−1∑

i=0

chave[i]× p[i]

Page 19: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Transformações sobre chaves são aritméticas, portanto:

Primeiro passo: transformar chaves não-numéricas emnúmeros:

n−1∑

i=0

chave[i]× p[i]

onde chave[i] está em ASCII ou Unicode e p[i] é um peso.

Page 20: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Em C/C++:

Page 21: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Em C/C++:

1 void geraPesos(){2 for (int i = 0; i < n; i++)3 pesos[i] = rand() % m + 1;4 }

Page 22: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Em C/C++:

1 void geraPesos(){2 for (int i = 0; i < n; i++)3 pesos[i] = rand() % m + 1;4 }

Objetivo: chaves diferentes com mesmos caracteres terãopesos diferentes e levarão a funções hashing diferentes.

Page 23: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Em C/C++:

Page 24: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : transformação da chave

Em C/C++:

1 int h(char chave[ ]){2 int soma = 0;3 for (int i = 0; i < n; i++)4 soma += (unsigned int)chave[i] ∗ pesos[i];5 return soma % m;6 }

Page 25: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Acesso DiretoChave x é armazenada no compartimento x :

00

01

02

03

04

05

040502000301

Page 26: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Acesso DiretoChave x é armazenada no compartimento x :

00

01

07

03

04

05

040701000503

Pode ser utilizado quando n = m ou n < m mas m − n épequeno.

Page 27: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Colisões

Page 28: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Colisões

Para chaves x 6= y , obtemos h(x) = h(y):

Page 29: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Colisões

Para chaves x 6= y , obtemos h(x) = h(y):

60

96

59

1359966078

h(x)=x mod 5

0

1

2

3

4

Page 30: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Colisões

Para chaves x 6= y , obtemos h(x) = h(y):

60

96

59

1359966078

h(x)=x mod 5

0

1

2

3

4

Chaves x e y são sinônimas .

Page 31: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Função de Dispersão

Objetivos:

Page 32: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Função de Dispersão

Objetivos:• produzir número baixo de colisões;

Page 33: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Função de Dispersão

Objetivos:• produzir número baixo de colisões;

• ser facilmente computável: assume-se tempo O(1);

Page 34: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Função de Dispersão

Objetivos:• produzir número baixo de colisões;

• ser facilmente computável: assume-se tempo O(1);

• ser uniforme;

Page 35: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Função de Dispersão

Objetivos:• produzir número baixo de colisões;

• ser facilmente computável: assume-se tempo O(1);

• ser uniforme;

Função uniforme: mesma probabilidade para todoscompartimentos, ou seja, 1

m de h(x) acontecer.

Page 36: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Page 37: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)

Page 38: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

Page 39: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

• Se m par:

Page 40: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

• Se m par: x par

Page 41: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

• Se m par: x par⇒ h(x) par;

Page 42: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

• Se m par: x par⇒ h(x) par;

• Se m ímpar:

Page 43: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

• Se m par: x par⇒ h(x) par;

• Se m ímpar: x ímpar

Page 44: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

• Se m par: x par⇒ h(x) par;

• Se m ímpar: x ímpar⇒ h(x) ímpar;

Page 45: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: Método da divisão

Função: h(x) = x (mod m)Sobre a escolha de m:

• Se m par: x par⇒ h(x) par;

• Se m ímpar: x ímpar⇒ h(x) ímpar;

96803510

h(x)=x mod 2

0

1

66 10

5 3

80 96

Page 46: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

Page 47: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

• m é número primo não próximo a potência de 2;

Page 48: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

• m é número primo não próximo a potência de 2;• m não possui divisores primos menores que 20;

Page 49: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

• m é número primo não próximo a potência de 2;• m não possui divisores primos menores que 20;• se m = 2j : h(x) depende apenas últimos j dígitos de x ;

Page 50: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

• m é número primo não próximo a potência de 2;• m não possui divisores primos menores que 20;• se m = 2j : h(x) depende apenas últimos j dígitos de x ;

Inteiro Binário resto divisão por 23= 8

0 00000 01 00001 12 00010 23 00011 34 00100 45 00101 56 00110 67 00111 78 01000 09 01001 110 01010 211 01011 312 01100 413 01101 514 01110 615 01111 716 10000 0

Page 51: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

• m é número primo não próximo a potência de 2;• m não possui divisores primos menores que 20;• se m = 2j : h(x) depende apenas últimos j dígitos de x ;

Inteiro Binário resto divisão por 23= 8

0 00000 01 00001 12 00010 23 00011 34 00100 45 00101 56 00110 67 00111 78 01000 09 01001 110 01010 211 01011 312 01100 413 01101 514 01110 615 01111 716 10000 0

Page 52: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

Page 53: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

m primo:

Page 54: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Função de Dispersão: alguns critérios para escolha de m

m primo:

46

71

68

49

97

977168494644

44

h(x)=x mod 23

Page 55: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Page 56: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

• Tratamento de colisões é procedimento crítico e deve serrealizado com cuidado.

Page 57: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

• Tratamento de colisões é procedimento crítico e deve serrealizado com cuidado.

• Fator de carga: α = nm .

Page 58: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

• Tratamento de colisões é procedimento crítico e deve serrealizado com cuidado.

• Fator de carga: α = nm .

• Quanto menor o fator de carga, menos colisões.

Page 59: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

• Tratamento de colisões é procedimento crítico e deve serrealizado com cuidado.

• Fator de carga: α = nm .

• Quanto menor o fator de carga, menos colisões.

• Fator de carga pequeno não garante ausência de colisões.

Page 60: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

• Tratamento de colisões é procedimento crítico e deve serrealizado com cuidado.

• Fator de carga: α = nm .

• Quanto menor o fator de carga, menos colisões.

• Fator de carga pequeno não garante ausência de colisões.

• Paradoxo do aniversário (Feller): em grupo com 23 oumais pessoas juntas ao acaso, existe chance maior que50% de 2 pessoas fazerem aniversário no mesmo dia.

Page 61: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

• Tratamento de colisões é procedimento crítico e deve serrealizado com cuidado.

• Fator de carga: α = nm .

• Quanto menor o fator de carga, menos colisões.

• Fator de carga pequeno não garante ausência de colisões.

• Paradoxo do aniversário (Feller): em grupo com 23 oumais pessoas juntas ao acaso, existe chance maior que50% de 2 pessoas fazerem aniversário no mesmo dia.

• Em uma tabela hashing, isso significaria: α = 23365 = 0,063.

Page 62: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

• Tratamento de colisões é procedimento crítico e deve serrealizado com cuidado.

• Fator de carga: α = nm .

• Quanto menor o fator de carga, menos colisões.

• Fator de carga pequeno não garante ausência de colisões.

• Paradoxo do aniversário (Feller): em grupo com 23 oumais pessoas juntas ao acaso, existe chance maior que50% de 2 pessoas fazerem aniversário no mesmo dia.

• Em uma tabela hashing, isso significaria: α = 23365 = 0,063.

• Mesmo assim, há 50% de chance de ocorrer pelo menosuma colisão.

Page 63: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Page 64: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Algumas estratégias:

Page 65: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Algumas estratégias:1. Tratamento de Colisões por Encadeamento:

Page 66: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Algumas estratégias:1. Tratamento de Colisões por Encadeamento:

1.1 Exterior;

Page 67: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Algumas estratégias:1. Tratamento de Colisões por Encadeamento:

1.1 Exterior;1.2 Interior;

Page 68: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Algumas estratégias:1. Tratamento de Colisões por Encadeamento:

1.1 Exterior;1.2 Interior;

2. Tratamento de Colisões por Endereçamento Aberto:

Page 69: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Algumas estratégias:1. Tratamento de Colisões por Encadeamento:

1.1 Exterior;1.2 Interior;

2. Tratamento de Colisões por Endereçamento Aberto:2.1 Tentativa Linear;

Page 70: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Hashing : Tratamento de Colisões

Algumas estratégias:1. Tratamento de Colisões por Encadeamento:

1.1 Exterior;1.2 Interior;

2. Tratamento de Colisões por Endereçamento Aberto:2.1 Tentativa Linear;2.2 Tentativa Quadrática;

Page 71: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Exterior

Page 72: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Exterior

• Cada endereço-base mantém uma lista encadeada;

Page 73: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Exterior

• Cada endereço-base mantém uma lista encadeada;

96803510

h(x)=x mod 2

0

1

66 10

5 3

80 96

Page 74: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Exterior

• Cada endereço-base mantém uma lista encadeada;

96803510

h(x)=x mod 2

0

1

66 10

5 3

80 96

• chaves inseridas no final da lista que tem que serpercorrida para verificar se chave já não existe;

Page 75: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Exterior

• Cada endereço-base mantém uma lista encadeada;

96803510

h(x)=x mod 2

0

1

66 10

5 3

80 96

• chaves inseridas no final da lista que tem que serpercorrida para verificar se chave já não existe;

• se função hashing é uniforme, busca tem tempo O(1);

Page 76: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Exterior

• Cada endereço-base mantém uma lista encadeada;

96803510

h(x)=x mod 2

0

1

66 10

5 3

80 96

• chaves inseridas no final da lista que tem que serpercorrida para verificar se chave já não existe;

• se função hashing é uniforme, busca tem tempo O(1);

• lista encadeada pode ser implementada como árvore AVL;

Page 77: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Page 78: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

• Duas zonas na tabela com m = p + s:

Page 79: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

• Duas zonas na tabela com m = p + s:1. uma de endereços-base de tamanho p;

Page 80: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

• Duas zonas na tabela com m = p + s:1. uma de endereços-base de tamanho p;2. uma de sinônimos de tamanho s;

Page 81: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

• Duas zonas na tabela com m = p + s:1. uma de endereços-base de tamanho p;2. uma de sinônimos de tamanho s;

48

03

80

31

2031800348

20

0

1

2

3

4

5

6

p

sh(x)=x mod 4

Page 82: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Page 83: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Problemas:

Page 84: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Problemas:• possibilidade de falso overflow : zona de sinônimos

cheia e zona de endereços-base ainda com vazios;

Page 85: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Problemas:• possibilidade de falso overflow : zona de sinônimos

cheia e zona de endereços-base ainda com vazios;

• Para evitar falso overflow : aumentar zona de colisões;

Page 86: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Problemas:• possibilidade de falso overflow : zona de sinônimos

cheia e zona de endereços-base ainda com vazios;

• Para evitar falso overflow : aumentar zona de colisões;

• Aumentar zona de colisões: diminui eficiência da tabela;

Page 87: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Problemas:• possibilidade de falso overflow : zona de sinônimos

cheia e zona de endereços-base ainda com vazios;

• Para evitar falso overflow : aumentar zona de colisões;

• Aumentar zona de colisões: diminui eficiência da tabela;

• p = 1 e s = m − 1⇒

Page 88: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento Interior

Problemas:• possibilidade de falso overflow : zona de sinônimos

cheia e zona de endereços-base ainda com vazios;

• Para evitar falso overflow : aumentar zona de colisões;

• Aumentar zona de colisões: diminui eficiência da tabela;

• p = 1 e s = m − 1⇒ lista encadeada!!!

Page 89: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento InteriorOpção: não diferenciar duas zonas da tabela

Page 90: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento InteriorOpção: não diferenciar duas zonas da tabela• qualquer endereço pode ser de base ou de sinônimo;

Page 91: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento InteriorOpção: não diferenciar duas zonas da tabela• qualquer endereço pode ser de base ou de sinônimo;• Problema: colisões secundárias;

Page 92: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento InteriorOpção: não diferenciar duas zonas da tabela• qualquer endereço pode ser de base ou de sinônimo;• Problema: colisões secundárias;• Fusão de listas diferentes: diminuição de eficiência;

Page 93: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Encadeamento InteriorOpção: não diferenciar duas zonas da tabela• qualquer endereço pode ser de base ou de sinônimo;• Problema: colisões secundárias;• Fusão de listas diferentes: diminuição de eficiência;

28

19

70

14

1970143528

35

0

1

2

3

4

5

6h(x)=x mod 7

Page 94: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

Page 95: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

Page 96: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

• Sem uso de ponteiros;

Page 97: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

• Sem uso de ponteiros;

• Calcula próximo compartimento a ser examinado;

Page 98: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

• Sem uso de ponteiros;

• Calcula próximo compartimento a ser examinado;

• Busca com sucesso: termina quando encontra chave;

Page 99: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

• Sem uso de ponteiros;

• Calcula próximo compartimento a ser examinado;

• Busca com sucesso: termina quando encontra chave;

• Busca sem sucesso: termina quando encontracompartimento vazio ou exaure tabela;

Page 100: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

• Sem uso de ponteiros;

• Calcula próximo compartimento a ser examinado;

• Busca com sucesso: termina quando encontra chave;

• Busca sem sucesso: termina quando encontracompartimento vazio ou exaure tabela;

• Função hash : fornece m endereços-base h(x , k) parachave x e k = 0, . . . ,m − 1 tentativas;

Page 101: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

• Sem uso de ponteiros;

• Calcula próximo compartimento a ser examinado;

• Busca com sucesso: termina quando encontra chave;

• Busca sem sucesso: termina quando encontracompartimento vazio ou exaure tabela;

• Função hash : fornece m endereços-base h(x , k) parachave x e k = 0, . . . ,m − 1 tentativas;

• Endereço-base: h(x ,0);

Page 102: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

• Idéia: armazenar chaves sinônimas também na tabela;

• Sem uso de ponteiros;

• Calcula próximo compartimento a ser examinado;

• Busca com sucesso: termina quando encontra chave;

• Busca sem sucesso: termina quando encontracompartimento vazio ou exaure tabela;

• Função hash : fornece m endereços-base h(x , k) parachave x e k = 0, . . . ,m − 1 tentativas;

• Endereço-base: h(x ,0);

• Se colisão: h(x ,0), h(x ,1), h(x ,2), . . . ,h(x ,m − 1);

Page 103: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

Page 104: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

Busca por endereçamento aberto em pseudo-código:

Page 105: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Tratamento de Colisões: Endereçamento Aberto

Busca por endereçamento aberto em pseudo-código:

1 buscaAberto(x , end , a):2 a← 3; k ← 0;3 enquanto k < m faça4 end ← h(x , k);5 se (T [end ].chave = x) então6 a← 1;7 k ← m;8 senão se (T [end ].chave = null) então9 a← 2;

10 k ← m;11 senão k ← k + 1;

onde a = 1 indica chave localizada, a = 2 ou 3 indica chavenão localizada. Se a = 2, end indica posição livre

Page 106: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Page 107: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:

Page 108: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h′(x) + k) (mod m),0 ≤ k ≤ m − 1.

Page 109: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h′(x) + k) (mod m),0 ≤ k ≤ m − 1.

que é o mesmo que:

Page 110: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h′(x) + k) (mod m),0 ≤ k ≤ m − 1.

que é o mesmo que:

• h(x , k) = (h(x , k − 1) + 1) (mod m),0 ≤ k ≤ m − 1.

Page 111: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h′(x) + k) (mod m),0 ≤ k ≤ m − 1.

que é o mesmo que:

• h(x , k) = (h(x , k − 1) + 1) (mod m),0 ≤ k ≤ m − 1.

Exemplo:

Page 112: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h′(x) + k) (mod m),0 ≤ k ≤ m − 1.

que é o mesmo que:

• h(x , k) = (h(x , k − 1) + 1) (mod m),0 ≤ k ≤ m − 1.

Exemplo:

h(x , 0) = 1 = 1h(x , 1) = (h(x , 0) + 1) (mod m) = 2h(x , 2) = (h(x , 1) + 1) (mod m) = 3h(x , 3) = (h(x , 2) + 1) (mod m) = 4

... =... =

...

Page 113: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Page 114: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:

Page 115: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Desvantagem: agrupamento primário;

Page 116: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Desvantagem: agrupamento primário;

• Agrupamento primário: longos trechos consecutivos dememória ocupados;

Page 117: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Linear

Tentativa Linear:• Desvantagem: agrupamento primário;

• Agrupamento primário: longos trechos consecutivos dememória ocupados;

• quanto maior o agrupamento primário, maior probabilidadede aumentá-lo mais;

Page 118: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Page 119: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:

Page 120: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h(x , k − 1) + k) (mod m),0 < k < m.

Page 121: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h(x , k − 1) + k) (mod m),0 < k < m.

Exemplo:

Page 122: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:• Suponha endereço da chave x é h′(x), ou seja,

h′(x) = h(x ,0)

• h(x , k) = (h(x , k − 1) + k) (mod m),0 < k < m.

Exemplo:

h(x , 0) = 1 = 1h(x , 1) = (h(x , 0) + 1) (mod m) = 2h(x , 2) = (h(x , 1) + 2) (mod m) = 4h(x , 3) = (h(x , 2) + 3) (mod m) = 7h(x , 4) = (h(x , 3) + 4) (mod m) = 11h(x , 5) = (h(x , 4) + 5) (mod m) = 16

... =... =

...

Page 123: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Page 124: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:

Page 125: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:• evita agrupamentos primários;

Page 126: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:• evita agrupamentos primários;

• produz agrupamentos secundários;

Page 127: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Endereçamento Aberto: Tentativa Quadrática

Tentativa Quadrática:• evita agrupamentos primários;

• produz agrupamentos secundários;

• degradação produzida pelos agrupamentos secundáriosainda é menor que a produzida pelos agrupamentosprimários;

Page 128: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Conclusão

Page 129: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Conclusão

• Complexidade média por operação: O(1);

Page 130: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Conclusão

• Complexidade média por operação: O(1);

• Tabela hash é estrutura de dados que não permitearmazenar elementos repetidos;

Page 131: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Conclusão

• Complexidade média por operação: O(1);

• Tabela hash é estrutura de dados que não permitearmazenar elementos repetidos;

• Não permite recuperar elementos sequencialmente(ordenação);

Page 132: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Conclusão

• Complexidade média por operação: O(1);

• Tabela hash é estrutura de dados que não permitearmazenar elementos repetidos;

• Não permite recuperar elementos sequencialmente(ordenação);

• Não permite recuperar o elemento antecessor e sucessor;

Page 133: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Conclusão

• Complexidade média por operação: O(1);

• Tabela hash é estrutura de dados que não permitearmazenar elementos repetidos;

• Não permite recuperar elementos sequencialmente(ordenação);

• Não permite recuperar o elemento antecessor e sucessor;

• Para otimizar a função hash é necessário conhecer anatureza da chave a ser utilizada;

Page 134: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Conclusão

• Complexidade média por operação: O(1);

• Tabela hash é estrutura de dados que não permitearmazenar elementos repetidos;

• Não permite recuperar elementos sequencialmente(ordenação);

• Não permite recuperar o elemento antecessor e sucessor;

• Para otimizar a função hash é necessário conhecer anatureza da chave a ser utilizada;

• No pior caso, a ordem das operações pode ser O(n)quando todos elementos inseridos colidem.

Page 135: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

Page 136: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:

Page 137: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;

Page 138: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;

Page 139: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

Page 140: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:

Page 141: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:1. envio de dados com resultado da função hash;

Page 142: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:1. envio de dados com resultado da função hash;2. receptor calcula função hash sobre dados recebidos e

obtém novo resultado;

Page 143: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:1. envio de dados com resultado da função hash;2. receptor calcula função hash sobre dados recebidos e

obtém novo resultado;3. se resultados iguais, dados são iguais;

Page 144: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:1. envio de dados com resultado da função hash;2. receptor calcula função hash sobre dados recebidos e

obtém novo resultado;3. se resultados iguais, dados são iguais;4. se diferentes, novo download é feito;

Page 145: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:1. envio de dados com resultado da função hash;2. receptor calcula função hash sobre dados recebidos e

obtém novo resultado;3. se resultados iguais, dados são iguais;4. se diferentes, novo download é feito;

Exemplo: download imagem de disco do Linux;

Page 146: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:1. envio de dados com resultado da função hash;2. receptor calcula função hash sobre dados recebidos e

obtém novo resultado;3. se resultados iguais, dados são iguais;4. se diferentes, novo download é feito;

Exemplo: download imagem de disco do Linux;

• armazenamento de senhas com segurança: somenteresultado função hash é armazenado no servidor;

Page 147: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações

• busca de elementos em base de dados:• estruturas de dados em memória;• bancos de dados;• mecanismos de busca na Internet;

• verificação de integridade de dados grandes:1. envio de dados com resultado da função hash;2. receptor calcula função hash sobre dados recebidos e

obtém novo resultado;3. se resultados iguais, dados são iguais;4. se diferentes, novo download é feito;

Exemplo: download imagem de disco do Linux;

• armazenamento de senhas com segurança: somenteresultado função hash é armazenado no servidor;

• Exemplos de hash (criptográficos): MD5 e família SHA(SHA− 2, SHA− 256 e SHA− 512);

Page 148: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

Page 149: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

Page 150: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

Page 151: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

Page 152: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

Page 153: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

5. Google: desconsidera artigos (“um”, “uma”, “o”, “a”);

Page 154: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

5. Google: desconsidera artigos (“um”, “uma”, “o”, “a”);

6. Construção do índice: tabela hash;

Page 155: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

5. Google: desconsidera artigos (“um”, “uma”, “o”, “a”);

6. Construção do índice: tabela hash;

7. usa peso: expressa número ocorrências de palavra, ondeaparece (título, meta-tags, etc), se maiúscula, fonte, etc;

Page 156: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

5. Google: desconsidera artigos (“um”, “uma”, “o”, “a”);

6. Construção do índice: tabela hash;

7. usa peso: expressa número ocorrências de palavra, ondeaparece (título, meta-tags, etc), se maiúscula, fonte, etc;

Combinação de

Page 157: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

5. Google: desconsidera artigos (“um”, “uma”, “o”, “a”);

6. Construção do índice: tabela hash;

7. usa peso: expressa número ocorrências de palavra, ondeaparece (título, meta-tags, etc), se maiúscula, fonte, etc;

Combinação de indexação eficiente

Page 158: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

5. Google: desconsidera artigos (“um”, “uma”, “o”, “a”);

6. Construção do índice: tabela hash;

7. usa peso: expressa número ocorrências de palavra, ondeaparece (título, meta-tags, etc), se maiúscula, fonte, etc;

Combinação de indexação eficiente +

Page 159: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Aplicações: mecanismos de busca na Internet

1. spiders : constroem listas de palavras dos Web sites;

2. spiders começam busca em servidores mais utilizados epáginas populares;

3. spider começa busca em site popular, indexa suaspalavras (e onde encontrou) e segue por seus links;

4. atenção especial: meta-tags, títulos, subtítulos;

5. Google: desconsidera artigos (“um”, “uma”, “o”, “a”);

6. Construção do índice: tabela hash;

7. usa peso: expressa número ocorrências de palavra, ondeaparece (título, meta-tags, etc), se maiúscula, fonte, etc;

Combinação de indexação eficiente + armazenagem efetiva ;

Page 160: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

Page 161: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

1. Considere as técnicas de busca sequencial, busca bináriae busca baseada em hashing:

Page 162: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

1. Considere as técnicas de busca sequencial, busca bináriae busca baseada em hashing:1.1 Descreva as vantagens e desvantagens de cada uma

dessas técnicas, indicando em que situações você usariacada uma delas.

Page 163: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

1. Considere as técnicas de busca sequencial, busca bináriae busca baseada em hashing:1.1 Descreva as vantagens e desvantagens de cada uma

dessas técnicas, indicando em que situações você usariacada uma delas.

1.2 Qual é a eficiência de utilização da memória (relação entreo espaço necessário para dados e o espaço totalnecessário) para cada método?

Page 164: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

1. Considere as técnicas de busca sequencial, busca bináriae busca baseada em hashing:1.1 Descreva as vantagens e desvantagens de cada uma

dessas técnicas, indicando em que situações você usariacada uma delas.

1.2 Qual é a eficiência de utilização da memória (relação entreo espaço necessário para dados e o espaço totalnecessário) para cada método?

2. Quais as características de uma boa função hash?

Page 165: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

1. Considere as técnicas de busca sequencial, busca bináriae busca baseada em hashing:1.1 Descreva as vantagens e desvantagens de cada uma

dessas técnicas, indicando em que situações você usariacada uma delas.

1.2 Qual é a eficiência de utilização da memória (relação entreo espaço necessário para dados e o espaço totalnecessário) para cada método?

2. Quais as características de uma boa função hash?

3. Em que situações a tabela hash deve ser utilizada?

Page 166: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

Page 167: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

4. Descreva dois mecanismos diferentes para resolver oproblema de colisões de várias chaves em uma mesmaposição da tabela, destacando as vantagens edesvantagens de cada método.

Page 168: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

4. Descreva dois mecanismos diferentes para resolver oproblema de colisões de várias chaves em uma mesmaposição da tabela, destacando as vantagens edesvantagens de cada método.

5. Para um conjunto de n chaves x formada pelos n primeirosmúltiplos de 7, quantas colisões são obtidas para asfunções de dispersão abaixo?

Page 169: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

4. Descreva dois mecanismos diferentes para resolver oproblema de colisões de várias chaves em uma mesmaposição da tabela, destacando as vantagens edesvantagens de cada método.

5. Para um conjunto de n chaves x formada pelos n primeirosmúltiplos de 7, quantas colisões são obtidas para asfunções de dispersão abaixo?5.1 x (mod 7)

Page 170: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

4. Descreva dois mecanismos diferentes para resolver oproblema de colisões de várias chaves em uma mesmaposição da tabela, destacando as vantagens edesvantagens de cada método.

5. Para um conjunto de n chaves x formada pelos n primeirosmúltiplos de 7, quantas colisões são obtidas para asfunções de dispersão abaixo?5.1 x (mod 7)5.2 x (mod 14)

Page 171: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

4. Descreva dois mecanismos diferentes para resolver oproblema de colisões de várias chaves em uma mesmaposição da tabela, destacando as vantagens edesvantagens de cada método.

5. Para um conjunto de n chaves x formada pelos n primeirosmúltiplos de 7, quantas colisões são obtidas para asfunções de dispersão abaixo?5.1 x (mod 7)5.2 x (mod 14)5.3 x (mod 5)

Page 172: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

4. Descreva dois mecanismos diferentes para resolver oproblema de colisões de várias chaves em uma mesmaposição da tabela, destacando as vantagens edesvantagens de cada método.

5. Para um conjunto de n chaves x formada pelos n primeirosmúltiplos de 7, quantas colisões são obtidas para asfunções de dispersão abaixo?5.1 x (mod 7)5.2 x (mod 14)5.3 x (mod 5)

6. Descreva algoritmos de busca, inserção e remoção emuma tabela hash com tratamento de colisões porencadeamento exterior.

Page 173: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Exercícios

4. Descreva dois mecanismos diferentes para resolver oproblema de colisões de várias chaves em uma mesmaposição da tabela, destacando as vantagens edesvantagens de cada método.

5. Para um conjunto de n chaves x formada pelos n primeirosmúltiplos de 7, quantas colisões são obtidas para asfunções de dispersão abaixo?5.1 x (mod 7)5.2 x (mod 14)5.3 x (mod 5)

6. Descreva algoritmos de busca, inserção e remoção emuma tabela hash com tratamento de colisões porencadeamento exterior.

7. Descreva algoritmos de busca e inserção em uma tabelahash com tratamento de colisões por encadeamentointerior, supondo não-existência de exclusões.

Page 174: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Bibliografia

FRANKLIN, Curt. “How Internet Search Engines Work”. 27September 2000. HowStuffWorks.com.< http : //computer .howstuffworks.com/internet/basics/search−engine.htm > 14 October 2012.

SZWARCFITER, J. L. e MARKENZON, L. Estruturas de Dados eseus Algoritmos, LTC, 1994.

ZIVIANI, N. Projeto de Algoritmos: com implementações em Java eC++, 1a edição, Cengage Learning, 2009.

Page 175: Hashing - Universidade Federal do ABCprofessor.ufabc.edu.br/.../aed2/materiais/hashing.pdf · Hashing: Tratamento de Colisões •Tratamento de colisões é procedimento crítico

Perguntas?