Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Hashing, Sets, Dictionarie, Consequentemente, a…
Sets and Dictionaries
Hashing
Closed Hashing (Open Addressing)
tamanho da tabela m deve ser pelo menos tão
grande quanto o número de chaves n.
todas as chaves são armazenadas na própria tabela hash sem o uso
de listas vinculadas.
estratégias podem para resolução de colisão
sondagem linear
verifica a célula seguinte aquele onde ocorre a colisão. Se essa célula estiver vazia, a nova chave será instalada lá; se a próxima célula já estiver ocupada, a disponibilidade imediata dessa célula o sucessor é verificado e assim por diante.
Para procurar uma determinada chave K, começamos calculando h(K) onde h é a função hash usada na construção da tabela.
Se a célula h(K) estiver vazia, a busca não terá sucesso. Se a célula não estiver vazia, devemos comparar K com o ocupante da célula
se forem iguais, encontramos uma chave correspondente; se não forem, comparamos K com uma chave na próxima célula e continuamos dessa maneira até encontrarmos uma chave correspondente (uma pesquisa bem-sucedida) ou uma célula vazia (uma pesquisa malsucedida).
usar a “exclusão lenta”, ou seja, marcar os locais anteriormente ocupados com um símbolo especial para distingui-los dos locais que não foram ocupados.
Open Hashing (Separate Chaining)
as chaves(ites. EX: nome, endereço, etc.) são armazenadas em listas vinculadas anexadas às células de uma tabela hash.
Para pesquisamos em um dicionário implementado como uma tabela de listas vinculadas, simplesmente aplicamos a uma chave de pesquisa o mesmo procedimento usado para criar a tabela.
a eficiência da pesquisa depende do comprimento das listas vinculadas, que, por sua vez, dependem do tamanho do dicionário e da tabela, bem como da qualidade da função hash.
Se a função hash distribuir n chaves entre m células da tabela hash de maneira aproximadamente uniforme, cada lista terá cerca de n/m chaves.
A razão α = n/m, chamada de fator de carga da tabela hash, desempenha um papel crucial na eficiência do hash.
Em particular, o número médio de ponteiros (elos da cadeia) inspecionados em pesquisas bem-sucedidas, S, e em pesquisas malsucedidas, U, acaba sendo: S ≈ 1 + α /2 e U = α
As inserções são normalmente feitas no final de uma lista
A exclusão é realizada procurando uma chave a ser excluída e removendo-a de sua lista.
uma função hash precisa satisfazer requisitos
Uma função hash deve ser fácil de calcular.
O tamanho de uma tabela hash não deve ser excessivamente grande comparado ao número de chaves, mas deve ser suficiente para não comprometer a eficiência do tempo de implementação
se escolhermos que o tamanho m de uma tabela hash seja menor que o número de chaves n, teremos colisões – um fenômeno de duas (ou mais) chaves sendo criptografadas na mesma célula da tabela hash
Uma função hash precisa distribuir chaves entre as células da tabela hash da maneira mais uniforme possível.
Baseado na ideia de distribuição de chaves entre um array unidimensional H[0..m − 1] chamado tabela hash.
A distribuição é feita calculando, para cada uma das chaves, o valor de alguma função predefinida h chamada função hash. Esta função atribui um número inteiro entre 0 e m − 1, chamado endereço hash, a uma chave.
Forma muito eficiente de implementar dicionários.
todo esquema de hashing deve ter um mecanismo de resolução de colisão.
Sets
Operações comuns na computação usando conjuntos(sets)
procurar um determinado item
adicionar um novo item
excluir um item da coleção
Uma estrutura de dados que implementa essas três operações é chamada de dicionário(Dictionarie).
Operações de conjunto mais importantes
verificar a adesão de um determinado item a um determinado conjunto
encontrar a união de dois conjuntos, que compreende todos os elementos de um ou de ambos
encontrar a intersecção de dois conjuntos, que compreende todos os elementos comuns nos conjuntos.
Um conjunto específico é definido por uma listagem explícita de seus elementos ou pela especificação de uma propriedade que todos os elementos do conjunto e somente eles devem satisfazer
S = {n : n é um número primo menor que 10}) S = {2, 3, 5, 7})
Representação computacional
1
2
Usar a estrutura de lista para indicar os elementos do conjunto(finito).
conjunto != lista
Um conjunto não pode conter elementos idênticos; uma lista pode
Um conjunto é uma coleção não ordenada de itens; portanto, alterar a ordem dos seus elementos não altera o conjunto. Uma lista, definida como uma coleção ordenada de itens, é exatamente o oposto.
Considera conjuntos que são subconjuntos de algum conjunto U(universal), onde o elemento na posição i é representado por 1 <-> x e S.
U = {1, 2, 3, 4, 5, 6, 7, 8, 9} S = {2, 3, 5, 7}
Vetor de bits: 011010100
U é representado por uma sequência de bits de tamanho n(vetor de bits)
Implementa as operações de conjunto padrão muito rapidamente, mas utiliza uma grande quantidade de armazenamento.
Um conjunto é uma coleção não ordenada (possivelmente vazia) de itens distintos chamados elementos do conjunto.
Dictionarie
Implementações
Arrays
Hashing
árvores
implementação eficiente de um dicionário deve encontrar um compromisso entre a eficiência da pesquisa e a eficiência das outras duas operações.
Consequentemente, a eficiência dessas operações é idêntica à da pesquisa, e todas elas são (1) no caso médio se o número de chaves n for aproximadamente igual ao tamanho m da tabela hash.