Tabelas de espalhamento
(HASH)
Observação
Leiam o seguinte texto baseado no livro do Cormen. Estes slides tem como único objetivo auxiliar no entendimento destes conceitos. Não está completo.
Busca ?
Quais algoritmo e estruturas que vocês já conhecem ?
Quais as limitações ?
Alguns algoritmos ....
Pesquisa sequencial
Pesquisa binária
Pesquisa Sequencial
x
Pesquisa Binária
Estruturas ....
Estruturas ....
Arranjos (array ou vetor)
Estruturas ....
Arranjos (array ou vetor)
Listas encadeadas
Estruturas ....
Arranjos (array ou vetor)
Listas encadeadas
Árvores binárias e n-árias
Estruturas ....
Arranjos (array ou vetor)
Listas encadeadas
Árvores binárias e n-árias
X
X
Estruturas ....
Arranjos (array ou vetor)
Listas encadeadas
Árvores binárias e n-árias
X
X
O (1)
O (N)
O (logN)
Como aproveitar as características de acesso constante de uma estrutura de dados contigua (vetor ou arranjo) ?
Pense na matricula de vocês ? Posso usá-la diretamente como um indice de um vetor ? Como seria a complexidade de busca ? Quais problemas ?
Rafael
24452
|
15600
Tancredo
Para a turma SIF130-2012, teriamos algo assim:
struct aluno {
int mat; // 4 bytes = 4 bytes
char nome[81]; // 1 byte * 81 = 81 bytes
char email[41]; // 1 byte * 41 = 41 bytes
}; Total = 126 bytes
typedef struct aluno Aluno;
Rafael
24452
|
15600
Tancredo
Para a turma SIF130-2012, teriamos algo assim:
struct aluno {
int mat; // 4 bytes = 4 bytes
char nome[81]; // 1 byte * 81 = 81 bytes
char email[41]; // 1 byte * 41 = 41 bytes
}; Total = 126 bytes
typedef struct aluno Aluno;
Quanto estarei consumindo de memoria ?
E se a matricula fosse composta por mais digitos, por exemplo 8.
E se quisessemos indexar por outra informação, ao invés da matricula, por exemplo o nome.
Função
Que função simples eu posso usar para mapear a matricula para valores entre 0 a 100.
Método da divisão
h(k) = k mod m
21398
17328
21513
21613
21264
98
Para m igual a 100, concluam o mapeamento e me diz o que identificaram ?
Função sobrejetora
Pode ocorrer que mais de um "índice" seja mapeado para um único valor.
Neste caso dizemos que ocorreu uma "colisão".
Função hash
Colisão
Funçao hash
Função hash é como uma função qualquer, porém o grande desafio é gerar funções onde ocorra poucas colisões.
Em rede e sistemas operacionais vocês verão alguns algoritmos, como o md5 e sha-1.
Como vocês acham que funciona a autenticação em um sistem unix ?
Tabelas de espalhamento (hash)
DEFINIÇÃO DE HASH
Função de
Hashing
123.456.781-00
143.576.342-23
345.365.768-93
879.094.345-45
19
19
123.456.781-00; Fausto Silva; Av. Canal. Nº 45.
...
37
143.576.342-23; Carla Perez; Rua Celso Oliva. Nº 27.
...
50
345.365.768-93; Gugu Liberato; Av. Atlântica. S/N.
...
85
879.094.345-45 ; Hebe Camargo; Rua B. Nº 100.
...
37
50
85
20
Tabela Hash
Função hash
Função hash
Função hash
Considerem uma função hash que mapeia todos os valores para o mesmo indice. Qual será a complexidade de busca ?
Considerem uma função hash que mapeia apenas um valor para cada indice. Qual será a complexidade de busca?
Como representar ?
Como representar ?
Precisamos de uma função hash
Como representar ?
Precisamos de uma função hash
Precisamos de um arranjo (vetor)
Como representar ?
Precisamos de uma função hash
Precisamos de um arranjo (vetor)
Precisamos tratar as colisões
Tratando colisões
Endereçamento fechado
Endereçamento aberto
ENDEREÇAMENTO FECHADO
ENDEREÇAMENTO FECHADO
No endereçamento fechado, a posição de inserção não muda. Todos devem ser inseridos na mesma posição, através de uma lista ligada em cada uma.
0
1
2
3
4
20 mod 5 = 0
20
18 mod 5 = 3
18
25 mod 5 = 0�colisão com 20
25
ENDEREÇAMENTO FECHADO
A busca é feita do mesmo modo: calcula-se o valor da função hash para a chave, e a busca é feita na lista correspondente.
Se o tamanho das listas variar muito, a busca pode se tornar ineficiente, pois a busca nas listas se torna seqüencial
0
1
2
3
20
4
0
88
32
15
11
60
ENDEREÇAMENTO FECHADO
A função HASH deve distribuir as chaves entre as posições de maneira uniforme
0
0
1
2
3
4
5
6
15
10
31
4
88
13
20
Endereçamento fechado - Operações
Chained-Hash-Search(T,k)
procure um elemento com chave k na lista T[h(k)] e devolva seu ponteiro
Chained-Hash-Insert(T,x)
insira x na cabeça da lista T[h(key[x])]
Chained-Hash-Delete(T,x)
remova x da lista T[h(key[x])]
Endereçamento aberto
No enderecamento aberto, todos os elementos são armazenados na
propria tabela hash.
Para realizar uma inserção, examinamos/testamos sucessivamente a
tabela hash ate que encontrarmos um slot vazio no qual a chave sera
inserida.
Em enderecamento aberto, a tabela hash pode encher, de forma que
nao seja mais possvel inserir elementos.
Endereçamento aberto - Inserção
9
|
0
1
Valores: 204, 44, 58, 10, 100, 25, 20
Endereçamento aberto - Inserção
9
204
|
0
1
Valores: 204, 44, 58, 10, 100, 25, 20
Endereçamento aberto - Inserção
44
9
204
|
0
1
Valores: 204, 44, 58, 10, 100, 25, 20
Endereçamento aberto - Inserção
44
9
204
|
0
1
Valores: 204, 44, 58, 10, 100, 25, 20
Terminem de completar ....
Endereçamento aberto
Algoritmo de inserção
Algoritmo de busca
Endereçamento aberto
Algoritmo de inserção
Algoritmo de busca
Quais conclusões que são possíveis tirar ?
Endereçamento aberto
A tabela tem que ser tratada de modo circular, quando chega no fim da tabela a varredura reinicia na posição 0.
Quanto mais "cheia" a tabela estiver, pior será a eficiência.