Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hash, Conjuntos, Trade-offs de Espaço e Tempo, Se eu tentar inserir um…
Hash
Conjuntos
Operações mais importantes:
Verificar a associação de um determinado item em um determinado conjunto (uma espécie de busca)
Encontrar a união entre dois conjuntos
Encontrar a intersecção entre dois conjuntos
Pode ser representado de duas formas: Mostrando os elementos do conjunto ou com uma propriedade (ou mais) que somente os elementos do conjunto que se encaixam
S = {1, 3, 5, 7, 9}
S = {n : n é um número ímpar menor que 10}
Existem dua formas de representar os conjuntos computacionalmente:
Considerando que existe um conjunto U (com n elementos) que é o universo e que S é um subconjunto de U, então podemos representar s como uma string binaria de tamanho n
Por exemplo: se U = {1, 2, 3, 4, 5, 6, 7, 8, 9} e S(que é um subconjunto de U) = {2, 4, 6}, então podemos representar S como 010101000
Caso S=U então a representação seria: 111111111
Caso S ={1}, seria 100000000
Embora essa forma faça com que o computador realize os métodos de maneira muito eficiente, isso pode ser muito custoso em relação à memória
Utilizando uma estrutura de lista
Porém é necessário saber a diferença entre um conjunto e uma lista
Uma lista pode conter elementos iguais e é ordenada
Um conjunto não pode conter elementos iguais e é desordenado
Porém, podemos alterar a ordem de um conjunto por algum motivo (como ajudar na busca), mas isso não vai mudar o conjunto
As operações mais usadas na computação são: Busca (procura por um elemento em um conjunto), inserção e remoção
Dicionário
É a estrutura de dados que implementa esses métodos
É uma coleção de valores (é a estrutura de dados que implementa o conceito de conjunto)
É uma coleção desordenada (ordem não importa) de diferentes elementos (uma coleção vazia pode ser um conjunto) e para a computação vão ser na maioria das vezes finitos (para não dizer sempre)
Trade-offs de Espaço e Tempo
Aprimoramento de entrada
É quando o computador vai armazenado dados de um problema para
que quando precisar do valor novamente não seja necessário calculá-lo, apena consultá-lo
Existem dois algoritmos famosos baseado nessa ideia
Métodos de contagem para classificação
Algoritmo de Boyer-Moore para correspondência de strings e sua versão simplificada sugerida por Horspool
Pré-estruturação
É a utilização de espaço extra para facilitar e/ou acelerar o acesso aos dados
Esse abordagem é mostrada em:
Hashing
Hashing
Hashing é basicamente distribuir chaves por um array (uni-dimensional), esse array é chamado de Tabela Hash
Em um registro (um conjunto de informações como um registro estudantil que contêm varias informações sobre o estudante) temos uma chave, que a informação que é a principal em determinada circunstância (é a informação que vai ser responsável pela ordenação)
Essa distribuição é feita através de um função h, chamada de Função Hash, que retorna um inteiro entre 0 e m-1 que é chamado de Endereço Hash (de uma chave), onde m é o tamanho do array
Por exemplo:
Se a chave for um inteiro não negativo, então a função pode ser do tipo:
1 more item...
Se a chave for um caractere de um certo alfabeto, então a função pode ser do tipo:
1 more item...
Se a chave for uma cadeia caracteres de um certo alfabeto, então a função pode ser do tipo:
1 more item...
Um função Hash deve satisfazer alguns requisitos para evitar conflitos
O tamanho de uma tabela hash não deve ser excessivamente grande em comparação com o número de chaves, mas deve ser suficiente para não comprometer a eficiência de tempo da implementação
Uma função hash precisa distribuir as chaves entre as células da tabela hash da maneira mais uniforme possível. (para que isso aconteça é desejável usar a maior quantidade possível de informações da chave)
Uma função Hash tem que ser fácil de ser computada
Podem haver colisões na tabela Hash (se os requisitos forem cumpridos, as colisões serão mais raras, mas podem acontecer mesmo assim) e para isso precisam haver mecanismos de correção de colisões
Colisões são quando duas ou mais chaves são armazenadas no mesmo endereço Hash
Os mecanismos são diferenciados para cada um dos dois principais tipos de Hashing:
Hashing aberto
As chaves são armazenadas em listas ligadas, que por sua vez, são armazenadas em posições da tabela Hash
1 more item...
Hashing Fechado
As chaves são armazenadas na tabela Hash, não em listas ligadas associadas aos endereços da tabela, para que isso seja possível a tabela Hash tem que ter o tamanho m maior ou igual ao número de chaves n
2 more items...
indexando com árvores B
Outra Técnica é a Programação Dinâmica, porém só será estudada em breve
Nem sempre Espaço e Tempo vão ir um contra o outro é possível (para alguns problemas) desenvolver soluções em que ambos sejam minimizados
Se eu tentar inserir um elemento e houver colisão eu vou somar a posição que deu colisão e vou somar ao offset, então se após essa soma a posição está vazia eu insiro, se não eu somo 1 ao offset, ou seja, o offset é a distância entre a posição da colisão e a próxima posição vazia