Please enable JavaScript.
Coggle requires JavaScript to display documents.
sets and dictionaries - Coggle Diagram
sets and dictionaries
sets
coleção desordenada ou vazia de elementos distintos
operações
procurar um elemento
união
intercessão
pode ser uma lista ou uma propriedade comum dos elementos do set
implementação
usar um subset de um set universal
bit string/bit vector
usar a estrutura de uma lista
dicionários
operações
searching/busca
adding/adição
deleting/deleção
chapter 7: hashing
usado na implementação de dicionários
key/chaves
identificador da identidade usada
distribuimos as chaves em arrays
(hash tables)
para cada chave temos uma função "hash function"
requesitos
o array não deve ter um tamanho ideal
a distribuição das chaves deve ser o mais uniforme possível
deve ser fácil de calcular
open hashing
as chaves são guardadas em listas encadeadas e cada uma se liga a uma célula
load factor
alfa = n/m
s = 1 + (alfa/2)
u = alfa
closed hashing
linear probing
conferimos se a célula está ocupada, se estiver conferimos a seguinte até achar uma vazia
searching
procuramos a chave
2 more items...
deletion
usar algo para diferenciar as células vazias da que já foram ocupadas antes
load factor
alfa = m/n
2 more items...
clusters
proclema decorrente de conjuntos de células muito ocupadas
soluções
2 more items...