Hash Tables

Prévia do material em texto

Hash Tables
“Tabelas de Espalhamento”
Estruturas de Dados
Prof. Vilson Heck Junior
Hash Table
• Como Estrutura de Dados:
– Serve para organizar e armazenar dados
de forma a agilizar o processo de
pesquisa;
– Pode ser programada de diversas
formas, sendo a mais comum com o uso
de array e listas dinâmicas.
Tabela Hash
• Usos mais comuns:
– Indexação de grandes volumes de 
informação;
– Classificação por categorias;
– Softwares per-to-per (BitTorrent);
– Entre outros.
Tabela Hash
• São elementos compositores:
– Função Hash (Função de 
espalhamento);
– Chaves de Pesquisa;
– Índices Hash;
– Array de informações ou de listas de 
informações.
Função Hash
• Responsável pelo “espalhamento”
(distribuição) dos dados, através da geração
do índice do elemento com base em uma
determinada chave e operação matemática;
• O desempenho da tabela, como um todo, é
completamente dependente do
planejamento desta função;
• Quanto menos colisões ocorrerem, melhor é
a função Hash escolhida, e melhor o
desempenho da tabela como um todo.
Função Hash
• Exemplo de Função Hash (1):
– Supondo que queremos dividir todos os
nomes de pessoas em um determinado
cadastro pela primeira letra (maiúscula)
do nome:
public int FuncaoHash(String chave) {
return chave.toUpperCase().charAt(0) – 65;
}
Função Hash
• Exemplo de Função Hash (2):
– Supondo que queremos dividir todos os
CPFs de pessoas em um determinado
cadastro de 100 em 100 registros:
public int FuncaoHash(long chave) {
return (int)(chave % 100);
}
Chave Hash
• É o valor que será utilizado pela
fórmula Hash para o espalhamento
dos dados;
• Como no exemplo anterior, a chave
utilizada como parâmetro da função,
nada mais é do que uma string
contendo o nome que se pretende
espalhar separando pela primeira
letra do nome.
Índice Hash
• Índice é o valor que é retornado pela
função Hash;
• É um número que representa a
posição no array de dados aonde a
informação deverá ser inserida.
Array de Informações
• É um array que pode armazenar
diretamente os valores, para cada
uma das posições resultantes da
função Hash, ou armazenar
referências para as listas de dados
associadas a uma determinada
posição fornecida pela Função Hash.
Exemplo
• Distribuindo números de X em X:
– Imagine que temos um banco de dados
de uma instituição bancária.
– Neste banco de dados, definimos como
chave para uma tabela Hash o número
da conta-corrente do cliente.
– Queremos então dividir, através da
tabela Hash, as contas bancarias dos
clientes em 6 grupos.
Exemplo
• Distribuindo números de X em X:
– Este banco de dados esta sempre
crescendo;
– Por isso não podemos definir limiares
fixos separando grupos de contas. Uma
das soluções, seria, separar os números
das contas, inclusive as futuras novas,
de X em X números.
– Como isto? Segue a demonstração:
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = __
L = 06
R = __
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 99
L = 06
R = __
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99 E = 99
L = 06
R = 03
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 99
L = 06
R = 03
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 99
L = 06
R = 03
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = __
L = 06
R = __
05
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 05
L = 06
R = __
05
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 05
L = 06
R = 05
05
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 05
L = 06
R = 0505
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 05
L = 06
R = 05
05
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = __
L = 06
R = __
05
11
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 11
L = 06
R = __
05
11
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 11
L = 06
R = 05
05
11
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 11
L = 06
R = 05
05
11
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 11
L = 06
R = 05
05
11
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 11
L = 06
R = 05
05
11
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 11
L = 06
R = 05
05
11
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = __
L = 06
R = __
05
11
06
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 06
L = 06
R = __
05
11
06
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 05
L = 06
R = 00
05
11
06
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 05
L = 06
R = 00
05
11
06
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 05
L = 06
R = 00
05
11
06
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = __
L = 06
R = __
05
11
06
20
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 20
L = 06
R = __
05
11
06
20
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 20
L = 06
R = 02
05
11
06
20
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 20
L = 06
R= 02
05
11
06
20
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 20
L = 06
R = 02
05
11
06 20
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = __
L = 06
R = __
05
11
06 20
35
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 35
L = 06
R = __
05
11
06 20
35
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 35
L = 06
R = 05
05
11
06 20
35
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 35
L = 06
R = 05
05
11
06 20
35
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 35
L = 06
R = 05
05
11
06 20
35
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 35
L = 06
R = 05
05
11
06 20
35
Colunas
Ponteiros
Índices
Função Hash
0 1 2 3 4 5
Dados
R = E % L
E
R
L (Largura; Colunas)
Entrada
Saíd
a
99
E = 35
L = 06
R = 05
05
11
06 20
35
Exercícios
1. Crie uma função Hash que separa números de CPF de 200 em 200
elementos;
2. Com a função h(k) = k % 11, desenhe o resultado de uma Hash Table
para os dados: 82, 31, 28, 4, 45, 27, 59, 79, 35;
3. Com a função hash abaixo, desenhe o resultado de uma Hash Table com
os seguintes valores:
– 80, 35, 29, 33, 19, 18, 40, 10, 6, 21;
public static int funcaoHash(int valor) {
if (valor % 2 == 0) {
return 0;
} else if (valor % 3 == 0) {
return 1;
}
return 2;
}
Trabalho Hash Table
• Uma empresa precisa de um programa de
computador que efetue o cadastro de compradores.
Os compradores deverão ser alocados e
recuperados rapidamente da memória. Crie o
programa para esta empresa, alocando os
“Compradores” em uma hash table.
– Use sua criatividade para escolher os
componentes que irá utilizar para construir a
Hash Table;
– A chave hash deverá ser composta pelo NOME
do comprador;
– Cada comprador tem os seguintes dados:
• Nome;
• CPF;
• RG;
• Telefone.