Definição de Dicionário
Dicionário é um sistema de informações:

Equivalente a um conjunto de elementos não
repetidos

Cujas operações são:
Inserir, Deletar e Membro (verificar se um
elemento pertence, ou é membro do conjunto)
Além das operações de fazer consultas e de
esvaziar
1
Tabela Hashing
1 – Idéia básica

Hashing: técnica importante, eficiente e muito usada
para a implementação de dicionários.
Hashing = ato de retalhar, recortar ou picar

Divisão dos elementos do dicionário em subconjuntos
mais gerenciáveis denominados classes (buckets)

A idéia é direcionar procuras, inserções e deleções
para apenas uma dessas classes
2

Um dicionário Dic dividido em C classes:
Classe 0
Classe 1
Classe 2
Classe C-1

Como dizer qual a classe de um elemento?

Função classificadora h: para um elemento x, do
mesmo tipo dos elementos do dicionário, h(x) é um
inteiro do conjunto {0, 1, 2, . . . , C-1}
3
Classe 0
Classe 1
Classe 2
Classe C-1

Para um elemento x, sua classe é h(x) em [0 .. C-1]

Dado um elemento x, ele seria procurado, inserido ou
deletado apenas da classe h(x), ignorando-se o
conteúdo das outras classes

Essa função deve ser tal que consiga equilibrar o
número de elementos das classes.
4
Exemplo: seja a montagem de um dicionário de nomes
de, no máximo, 10 caracteres.

Seja x um nome e x[i] o iésimo caractere de x

Seja
onde
n é o nº de caracteres de x e C=11.

Seja a seguir uma tabela de nomes a serem
introduzidos no dicionário, ao lado da sua somatória e
de sua função h
5
Conteúdo das classes do dicionário:
sergio
rogerio
itamar
ciro
antonio
Classe 0
orlando
juliana
Classe 1
francisco
paulo
carlos
severino
gisele
Classe 6
Classe 2
moises
joao
Classe 7
jose
berenice
Classe 3
tania
Classe 8
maria
raimundo
Classe 4
alessandra
fernando
Classe 9
Classe 5
sonia
Classe 10
6

Há duas estruturas muito conhecidas para as classes de
uma tabela hashing:

Hashing aberto: as classes são guardadas em listas
lineares encadeadas

Hashing fechado: as classes são guardadas em
blocos de elementos adjacentes num vetor de
elementos
7
2 – Hashing aberto
Estrutura básica:
8
Exemplo: hashing aberto para a tabela abaixo:
9

Declarações e operações:
const int C = 11;
/* escolhida convenientemente */
typedef char cadeia [11];
typedef struct celula celula;
struct celula {cadeia elemento; celula *prox;};
typedef celula *dicionario [11];
int h (cadeia x) {
int i, soma;
for (soma = 0, i = 0; x[i] != ‘\0’;
soma += x[i];
return soma % C;
}
i++)
10
void Esvaziar (dicionario Dic) {
int i; celula *p;
for (i = 0; i <= C-1; i++)
while (Dic[i] != NULL) {
p = Dic[i]; Dic[i] = Dic[i]->prox;
free (p);
}
}
logic Membro (cadeia x, dicionario Dic) {
celula *pont;
pont = Dic[h(x)];
while (pont != NULL)
if (pont->elemento == x)
return TRUE;
else pont = pont->prox;
return FALSE;
}
11
void Inserir (cadeia x; dicionario Dic)
int class; celula *p;
{
if (!Membro (x, Dic)) {
class = h(x);
p = Dic[class];
Dic[class] = malloc (sizeof (celula));
Dic[class]->elemento = x;
Dic[class]prox = p;
}
}
12
void Deletar (cadeia x, dicionario Dic) {
celula *p, *q; int class; logic achou;
class = h(x);
if (Dic[class] != NULL) {
if (Dic[class]->elemento == x) {
q = Dic [class];
Dic [class] = Dic[class]->prox; free (q);
}
else {
p = Dic[class]; achou = FALSE;
while (p->prox != NULL && !achou)
if (p->prox->elemento == x) {
Achou = Verdade; q = p->prox;
p->prox = p->prox->prox;
free (q);
}
else p = p->prox;
}
}
}
13
3 – Hashing fechado

É uma técnica apropriada para dicionários em que a
operação de deletar não é frequente

Os elementos do dicionário são armazenados em um
vetor
14

Cada posição do vetor guarda um elemento e mais
dois flags

Um para dizer se a posição está vazia

Outro para dizer se o elemento ali colocado foi
deletado
elemento
vazio
deletado
15

As classes são guardadas em blocos de posições adjacentes no
vetor (Na figura abaixo, são reservadas 3 posições por classe)

Para cada elemento inserido, o flag vazio torna-se falso; o flag
del inicialmente é falso em todas as posições
elemento
Cl
0
Cl
1
Cl
2
Cl
3
vaz
del
0
N
1
N
2
N
3
N
4
N
5
N
6
N
7
N
8
N
9
N
10
N
11
N
elemento
Cl
4
Cl
5
Cl
6
Cl
7
vaz
del
12
N
13
N
14
N
15
N
16
N
17
N
18
N
19
N
20
N
21
N
22
N
23
N
elemento
Cl
8
Cl
9
Cl
10
vaz
del
24
N
25
N
26
N
27
N
28
N
29
N
30
N
31
N
32
N
16
Os elementos vão sendo
inseridos até que não caiba
elemento em alguma classe;
exemplo: tabela vista

0
Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
sergio
N
N
1
N
2
N
3
N
4
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
12
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
jose
N
N
13
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
N
22
N
23
N
24
Cl
8
Cl
9
10
vaz
del
tania
N
N
25
N
26
N
27
N
28
N
29
N
30
Cl
elemento
sonia
N
N
31
N
32
N
17
O próximo elemento da
classe 6 é inserido na
próxima posição vazia

0
Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
sergio
N
N
1
N
2
N
3
N
4
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
12
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
jose
N
N
13
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
N
23
N
24
Cl
8
Cl
9
10
vaz
del
tania
N
N
25
N
26
N
27
N
28
N
29
N
30
Cl
elemento
sonia
N
N
31
N
32
N
18
Continua a inserção até
chegar um elemento da
classe 7

Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
N
4
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
12
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
jose
N
N
13
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
N
23
N
24
Cl
8
9
10
del
tania
N
N
N
26
N
alessandra
N
N
28
N
29
N
30
Cl
vaz
25
27
Cl
elemento
sonia
N
N
31
N
32
N
19
Insere-se o elemento na
primeira posição vazia a
partir da classe 7

Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
N
4
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
12
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
jose
N
N
13
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
moises
N
N
23
24
Cl
8
9
10
del
tania
N
N
N
26
N
alessandra
N
N
28
N
29
N
30
Cl
vaz
25
27
Cl
elemento
sonia
N
N
31
N
32
N
N
20
Classe 0 cheia, insere na
próxima posição vazia

Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
12
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
jose
N
N
13
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
moises
N
N
23
24
Cl
8
9
10
del
tania
N
N
N
26
N
alessandra
N
N
28
N
29
N
30
Cl
vaz
25
27
Cl
elemento
sonia
N
N
31
N
32
N
N
21
Continua até o próximo
problema

Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
12
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
jose
N
N
13
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
moises
N
N
23
joao
N
N
24
Cl
8
9
10
del
tania
N
N
N
26
N
alessandra
N
N
28
N
29
N
30
Cl
vaz
25
27
Cl
elemento
sonia
N
N
31
N
32
N
22
Só há posição vazia para
elemento da classe 6 na
classe 8

Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
12
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
jose
N
N
13
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
moises
N
N
23
joao
N
N
Cl
8
elemento
vaz
del
24
tania
N
N
25
gisele
N
N
26
27
Cl
9
10
alessandra
N
N
28
N
29
N
30
Cl
N
sonia
N
N
31
N
32
N
23
E assim até o final

Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
antonio
N
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
12
jose
N
N
13
berenice
N
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
moises
N
N
23
joao
N
N
Cl
8
Cl
9
elemento
vaz
del
24
tania
N
N
25
gisele
N
N
26
27
alessandra
N
N
28
fernando
N
N
29
30
Cl
10
N
N
sonia
N
N
31
N
32
N
24

Procuras, inserções e deleções realizam percurso que começa no início
da classe correspondente

Proibindo-se deleções, procuras e inserções encerram percurso ao
encontrar o elemento ou uma posição vazia (desnecessário o campo del)
Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
antonio
N
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
12
jose
N
N
13
berenice
N
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
N
19
paulo
N
N
20
carlos
N
N
21
severino
N
N
22
moises
N
N
23
joao
N
N
Cl
8
Cl
9
elemento
vaz
del
24
tania
N
N
25
gisele
N
N
26
27
alessandra
N
N
28
fernando
N
N
29
30
Cl
10
N
N
sonia
N
N
31
N
32
N
25

Permitindo-se deleções, marca-se o campo del do elemento deletado

Exemplo: deletando-se paulo e moises, inserção na classe 6 ou 7, só na
classe 8 e adiante
Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
antonio
N
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
12
jose
N
N
13
berenice
N
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
19
paulo
N
20
carlos
N
N
21
severino
N
N
22
moises
N
23
joao
N
Cl
8
Cl
9
N
elemento
vaz
del
24
tania
N
N
25
gisele
N
N
26
27
alessandra
N
N
28
fernando
N
N
29
30
Cl
10
N
N
sonia
N
N
31
N
32
N
N
26

Uma procura por um elemento da classe 6 que não esteja presente, só
termina na posição 26 (vazia)

Encerrar uma procura para inserção, quando encontrado um elemento
deletado, não garante que o elemento a ser inserido não esteja presente
Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
antonio
N
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
12
jose
N
N
13
berenice
N
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
19
paulo
N
20
carlos
N
N
21
severino
N
N
22
moises
N
23
joao
N
Cl
8
Cl
9
N
elemento
vaz
del
24
tania
N
N
25
gisele
N
N
26
27
alessandra
N
N
28
fernando
N
N
29
30
Cl
10
N
N
sonia
N
N
31
N
32
N
N
27

A recuperação de posições deletadas é um trabalho complicado de
remanejamento dos elementos dentro do vetor

Isso deve ser feito quando se esgotarem as posições de inserção
Cl
0
Cl
1
Cl
2
Cl
3
elemento
vaz
del
0
sergio
N
N
1
rogerio
N
N
2
itamar
N
N
3
ciro
N
N
4
antonio
N
N
5
N
6
N
7
N
8
N
9
orlando
N
N
10
juliana
N
N
11
N
Cl
4
Cl
5
Cl
6
Cl
7
elemento
vaz
del
12
jose
N
N
13
berenice
N
N
14
N
15
maria
N
N
16
raimundo
N
N
17
N
18
francisco
N
19
paulo
N
20
carlos
N
N
21
severino
N
N
22
moises
N
23
joao
N
Cl
8
Cl
9
N
elemento
vaz
del
24
tania
N
N
25
gisele
N
N
26
27
alessandra
N
N
28
fernando
N
N
29
30
Cl
10
N
N
sonia
N
N
31
N
32
N
N
28