Hash Table: Estrutura de Dados

Prévia do material em texto

Monitoria de Algoritmos
Hash Table6
Hash Table
◇ Hash Table é uma estrutura de dados especial, que 
associa chaves de pesquisa a valores
◇ Seu objetivo é, a partir de uma chave simples, fazer 
uma busca rápida e obter o valor desejado
◇ São tipicamente usadas para indexação de grandes 
volumes de informação (como bases de dados)
Hash Table
◇ A implementação típica busca uma função de 
dispersão que seja de complexidade O(1), não 
importando o número de registros na tabela 
(desconsiderando colisões)
◇ O ganho com relação a outras estruturas 
associativas (como um vetor simples) passa a ser 
maior conforme a quantidade de dados aumenta
Hash Table
Fator de Carga
◇ À medida que o fator de carga aumenta, a hash 
table torna-se mais lenta e pode até não funcionar 
(dependendo do método usado). A propriedade de 
tempo constante, esperada de uma hash table, 
pressupõe que o fator de carga é mantido abaixo de 
algum limite. Para um número fixo de buckets, o 
tempo de busca cresce com o número de entradas e, 
portanto, o tempo constante desejado não é 
alcançado.
Fator de Carga
◇ Em segundo lugar, pode-se examinar a variância do 
número de entradas por bucket. Por exemplo, duas 
tabelas possuem 1000 entradas e 1000 buckets; um 
tem exatamente uma entrada em cada balde, o 
outro tem todas as entradas no mesmo balde. 
Claramente, o hash não está funcionando no 
segundo.
Fator de Carga
◇ Um fator de carga baixo não é especialmente 
benéfico. À medida que o fator de carga se 
aproxima de 0, a proporção de áreas não utilizadas 
na hash tabela aumenta, mas não há 
necessariamente qualquer redução no custo de 
busca. Isso resulta em memória desperdiçada.
Fator de Carga
Open Hashing
Closed Hashing
Busca em ED Lineares7
Busca Linear
Busca Binária