Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets e Dicionários - Coggle Diagram
Sets e Dicionários
Set: uma coleção desordenada (pode ser vazia) de elementos
Operações
Verificar se um elemento pertence
Achar a união e a interseção de dois sets
Não podem ter elementos repetidos (bag e multiset pra contornar)
Pode ser explícita ou apresentar uma propriedade que os elementos tem que satisfazer
Mudar a ordem dos elementos não muda o set
Implementações
Usar a estrutura de lista pra representar
os elementos
Subsets de um set maior (set universal)
Bit vector: só é 1 se o elemento do
universal estiver incluído
Pode usar muito armazenamento, mas é rápido
Operações realizadas no set são implementadas
por dicionários
Operações
Procurar
Inserir
Deletar
Hashing: distribuir chaves pra elementos num array unidimensional (hash table)
Open Hashing: chaves são armazenadas numa
lista ligada atrelada às células do hash table
Load factor (chaves/células)
(melhor próximo de 1)
Inserção no final da lista
(geralmente)
Busca: checa a chave da palavra buscada e
depois na lista daquela célula
Deletar: buscar a chave e retirar
da lista
Closed Hashing: chaves são armazenadas na
própria hash table
Deletar: substituir o valor retirado por um símbolo
especial
Sondagem linear em caso de colisão
Inserção na célula da chave ou na próxima vazia
(ideia de array circular)
Busca: acha a posição com a função e procura
até célula vazia ou achar a chave
Clusters (aglomerações): muitas células juntas
ocupadas
Double hashing pra evitar
Rehashinh: escanear o table cheio e passar pra
um maior
As chaves devem ser o mais uniforme possível
Hash function deve ser fácil de computar
Tamanho do hash table não deve ser muito maior
que o número de chaves, mas não deve
comprometer o tempo de implementação
Colisão: quando duas chaves ocupam a
mesma célula no hash table