Please enable JavaScript.
Coggle requires JavaScript to display documents.
Implementação de Dicionários - Coggle Diagram
Implementação de Dicionários
Hashing
Hashing é baseado na ideia de distribuir keys, que são usadas para identificação, em um array unidimensional H[0...m − 1] chamado de hash table
A distribuição é feita ao computar, para cada uma das keys, o valor de alguma função predefinida h chamada de função hash. Ela atribui um inteiro entre 0 e m − 1, chamado de endereço hash, para a key.
Por exemplo, se as keys são inteiros não negativos, a função hash pode ser da forma h(K) = K mod m
Se escolhermos um tamanho m pra hash table’s que é menor que o número n de keys, teremos colisões, um fenômeno em que duas ou mais keys são postas na mesma célula da tabela hash.
. Mas colisões são esperadas mesmo se m for consideravelmente maior que n. Logo, cada esquema de hash
deve ter um mecanismo para resolver colisões. Que é diferente nas duas principais versões do hashing: open hashing e closed hashing.
Open Hashing
Keys são armazenadas em listas encadeadas ligadas as células de uma tabela hash. Cada lista contém todas as keys hasheadas a suas células.
Closed Hashing
Todas as keys são armazenadas na tabela hash sem o uso de listas encadeadas
Sets e Dicionários
Sets
Um set pode ser descrito como uma coleção desordenada (possivelmente vazia) de itens distintos chamados de elementos do set.
As operações mais importantes do set são: checar se um dado item pertence ao set, encontrar a união de dois sets, e encontrar a interseção de dois sets,
Sets podem ser implementados de duas formas. A primeira considera apenas sets que são subsets de algum set maior U, chamado de universal.
A segunda, e mais comum, é usar a estrutura da lista para indicar os elementos do set
Dicionários
Procura um dado elemento, adicionar um novo item, e deletar um item, são as operações que a estrutura de dados chamada dicionário executa.
Uma implementação eficiente de um dicionário deve ter compromisso entre eficiência de busca das outras duas operações.
Há algumas formas de implementar um dicionário. Um exemplo é através de hashes