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 [Link]().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:
E
99 Entrada R=E%L
Função Hash
E = __
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados
E
Entrada 99 R=E%L
Função Hash
E = 99
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados
E
Entrada R=E%L
Função Hash
99
E = 99
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 03
Colunas
Ponteiros
Dados
E
Entrada R=E%L
Função Hash
E = 99
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas)
99 R = 03
Colunas
Ponteiros
Dados
E
Entrada R=E%L
Função Hash
E = 99
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 03
Colunas
Ponteiros
Dados 99
E
05 Entrada R=E%L
Função Hash
E = __
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 99
E
Entrada 05 R=E%L
Função Hash
E = 05
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 99
E
Entrada R=E%L
Função Hash
05
E = 05
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
Dados 99
E
Entrada R=E%L
Função Hash
E = 05
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) 05 R = 05
Colunas
Ponteiros
Dados 99
E
Entrada R=E%L
Função Hash
E = 05
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
Dados 99 05
E
11 Entrada R=E%L
Função Hash
E = __
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 99 05
E
Entrada 11 R=E%L
Função Hash
E = 11
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 99 05
E
Entrada R=E%L
Função Hash
11
E = 11
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
Dados 99 05
E
Entrada R=E%L
Função Hash
E = 11
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) 11 R = 05
Colunas
Ponteiros
Dados 99 05
E
Entrada R=E%L
Função Hash
E = 11
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
11
Dados 99 05
E
Entrada R=E%L
Função Hash
E = 11
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
11
Dados 99 05
E
Entrada R=E%L
Função Hash
E = 11
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
Dados 99 05
11
E
06 Entrada R=E%L
Função Hash
E = __
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 99 05
11
E
Entrada 06 R=E%L
Função Hash
E = 06
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 99 05
11
E
Entrada R=E%L
Função Hash
06
E = 05
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 00
Colunas
Ponteiros
Dados 99 05
11
E
Entrada R=E%L
Função Hash
E = 05
Saída
R
L = 06
Índices 0 1 2 3 4 5
06 L (Largura; Colunas) R = 00
Colunas
Ponteiros
Dados 99 05
11
E
Entrada R=E%L
Função Hash
E = 05
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 00
Colunas
Ponteiros
Dados 06 99 05
11
E
20 Entrada R=E%L
Função Hash
E = __
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 06 99 05
11
E
Entrada 20 R=E%L
Função Hash
E = 20
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 06 99 05
11
E
Entrada R=E%L
Função Hash
20 E = 20
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 02
Colunas
Ponteiros
Dados 06 99 05
11
E
Entrada R=E%L
Função Hash
E = 20
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 02
Colunas 20
Ponteiros
Dados 06 99 05
11
E
Entrada R=E%L
Função Hash
E = 20
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 02
Colunas
Ponteiros
Dados 06 20 99 05
11
E
35 Entrada R=E%L
Função Hash
E = __
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 06 20 99 05
11
E
Entrada 35 R=E%L
Função Hash
E = 35
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = __
Colunas
Ponteiros
Dados 06 20 99 05
11
E
Entrada R=E%L
Função Hash
35 E = 35
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
Dados 06 20 99 05
11
E
Entrada R=E%L
Função Hash
E = 35
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas 35
Ponteiros
Dados 06 20 99 05
11
E
Entrada R=E%L
Função Hash
E = 35
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
35
Dados 06 20 99 05
11
E
Entrada R=E%L
Função Hash
E = 35
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
Dados 06 20 99 05
35
11
E
Entrada R=E%L
Função Hash
E = 35
Saída
R
L = 06
Índices 0 1 2 3 4 5
L (Largura; Colunas) R = 05
Colunas
Ponteiros
Dados 06 20 99 05
11
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.