Estruturas de dados para pesquisa em memória primária

Prévia do material em texto

L
N
C
C 
Parte 2: Estruturas de dados para 
pesquisa em memória primária 
GA-024 
Antônio Tadeu A. Gomes, D.Sc. 
 
atagomes@gmail.com 
http://wiki.martin.lncc.br/atagomes-cursos-lncc-ga024 
Sala 2C-01 
L
N
C
C 
Estruturas de dados para pesquisa 
em memória primária 
l  Primórdios: pesquisa sequencial e binária 
 
l  Árvores binárias 
 
l  Árvores Trie e Patricia 
 
l  Tabelas de dispersão (hash) 
L
N
C
C 
Primórdios: pesquisa sequencial e 
binária (I) 
l  Pesquisa: encontrar em uma estrutura uma ou mais 
ocorrências de registros de dados com chaves iguais a uma 
chave de pesquisa 
-  Ex. de registro: 
 
 
l  Grande quantidade de métodos de pesquisa, cuja eficiência 
varia conforme: 
-  Quantidade dos dados envolvidos 
-  Frequência de inserções e retiradas de dados 
l  Problema associado: ordenação de registros 
-  Estruturas pré-ordenadas podem auxiliar no processo de 
pesquisa 
struct registry { 
 int id; /* chave do registro */ 
 ... /* outros campos do registro */ 
} 
 
typedef struct registry Registry; 
L
N
C
C 
Primórdios: pesquisa sequencial e 
binária (II) 
l  Pesquisa sequencial: 
-  Método para vetores e listas encadeadas 
-  Método mais simples 
-  Independe da estrutura estar pré-ordenada 
-  Melhor solução para pequenas quantidades de dados 
l  Tempo médio de pesquisa para n registros: (n+1)/2 
 
l  Pesquisa binária: 
-  Método para vetores 
-  Depende da estrutura estar pré-ordenada 
l  Custo de manutenção da ordenação em vetores é alto 
-  Boa solução para dados estáveis 
l  Tempo médio de pesquisa para n registros: ≈ log n 
L
N
C
C 
Primórdios: pesquisa sequencial e 
binária (III) 
/* tamanho do vetor = n */ 
/* função retorna posição do registro no vetor v, 
 ou -1 se não encontrou */ 
int binsearch( Registry *v, int id ) { 
 if( n <= 0 ) return -1; 
 int esq = 0; int dir = n-1; int i; 
 do { 
 i = (esq+dir)/2; 
 if( id > v[i].id ) 
 esq = i+1; 
 else 
 dir = i-1; 
 } while( ( id != v[i].id ) && ( esq <= dir ) ); 
 if( id == v[i].id ) 
 return i; 
 return -1; 
} 
l  Ex. (pesquisa binária em vetor de registros): 
-  Versão recursiva? 
 
l  Ex. (busca de G): 
L
N
C
C 
Árvores binárias (I) 
l  Vetores e listas encadeadas: estruturas de dados 
lineares 
-  Inadequadas para representar hierarquias 
l  Ex.: diretórios de arquivos 
-  Vários trade-offs a serem considerados entre as duas 
estruturas no que se refere a ordenação e pesquisa 
 
l  Árvores: estruturas de dados hierárquicas 
-  Boa solução de compromisso para armazenamento: 
l  Eficiência no acesso direto e sequencial a registros 
l  Eficiência na inserção e retirada de registros 
l  Boa taxa de utilização de memória 
L
N
C
C 
Árvores binárias (II) 
l  Árvores: conjunto de nós tal que existe um nó r, 
denominado raiz, com zero ou mais sub-árvores, 
cujas raízes estão ligadas a r 
-  os nós raízes destas sub-árvores são os filhos de r 
-  os nós internos da árvore são os nós com filhos 
-  as folhas ou nós externos da árvore são os nós sem 
filhos 
L
N
C
C 
Árvores binárias (III) 
l  Árvores binárias: 
-  cada nó tem zero, um ou dois filhos 
 
l  Definição recursiva – uma árvore binária é: 
-  uma árvore vazia; ou 
-  um nó raiz com duas sub-árvores: 
l  a sub-árvore da direita (sad) 
l  a sub-árvore da esquerda (sae) 
L
N
C
C 
Árvores binárias (IV) 
l  Propriedade fundamental: 
-  só existe um caminho da raiz para qualquer nó (cf. 
grafos) 
 
l  Altura de uma árvore: 
-  comprimento do caminho mais 
longo da raiz até uma das folhas 
l  a altura de uma árvore com um único 
nó raiz é zero 
l  a altura de uma árvore vazia é, 
por convenção, -1 
 
-  Ex.: altura = 2 
L
N
C
C 
Árvores binárias (V) 
l  Nível de um nó 
-  a raiz está no nível 0, seus filhos diretos no nível 1, ... 
-  o último nível da árvore é a altura da árvore 
L
N
C
C 
Árvores binárias (VI) 
l  Árvore cheia: 
-  todos os seus nós internos têm duas sub-árvores 
associadas 
-  número n de nós de uma árvore cheia de altura h 
n = 2h+1 -1 
L
N
C
C 
Árvores binárias (VII) 
l  Árvore degenerada: 
-  todos os seus nós internos têm uma única sub-árvore 
associada 
-  número n de nós de uma árvore degenerada de altura h 
n = h+1 
L
N
C
C 
Árvores binárias (VIII) 
l  Esforço computacional necessário para alcançar 
qualquer nó da árvore 
-  Proporcional à altura da árvore 
 
l  Altura de uma árvore binária com n nós: 
-  mínima: proporcional a log n (caso da árvore cheia) 
-  máxima: proporcional a n (caso da árvore degenerada) 
L
N
C
C 
Árvores binárias (IX) 
l  Ex. (avaliação de expressões aritméticas): 
-  nós folhas representam operandos 
-  nós internos representam operadores 
 
-  (3+6)*(4-1)+5 
l  Como avaliar essa expressão? 
L
N
C
C 
Árvores binárias (X) 
l  TAD “BTree” em C (elemento ponteiro p/ Registry): 
-  Operações básicas: 
l  BTree* btree_create(void) 
l  BTree* btree_createfrom(Registry *r, BTree* sae, BTree* sad) 
l  BTree* btree_destroy(BTree* t) 
l  int btree_isempty(BTree* t) 
l  Registry* btree_getelem(BTree* t, int id) 
l  void btree_print(BTree* t) 
-  Estrutura: struct btree { 
 Registry *info; 
 struct btree* sae; 
 struct btree* sad; 
}; 
 
typedef struct btree BTree; 
L
N
C
C 
Árvores binárias (XI) 
l  Operações em geral implementadas recursivamente 
BTree* btree_create(void) { 
 return NULL; 
} 
BTree* btree_createfrom(Registry *r, BTree* sae, BTree* sad) { 
 BTree* p=(BTree*)malloc(sizeof(BTree)); 
 p->info = r; 
 p->sae = sae; 
 p->sad = sad; 
 return p; 
} 
BTree* btree_destroy(BTree* t) { 
 if (!btree_isempty(t)) { 
 btree_destroy(t->sae); 
 btree_destroy(t->sad); 
 free(t); 
 } 
 return NULL; 
} 
L
N
C
C 
Árvores binárias (XII) 
l  Ex. (criação de árvore): 
-  Para onde aponta t? 
-  Como pesquisar nessa árvore 
(btree_getelem())? 
BTree* t = btree_createfrom(a, 
 btree_createfrom(b, 
 btree_create(), 
 btree_createfrom(d, 
 btree_create(), 
 btree_create()) 
 ), 
 btree_createfrom(c, 
 btree_createfrom(e, 
 btree_create(), 
 btree_create()), 
 btree_createfrom(f, 
 btree_create(), 
 btree_create()) 
 ) 
 ); 
L
N
C
C 
Árvores binárias (XIII) 
l  Árvore binária de pesquisa: 
-  Todos os registros com chaves menores que o da raiz 
estão na sae e os com chaves maiores na sad 
l  Tempo médio de pesquisa para n registros: ≈ log n 
 
 
 
 
 
 
 
-  Como imprimir os registros 
da árvore em ordem crescente 
das chaves (btree_print())? 
a 
b 
c 
d 
e 
f 
Registry* btree_getelem(BTree* t, int id) { 
 if( btree_isempty(t) ) return NULL; 
 else if( id < t->info->id ) return btree_getelem( t->sae, id ); 
 else if( id > t->info->id ) return btree_getelem( t->sad, id ); 
 else return t->info; 
} 
L
N
C
C 
Árvores binárias (XIV) 
l  Ordens de percurso: 
 
-  pré-ordem: 
l  trata raiz, percorre sae, percorre sad 
l  Ex.: c a b e d f 
 
-  ordem simétrica (ou 
caminhamento central): 
l  percorre sae, trata raiz, percorre sad 
l  Ex.: a b c d e f 
 
-  pós-ordem: 
l  percorre sae, percorre sad, trata raiz 
l  Ex.: b a d f e c 
a 
b 
c 
d 
e 
f 
L
N
C
C 
Árvores binárias (XV) 
l  Inserção/remoção de nós em/de uma árvore binária 
de pesquisa envolve tratamento especial 
 
l  Inserção: 
-  Tempo médio: ≈ log n (!!!) 
BTree* btree_insert(BTree* t, Registry* r) { 
 if (btree_isempty(t)) { 
 t = (BTree*)malloc(sizeof(BTree)); 
 t->info = r; 
 t->sae = t->sad = NULL; 
 } 
 else if (r->id < t->info->id) 
 t->sae = btree_insert(t->sae,r); 
 else 
 t->sad = btree_insert(t->sad,r); 
 return t; 
} 
L
N
C
C 
Árvores binárias (XVI) 
l  Remoção: 
-  Segueo mesmo princípio recursivo da inserção, sendo 
necessário tratar 3 casos de remoção de nó: 
1) nó que é folha 
2) nó possui um único filho 
3) nó possui dois filhos 
 
l  Algoritmo em C: [Celes et al, 2004, pág. 269] 
-  Tempo médio: > log n, mas << n (!!) 
L
N
C
C 
Árvores binárias (XVII) 
l  Remoção – caso 1: nó é folha 
-  libere a memória alocada 
L
N
C
C 
Árvores binárias (XVIII) 
l  Remoção – caso 2: nó possui um único filho 
-  libere a memória alocada 
-  o filho do nó removido passa a ser filho do pai desse nó 
L
N
C
C 
Árvores binárias (XIX) 
l  Remoção – caso 3: nó possui dois filhos 
-  encontre o nó N que precede o nó removido na ordenação (o 
elemento mais à direita da sub-árvore à esquerda) 
-  troque o registro do nó com o registro de N 
-  retire N da sub-árvore à esquerda (que agora contém o 
registro do nó que se deseja retirar) 
l  retirar o nó N agora é trivial, pois N é um nó folha ou N é um nó 
com um único filho (no caso, o filho da direita nunca existe) 
L
N
C
C 
Árvores binárias (XX) 
l  Considerações: 
-  O maior esforço computacional de busca ocorre quando 
os registros são inseridos em ordem crescente ou 
decrescente de chaves 
l  Neste caso a árvore resultante é uma árvore degenerada 
 
l  Árvore binária de pesquisa randômica: 
-  Árvore com n chaves, construída através de n inserções 
randômicas sucessivas em uma árvore inicialmente vazia 
l  Nesse caso, número esperado de comparações para recuperar 
um registro qualquer é cerca de 1,39 log n 
l  Como conseguir log n comparações (melhor caso)? 
L
N
C
C 
Árvores binárias (XXI) 
l  Árvore bin. de pesq. completamente balanceada: 
-  Subárvores vazias aparecem em no máximo dois níveis 
adjacentes 
-  Árvore cheia ≠ completamente balanceada! 
-  Minimiza tempo médio de pesquisa para uma distribuição 
uniforme das chaves (cada chave igualmente provável de ser 
usada em uma pesquisa) 
 
-  Problema: custo para manter a árvore completamente 
balanceada após cada inserção é muito alto 
l  Ex. (inserção 
de registro 
com chave 1): 
L
N
C
C 
Árvores binárias (XXII) 
l  Soluções intermediárias: 
-  Princípio básico: manter árvore “quase-balanceada”, ao 
invés de tentar manter a árvore completamente 
balanceada 
-  Objetivo: Procurar obter bons tempos de pesquisa, 
próximos do tempo ótimo da árvore completamente 
balanceada (≈ log n), mas sem custo muito alto para 
inserir ou retirar da árvore 
 
-  Algumas abordagens: 
l  Árvores AVL (Adelson-Velskki e Landis, 1962) 
l  Árvores 2-3 (Bayer, 1971) 
l  Árvores Rubro-Negras (Guibas e Sedgewick, 1978) 
L
N
C
C 
Árvores binárias (XXIII) 
l  Árvores AVL: 
-  Árvore construída de tal modo que a altura de sua 
subárvore direita difere da altura da subárvore esquerda 
de no máximo 1 
-  Definição recursiva! 
L
N
C
C 
Árvores binárias (XXIV) 
l  Inserção em árvores AVL: 
-  Dada uma raiz r com subárvores sae e sad, e supondo que a 
inserção deve ser feita na sub-árvore sae, pode-se distinguir 3 
casos: 
l  Se h(sae) = h(sad), então sae e sad 
ficam com alturas diferentes 
mas continuam balanceadas 
l  Se h(sae) < h(sad), então sae e sad 
ficam com alturas iguais e 
balanceamento foi melhorado 
(Ex.: inserção dos nós 9 e 11) 
l  Se h(sae) > h(sad), então sae 
fica ainda maior e balanceamento foi violado 
(Ex.: inserção dos nós 3, 5 e 7) 
l  Remoção em árvores AVL também pode implicar em 
desbalanceamento (Ex.: remoção do nó 10) 
L
N
C
C 
Árvores binárias (XXV) 
l  Rebalanceamento de uma árvore AVL após uma 
inserção/remoção pode ser feito através de 
operações de rotação sobre a árvore 
-  Critério: Fator de Balanceamento (FB) dos nós 
l  Altura da subárvore direita do nó menos a altura da subárvore 
esquerda do nó 
-  Árvore está balanceada se FB = -1, 0 ou 1 
(Ex.: FB(8) = -1, FB(4) = 0, FB(10) = 0) 
 
-  FB deve ser reavaliado (e rotação 
efetuada, se necessário) antes/após 
inserção/remoção de nó, de modo 
ascendente em relação ao 
ponto de modificação da árvore 
L
N
C
C 
Árvores binárias (XXVI) 
l  Rotação: mudança do arranjo topológico da árvore 
em relação a um nó pivô 
-  Rotação à direita X Rotação à esquerda 
l  Ex.: inserção do nó 5 
Rotação de 4 à esquerda 
(pivô = 6) 
Rotação de 8 à direita 
(pivô = 6) 
L
N
C
C 
Árvores binárias (XXVII) 
l  Rebalanceamento 
de árvores AVL: 
-  2 tipos, 4 casos: 
 
-  Tipo 1: o nó raiz 
de uma subárvore 
tem FB = +-2 e 
tem um filho com 
FB = +-1, com 
mesmo sinal que 
FB do nó pai 
-  Tipo 2: o nó raiz 
de uma subárvore 
tem FB = +-2 e 
tem um filho com 
FB = +-1, com 
sinal oposto ao FB 
do nó pai 
L
N
C
C 
Árvores binárias (XXVIII) 
l  Árvore com número variável de filhos: 
-  Representação: “lista de filhos” 
l  Um nó aponta apenas 
para seu primeiro 
filho 
l  Cada um de seus filhos 
aponta para o próximo 
irmão 
L
N
C
C 
Árvores Trie e Patricia (I) 
l  Algoritmos de pesquisa para registros cujas chaves 
são representadas por sequências de caracteres ou 
de dígitos 
-  Conhecidos como algoritmos de pesquisa digital 
-  Particularmente vantajosos quando as chaves são 
grandes e de tamanho variável 
 
l  Possibilitam localizar todas as ocorrências de uma 
determinada chave em um conjunto de registros, 
com tempo de resposta ≈ log n 
-  Uso em casamento de padrões, construção e consulta de 
tabelas de rotas em redes de computadores etc. 
L
N
C
C 
Árvores Trie e Patricia (II) 
l  Trie – árvore M-ária cujos: 
-  nós internos são conjuntos (p.ex. vetores) de M 
componentes com campos correspondentes aos dígitos 
ou caracteres que formam as chaves 
-  nós folhas armazenam chave completa e registro 
 
l  Cada nó interno no nível i representa o conjunto de 
todas as chaves que começam com a mesma 
sequência de i dígitos ou caracteres 
L
N
C
C 
Árvores Trie e Patricia (III) 
l  Considerando as chaves como sequência de bits (M 
= 2), o algoritmo de pesquisa digital é semelhante 
ao de pesquisa em árvore binária, exceto que 
caminha-se na árvore de acordo com os bits de 
chave 
-  Ex. (chaves de 6 bits) 
L
N
C
C 
Árvores Trie e Patricia (IV) 
l  Inserção de novas chaves na Trie binária: 
-  Caso 1: busca pela nova chave interrompida em um nó 
interno; cria-se novo nó folha abaixo desse nó interno 
l  Ex.: W = 110110 
-  Caso 2: busca pela nova chave interrompida em um nó 
folha; cria-se nós internos cujos descendentes conterão a 
chave já existente e a nova chave 
l  Ex.: K = 100010 
L
N
C
C 
Árvores Trie e Patricia (V) 
l  O formato das Tries binárias, diferentemente das 
árvores binárias comuns, não depende da ordem 
em que as chaves são inseridas e sim da estrutura 
das chaves através da distribuição de seus bits 
l  Desvantagem: 
-  Formação de árvores degeneradas para chaves com um 
grande número de bits em comum 
l  Ex. (caminho gerado 
pelas chaves B e C): 
L
N
C
C 
Árvores Trie e Patricia (VI) 
l  Patricia (Practical Algorithm to Retrieve Information 
Coded In Alphanumeric) – problema dos caminhos 
de uma só direção eliminado através da inserção, 
em cada nó interno da árvore, do índice do bit a ser 
testado para decidir qual ramo da árvore tomar 
-  Ex.: 
0 1 
1 1 
1 
0 
0 
0 
L
N
C
C 
Árvores Trie e Patricia (VII) 
0 1 
1 1 
1 
0 
0 
0 
1 0 
0 
0 
0 1 
1 
1 
1 0 
0 
0 1 
1 
l  Inserção de novas chaves na árvore Patricia: 
-  Caso 1: chave no nó folha de parada no nível i tem mesmo prefixo de 
comprimento x ≥ i que nova chave (ex.: K = 100010; i = 3, x = 4) 
 
 
 
 
 
 
-  Caso 2: chave no nó folha de parada no nível i tem mesmo prefixo de 
comprimento x < i que nova chave (ex.: W = 110110; i = 5, x = 1) 
0 1 
1 1 
1 
0 
0 
0 
1 0 
K = 100010 
5 
0 1 
1 1 
1 
0 
0 
0 
J = 100001 
3 
L
N
C
C 
Tabelas de dispersão (I) 
l  Tabelas “hash” – registros armazenados em uma tabela 
(ex.: vetor) são diretamente endereçados a partir de uma 
transformação aritmética da chave de pesquisa em um 
índice para a tabela(ex.: posição do registro no vetor) 
-  Tempo de resposta: ≈ constante (!) 
-  Ex.: 
L
N
C
C 
Tabelas de dispersão (II) 
l  TAD “Hash” em C (chave de pesquisa é inteiro e 
tabela é representada por um vetor de ponteiros): 
-  Estrutura: 
 
 
 
 
 
 
-  Operações básicas: 
l  Registry* hash_get(Hash tab, int key); 
l  Registry* hash_put(Hash tab, int key, ... /* outras infos */); 
struct registry { 
 int key; 
 ... /* informações do registro */ 
}; 
typedef struct registry Registry; 
 
#define M 193 
typedef Registry* Hash[M]; /* lê-se: array com M elementos do tipo ponteiro para Registry!!! */ 
L
N
C
C 
Tabelas de dispersão (III) 
l  Transformação aritmética de duas chaves distintas 
pode levar a um mesmo índice: colisão 
-  Assume-se transformações aritméticas como “funções 
não injetoras”, senão a tabela teria que ser 
extremamente grande 
-  Desse modo, mesmo que se use uma função de 
transformação que distribua os registros uniformemente 
entre as entradas da tabela, 
colisões fatalmente ocorrem 
e têm de ser resolvidas de 
alguma forma 
l  Ex.: chave 26 
L
N
C
C 
Tabelas de dispersão (IV) 
l  Propriedades desejáveis da função de 
transformação: 
-  ser eficientemente avaliada (para tempo de resposta 
constante e rápido) 
-  “dispersar” bem as chaves de busca (para minimizar 
colisões) – daí “função de dispersão” (ou “função hash”) 
 
l  A probabilidade p de se inserir N itens consecutivos 
sem colisão em uma tabela de tam. M é: 
-  Paradoxo do 
aniversário (Feller,1968): 
l  Para N = 23 e M = 365, p ≈ 0.49 
l  Para N=23 e M=23, p=0,000000001238096 
l  Para N=37 e M=37, p=0,000000000000001 
L
N
C
C 
Tabelas de dispersão (V) 
l  Função hash mais comum (método da divisão): 
 h(K) = K mod M, 
onde K é a chave e M o tamanho da tabela 
-  Para essa função, recomenda-se que M seja número 
primo distante de potências de 2 
l  Senão, as chaves com padrões de bits/dígitos semelhantes nos 
bits/dígitos menos significativos tendem a ser mapeadas para a 
mesma posição (colisão) 
 
 
 
l  Há, claro, alternativas: 
-  Método da multiplicação 
-  Funções hash universais 
32 64 53
64 128 97
128 256 193
...
Potência de 2
lower bound
Potência de 2
upper bound
Número 
primo
static int hash( int key ) { 
 return key % M; 
} 
L
N
C
C 
Tabelas de dispersão (VI) 
l  Como as transformações sobre chaves são 
aritméticas, deve-se transformar chaves não-
numéricas em números 
-  Ex.: 
 
 
l  n: número de caracteres da chave 
l  chave[i]: código de caractere (ASCII, Unicode etc.) do i-ésimo 
caractere da chave 
l  p[i]: pesos gerados aleatoriamente para 0 ≤ i ≤ n – 1 
-  Dois conjuntos de pesos p1 e p2 geram funções hash h1 e h2 diferentes 
L
N
C
C 
Tabelas de dispersão (VII) 
l  Independente da qualidade da função hash, taxa de 
ocupação da tabela não deve: 
 
-  ser muito alta (> 75%), para evitar colisões e manter 
eficiência da busca 
 
-  ser muito baixa (< 25%), para evitar desperdício de 
memória na tabela 
 
l  Estratégias de expansão/redução da tabela podem 
ser usadas, mas seu custo computacional depende 
das estratégias de tratamento de colisão adotadas 
L
N
C
C 
Tabelas de dispersão (VIII) 
l  Estratégias mais comuns para tratamento de 
colisão: 
 
-  Encadeamento separado: cada elemento da tabela 
representa um ponteiro para uma lista encadeada, onde 
os registros são armazenados 
 
-  Endereçamento aberto: registros podem ser 
armazenados diretamente na tabela 
 
-  Hash coalescente: estratégia híbrida 
L
N
C
C 
Tabelas de dispersão (IX) 
l  Encadeamento separado: 
 
-  Cada registro armazenado na tabela hash será um nó de 
uma lista encadeada 
 
-  Registros devem prever um ponteiro adicional para o 
próximo nó da lista 
struct registry { 
 int key; 
 ... /* outras infos */ 
 struct registry* next; 
}; 
typedef struct registry Registry; 
L
N
C
C 
Tabelas de dispersão (X) 
l  Encadeamento separado: 
Registry* hash_put(Hash tab, int key, ... /* outras infos */) { 
 int h = hash(key); 
 Registry* r = tab[h]; 
 while(r != NULL ) { 
 if(r->key == key) break; 
 r = r->next; 
 } 
 if (r==NULL) { /* não encontrou o elemento */ 
 /* insere novo elemento no início da lista */ 
 r = (Registry*) malloc(sizeof(Registry)); 
 r->key = key; 
 r->next = tab[h]; 
 tab[h] = r; 
 } 
 /* atribui ou modifica informação */ 
 ... 
 return r; 
} 
Registry* hash_get(Hash tab, int key) { 
 int h = hash(key); 
 Registry* r = tab[h]; 
 while(r != NULL ) { 
 if(r->key == key) break; 
 r = r->next; 
 } 
 return r; 
} 
L
N
C
C 
Tabelas de dispersão (XI) 
l  Endereçamento aberto: 
 
-  Útil quando o número de registros a armazenar na tabela 
puder ser previamente estimado 
 
-  Hash linear: uso da primeira posição consecutiva livre na 
tabela hash 
 
-  Hash duplo: uso de uma segunda função hash para 
determinar posição livre 
L
N
C
C 
Tabelas de dispersão (XII) 
l  Hash linear: se houver colisão, é procurado o 
próximo índice livre da tabela (usando incremento 
circular) para armazenar o novo elemento 
L
N
C
C 
Tabelas de dispersão (XIII) 
l  Hash linear: 
Registry* hash_put(Hash tab, int key, ... /* outras infos */) { 
 int h = hash(key); 
 while (tab[h] != NULL) { 
 if (tab[h]->key == key) 
 break; 
 h = (h+1) % M; 
 } 
 if (tab[h]==NULL) {/* não encontrou o elemento */ 
 tab[h] = (Registry*) malloc(sizeof(Registry)); 
 tab[h]->key = key; 
 } 
 /* atribui/modifica informação */ 
 ... 
 return tab[h]; 
} 
Registry* hash_get(Hash tab, int key) { 
 int h = hash(key); 
 while (tab[h] != NULL) { 
 if (tab[h]->key == key) 
 return tab[h]; 
 h = (h+1) % M; 
 } 
 return NULL; 
} 
L
N
C
C 
Tabelas de dispersão (XIV) 
l  Hash linear sofre de um problema chamado agrupamento 
(clustering) (Knuth, 1973), que piora à medida que a taxa de 
ocupação aumenta 
 
l  Hash duplo: se houver colisão, 
é procurada uma posição livre 
na tabela com incrementos 
dados por uma segunda 
função hash h’(k) 
-  em lugar de 
tentar-se (h(k)+1) mod M, 
tenta-se (h(k)+h’(k)) mod M 
-  Ex.: h'(k) = (M-2) - k mod (M-2) 
static int hash2 (int key) { 
 return M - 2 - key%(M-2); 
} 
Registry* hash_get(Hash tab, int key) { 
 int h = hash(key); 
 int h2 = hash2(key); 
 while (tab[h] != NULL) { 
 if (tab[h]->key == key) 
 return tab[h]; 
 h = (h+h2) % M; 
 } 
 return NULL; 
} 
L
N
C
C 
Tabelas de dispersão (XV) 
l  Cuidados na escolha da segunda função hash: 
-  Nunca pode retornar zero, pois isso não faria com que o 
índice fosse incrementado 
-  No caso de função baseada no método da divisão, não 
deve retornar um número divisor da dimensão da tabela, 
pois isso limitaria a procura de uma posição livre a um 
subconjunto restrito dos índices da tabela 
l  Se a dimensão da tabela for um número primo, garante-se 
automaticamente que o resultado da função não será um divisor 
L
N
C
C 
Tabelas de dispersão (XVI) 
l  Hash coalescente: usa uma técnica similar ao 
encadeamento separado, mas ao invés de alocar 
novos nós em uma lista encadeada separada por 
entrada na tabela, são usadas essas próprias 
entradas como nós no encadeamento 
-  Compromisso entre eficiência na busca e ocupação de 
memória 
L
N
C
C 
Tabelas de dispersão (XVII) 
l  Hash 
coalescente: 
 
-  No exemplo, 
procura-se 
primeira posição 
livre 
 
-  E hash_get()? 
Registry* hash_put(Hash tab, int key, ... /* outras infos */) { 
 int h = hash(key); 
 int cursor = 0; 
 if(tab[h] == NULL) { 
 cursor = h; 
 tab[cursor] = (Registry*) malloc(sizeof(Registry)); 
 } 
 else { 
 Registry *r = tab[h]; 
 /* procura próx. entrada livre */ 
 while (cursor < M && tab[cursor] != NULL) ++cursor; 
 /* se tabela está cheia, retorna NULL */ 
 if(cursor == M) return NULL; 
 tab[cursor] = (Registry*) malloc(sizeof(Registry)) 
 /* Procura último nó na lista e aponta para o mesmo */ 
 while(r->next != NULL) r = r->next;r->next = tab[cursor]; 
 } 
 /* atribui/modifica informação na posição “cursor” */ 
 ... 
 return tab[cursor]; 
} 
L
N
C
C 
Tabelas de dispersão (XVIII) 
l  Tabelas hash podem ser usadas na representação 
de matrizes esparsas: 
l  Basta definir uma função hash(int i, int j, …) 
 
l  Problema com tabelas hash: 
l  Custo computacional potencialmente alto para: 
l  recuperar os registros na ordem lexicográfica das chaves 
l  remover itens da tabela (em particular, nos casos de hash linear, 
duplo e coalescente) 
l  Redução da “localidade de referência” 
l  Dispersão dos registros impede ganhos de desempenho 
associados ao uso de memória cache (como em operações com 
matrizes esparsas, p.ex. multiplicação) 
L
N
C
C 
Tabelas de dispersão (XIX) 
l  Hash perfeito 
-  Função que permite construção de tabela sem colisões 
-  Possível se o conjunto de chaves for pré-determinado 
l  Para cada conjunto de chaves, uma função hash perfeita 
específica é necessária 
-  Problema passa a ser obter a função hash perfeita! 
l  Complicadores: hash perfeito mínimo (N=M) e com ordem 
lexicográfica preservada (k1 < k2 implica h(k1) < h(k2)) 
l  Campo fértil para pesquisas...