Please enable JavaScript.
Coggle requires JavaScript to display documents.
CONJUNTOS E DICIONÁRIOS, TROCA ENTRE ESPAÇO E TEMPO - Coggle Diagram
CONJUNTOS E DICIONÁRIOS
Conjuntos
Uma coleção não-ordenada de elementos distintos, podendo ser, inclusive, vazia
Operações mais importantes:
Checar se um determinado item pertence a um determinado conjunto
Achar a união de dois conjuntos
Achar a interseção entre os conjuntos
2 maneiras de implementar
Primeira
Considera apenas conjuntos que são subconjuntos de um conjunto maior
U
, que é o
conjunto universo
Se um conjunto U tem \(n\) elementos, então qualquer subconjunto S de U pode ser representado por uma cadeia de bits 0 ou 1 de tamanho \(n\)
O \(i\)-ésimo elemento é 1 se, e somente se, o \(i\)-ésimo elemento de U está incluído em S
Ex: U = {1,2,3,4,5,6,7,8,9} e S = {2,3,5,7}
S é representado pela cadeia de bits 011010100
Permite implementar as operações básicas de forma rápida, mas usando mais espaço de armazenamento que o necessário
Segunda e mais comum
Usar uma estrutura de lista para indicar os elementos do conjunto
Apenas para conjuntos finitos
2 principais pontos de distinção entre conjuntos e listas
Um conjunto não pode conter elementos iguais enquanto que uma lista pode
Como um conjunto é uma coleção de elementos não-ordenados, mudar elementos de posições não muda o conjunto
Uma lista muda caso a ordem de seus elementos seja mudada
Dicionários
É uma estrutura de dados que implementa as 3 operações básicas para conjuntos: procurar por um elemento, inserir um elemento e deletar um item
HASHING
Maneira muito eficiente de implementar dicionários
Os elementos desse conjunto são de natureza arbitrária
Geralmente usados para registrar coisas, tais como o registro estudantil em uma escola, já que ele contém vários campos, cada um com uma informação específica
Chaves
são o que identificam cada campo de um determinado dicionário
Um dicionário com \(n\) campos possui \(n\) chaves
Baseia-se na ideia de distribuir as chaves em um array unidimensional, chamado de tabela hash
A distribuição é feita ao computar uma função \(h\), chamada função hash, para cada chave
A Função hash atribui um valor inteiro de 0 a \(m-1\) a cada chave, chamado de
endereço hash
, onde \(m\) é o tamanho da tabela hash
No geral,
uma função hash precisa satisfazer os seguintes critérios
:
O tamanho de uma tabela hash não deve ser muito maior comparado ao número de chaves, mas deve ser suficiente para não prejudicar a eficiência temporal da implementação
Uma função hash deve distribuir as chaves entre as células da tabela hash da forma mais igual possível
Deve ser fácil de computar
Colisões
acontecem se escolher o tamanho da tabela hash menor que o número de chaves
Duas ou mais chaves em apenas uma célula da tabela
Colisões sempre devem ser esperadas
e é importante ter mecanismos para lidar com elas
Mecanismos
Hashing aberto (encadeamento separado)
As chaves são armazenadas em listas ligadas conectadas às células da tabela hash
Cada lista possui todas as chaves que foram adicionadas à ela pela função hash
Permite colisões armazenando os valores que colidiram em uma lista ligada
Operação de busca
Computar o valor da função hash para essa chave, checar se ele existe na tabela e, depois, verificar se a chave está na lista ligada correspondente
A eficiência da pesquisa depende do tamanho da lista, o qual depende do tamanho do dicionário e da tabela, além da qualidade da função hash
Número médio de ponteiros passados
Pesquisas com sucesso
\(S\approx1+\frac{\alpha}{2}\)
Pesquisas sem sucesso
\(U=\alpha\)
Se a função distribui as \(n\) chaves dentre as \(m\) células da tabela de forma igual ou parecida, é esperado que cada lista tenha, aproximadamente, o tamanho sendo \(\alpha = n/m\)
Essa razão \(\alpha\) é chamada de
fator de carga
da tabela hash
Operação de inserção
Geralmente ocorre no final de uma lista
Operação de deletar
Buscar por uma chave e removê-la da lista
Todas as operações são \(\Theta(1)\) para o caso médio em que o número de chaves \(n\) é praticamente igual ao número de células da tabela \(m\)
Hashing fechada (endereçamento aberto)
Todas as chaves são armazenadas na tabela, sem o uso de listas ligadas
O tamanho da tabela \(m\) deve ser, pelo menos, tão grande quanto o número de chaves \(n\)
A
estratégia
mais simples para lidar com
colisões
é a
sondagem linear
Verifica a célula após a célula da tabela na qual ocorreu a colisão
Se ela estiver vazia, a nova chave é colocada nela
Se ela estiver ocupada, então a próxima célula é verificada e esse processo continua até ser possível colocar a nova chave ou até acabarem as células
A tabela é tratada como um array circular porque, ao chegar no final da tabela, a pesquisa passa direto para o início
Operação de busca
Computar a função hash em função da chave procurada
Se a célula estiver vazia, então a busca não foi bem sucedida
Se ela não estiver vazia, ainda é preciso comparar a chave buscada com a chave que ocupa a célula
Se elas forem iguais, então a busca acaba
Se não, a busca continua comparando a chave na próxima célula até que as chaves sejam iguais ou até encontrar uma célula vazia
Operação de inserção
É uma operação direta
Operação de deletar
Não é uma operação direta
Em uma tabela com chaves iguais, deletar uma chave da tabela cujo resultado da função hash é o mesmo que outra chave impossibilita que a chave restante seja achada
Eliminação perigosa
Marcar locais ocupados anteriormente com um símbolo especial para diferenciá-las de locais que ainda não foram ocupados
Conforme a tabela hash enche, a
performance da sondagem linear diminui
por conta do
agrupamento
Um
grupo
é uma sequência de células ocupadas contiguamente
Torna as operações em um dicionário menos eficientes
Double hashing
Uma das estratégias para diminuir esse problema
Usar outra função hash para determinar um incremento fixo para a sequência de sondagem para ser usado após uma colisão
O incremento e o tamanho da tabela devem ser primos entre si
Outra solução
Rehashing
A tabela atual é escaneada e todas as suas chaves são realocadas em uma tabela maior quando a atual estiver ficando cheia
Comparação com árvores balanceadas
, que também servem para implementar dicionários
Eficiência temporal
Hashing
Busca, inserção e eliminação podem ser implementadas para tomar um tempo de \(\Theta(1)\), mas podendo chegar a \(\Theta(n)\) nos piores casos
Árvores balanceadas
\(\Theta(n)\) tanto para casos médios quanto para os piores casos
Preservação de ordem
Hashing
Não assume que exista uma ordem para as chaves
Menos adequadas para problemas que envolvem iterar sobre as chaves em ordem, por exemplo
TROCA ENTRE ESPAÇO E TEMPO
Pré-processar a entrada do problema ou em parte ou em sua totalidade e armazenar a informação adicional obtida
Acelerar a resolução do problema
Aprimoramento de entrada
Pré-estruturação
Outra técnica que explora a troca entre espaço e tempo
Usa espaço extra para facilitar o acesso mais rápido/flexível aos dados
Outra técnica para projetar algoritmos que utiliza essa ideia de trocar espaço pelo tempo é a
programação dinâmica
Armazenar soluções para subproblemas de um problema que se sobrepõem em uma tabela, da qual a solução para o próprio problema é obtida
Tempo e espaço não precisam competir em todas as formas de projetar algoritmos