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
Pode ser explícita ou apresentar uma propriedade que os elementos tem que satisfazer
Verificar se um elemento pertence
Achar a união e a interseção de dois sets
Operações
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
Implementações
Usar a estrutura de lista pra representar os elementos
Não podem ter elementos repetidos (bag e multiset pra contornar)
Mudar a ordem dos elementos não muda o set
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)
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
As chaves devem ser o mais uniforme possível
Hash function deve ser fácil de computar
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)
Deletar: buscar a chave e retirar da lista
Busca: checa a chave da palavra buscada e depois na lista daquela célula
Closed hashing: chaves são armazenadas na própria hash table
Sondagem linear em caso de colisão
Busca: acha a posição com a função e procura até célula vazia ou achar a chave
Inserção na célula da chave ou na próxima vazia (ideia de array circular)
Deletar: substituir o valor retirado por um símbolo especial
Clusters (aglomerações): muitas células juntas ocupadas
Double hashing pra evitar
Rehashinh: escanear o table cheio e passar pra um maior