Tabelas Hash

Tabelas Hash & Outras
Estruturas
Prof. MSc. João Ricardo Bittencourt
Algoritmos e Estrutura de Dados em C++
Desenvolvimento de Jogos &
Entretenimento Digital
UNISINOS
Sumário
1.
2.
3.
4.
5.
Conceito de hashing
Comparação de complexidade
Usando STL e tabelas hash
 Set & Multiset
 Map & Multimap
Vector & Deque
Exercícios
Conceito de Hashing

“Que tal efetuar buscas rapidamente sem
precisar percorrer toda a estrutura de
dados?”
 Seus problemas acabaram, agora você pode
usar a Super Hyper Hashing Table :-P
 A idéia é cada dado (ou estrutura) ser capaz
de gerar um código idealmente único. E
usarmos este código para fazer a indexação.
 Recurso extremamente usado em banco de
dados.
 Ótimo recurso para ser usado em games!!
Conceito de Hashing

Conceito Chave
 FUNÇÃO DE HASHING!

Cada dado/estrutura deve possuir uma função de
hash que gere um número preferencialmente
único!
0
1
2
3
4
5
6
7
f(x) = (x mod 12)
Função de hashing
8
9
10 11
Conceito de Hashing

Conceito Chave
 FUNÇÃO DE HASHING!

Cada dado/estrutura deve possuir uma função de
hash que gere um número preferencialmente
único!
0
1
2
3
4
5
6
7
x=232 f(x)=4
f(x) = (x mod 12)
Função de hashing
8
9
10 11
Conceito de Hashing

Conceito Chave
 FUNÇÃO DE HASHING!

Cada dado/estrutura deve possuir uma função de
hash que gere um número preferencialmente
único!
0
1
2
232
3 4
5
6
7
x=232 f(x)=4
f(x) = (x mod 12)
Função de hashing
8
9
10 11
Conceito de Hashing

Conceito Chave
 FUNÇÃO DE HASHING!

Cada dado/estrutura deve possuir uma função de
hash que gere um número preferencialmente
único!
0
1
2
232
3 4
5
6
7
x=969 f(x)=9
f(x) = (x mod 12)
Função de hashing
969
8 9 10 11
Conceito de Hashing

Conceito Chave
 FUNÇÃO DE HASHING!

Cada dado/estrutura deve possuir uma função de
hash que gere um número preferencialmente
único!
0
1
2
232
3 4
5
6
7
969
8 9 10 11
x=1024 f(x)=4 ???
f(x) = (x mod 12)
Função de hashing
Conceito de Hashing

Conceito Chave
 FUNÇÃO DE HASHING!

Cada dado/estrutura deve possuir uma função de
hash que gere um número preferencialmente
único!
1024
232
969
0 1 2 3 4 5 6 7 8 9 10 11
x=1024 f(x)=4 Vai para uma lista
f(x) = (x mod 12)
Função de hashing
Comparação de
Complexidade

Para busca
Melhor Caso Caso Médio Pior Caso
Pilha
O(1)
O(n/2)
O(n)
Fila
O(1)
O(n/2)
O(n)
Lista
O(1)
O(n/2)
O(n)
Hash
O(1)
O(n/k)
O(log n)
Sendo k o número de posições no vetor

Dependendo da qualidade da função de hashing
teremos uma complexidade na busca muito
próxima de O(1)
Usando STL e tabelas Hash

Na STL são chamados de contêiners associativos

Conjuntos
 Multiset - o próprio valor é a chave, permite
duplicações
 Set – o próprio valor é a chave, sem duplicata

Valores mapeados
 Multimap - associa uma chave ao valor,
permite duplicações
 Map – associa uma chave ao valor, sem
duplicata
Usando STL e tabelas Hash
81 101
81 745
32
75 71
99 101
71
81 745
32
75
99
71
Multiset
“A”
“K”
“B”
Multimap
Set
32
71
75
81
99
745
“A”
“C”
“H”
“K”
“L”
“B”
Map
32
71
75
81
99
745
Operações com Multiset

Inserir elemento no conjunto - insert

Remover elemento do conjunto- erase

Encontrar elemento no conjunto- find

Verificar se o conjunto está vazio - empty

Verificar o tamanho do conjunto- size

Obter a primeira ocorrência e a posição
após a última ocorrência de um elemento
no conjunto
 lower_bound
 upper_bound
Operações com Set

Inserir elemento no conjunto - insert

Remover elemento do conjunto- erase

Encontrar elemento no conjunto- find

Verificar se o conjunto está vazio - empty

Verificar o tamanho do conjunto- size

Demonstração
Operações com Multimap

Inserir elemento no conjunto - insert

Remover elemento do conjunto- erase

Encontrar elemento no conjunto- find

Verificar se o conjunto está vazio - empty

Verificar o tamanho do conjunto- size

Obter a primeira ocorrência e a posição
após a última ocorrência de um elemento
no conjunto
 lower_bound
 upper_bound
Operações com Map

Inserir elemento no conjunto - insert

Remover elemento do conjunto- erase

Encontrar elemento no conjunto- find

Verificar se o conjunto está vazio - empty

Verificar o tamanho do conjunto- size

Acesso ao elemento do map  mapa[chave] = valor

Demonstração
Vector

O mesmo princípio dos vetores “brutos” do C++

Acesso aleatório através de subscrito – vetor[n]

Entretanto faz todo o processo de
redimensionamento de forma automática

Faz a inserção (push_back) e a remoção
(pop_back) no final

Dá acesso ao início (front) e final (back) da
estrutura

Faz uso de iteradores
Deque

Combinação de um vector com uma list

Pronuncia-se “deek” - “double-end queue”

Acesso aleatório através de subscrito – vetor[n]

Faz uso de iteradores

Permite inserção/remoção no início e no final da
estrutura
(push_front/pop_front/push_back/pop_back)

Dá acesso ao início (front) e final (back) da
estrutura

Demonstração