Please enable JavaScript.
Coggle requires JavaScript to display documents.
Conjuntos e dicionários - Coggle Diagram
Conjuntos e dicionários
implementação de conjuntos em computadores
conjunto universal (conjunto U)
vetor de bits: subconjuntos de U representados por strings de bits de tamanho n
utilização de listas
distinções
unicidade dos elementos
multiconjuntos ou sacos
ordenação dos elementos
geração de tipos de dados abstratos (ADTs)
classes
operações com conjuntos
dicionário
métodos de implementação
hashing
arrays
árvores de busca
problema da união de conjunto
trocas de tempo e espaço
aprimoramento de input
métodos de contagem para ordenação
algoritmo de Boyer-Moore para comparação de strings
pré-estruturação
hashing
indexação com árvores binárias
programação dinâmica
hashing
chave: elemento usado para identificar entidades representadas no registro
distribuição de chaves em um array unidimensional, chamado
tabela hash
função hash: função utilizada para a distribuição das chaves na tabela
requerimentos
o tamanho de uma tabela hash não deve ser muito grande, mas deve ser o bastante para não comprometer a eficiência de tempo da implementação
uma função deve distribuir chaves entre as células da tabela hash o mais uniforme possível
uma função hash deve ser fácil de computar
endereço hash: valor atribuído a uma chave pela função hash
colisão: quando uma ou mais chaves são colocadas na mesma célula da tabela
hashing aberto (encadeamento separado)
chaves armazenadas em listas ligadas anexas às células de uma tabela hash
fator de carregamento: razão entre o número de chaves e de células da tabela
indicativo da eficiência do algoritmo
hashing fechado (endereçamento aberto)
chaves armazenadas diretamente na própria tabela
sondagem linear: se há colisão, a célula seguinte é checada e assim por diante até encontrar uma célula disponível para armazenar a chave ou atingir o final da tabela
aglomerados: sequência de células ocupadas
deterioram a eficiência do algoritmo
double hashing: aplicação de uma segunda função hash
rehashing: a tabela tem todas suas chaves realocadas em uma tabela maior
eficiência de tempo assintótica: constante em casos médios e linear no pior caso improvável