Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets e Dictionaries, Hashing, Space and time trade-offs - Coggle Diagram
Sets e Dictionaries
-
Dictionaries (dicionários): É uma estrutura de dados que implementa três operações: as operações que precisamos realizar para um conjunto ou multiconjunto geralmente são pesquisar um determinado item, adicionar um novo item e excluir um item da coleção.
Existem várias maneiras de implementar um dicionário. Eles variam de um uso não sofisticado de arrays (classificados ou não) a técnicas muito mais sofisticadas, como hash e árvores de pesquisa balanceadas.
Hashing
-
O hash é baseado na ideia de distribuir chaves entre uma matriz unidimensional H [0..m - 1] chamada de tabela hash. A distribuição é feita calculando, para cada uma das chaves, o valor de alguma função predefinida 'h' chamada de função hash. Esta função atribui um número inteiro entre 0 e m - 1, denominado endereço hash, a uma chave.
O tamanho da 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. (Este requisito torna desejável, para a maioria dos aplicativos, ter uma função hash dependente de todos os bits de uma chave, não apenas de alguns deles.)
-
se escolhermos o tamanho m de uma tabela de hash para ser menor do que o número de chaves n, teremos colisões - um fenômeno de duas (ou mais) chaves sendo hash na mesma célula da tabela de hash
todo esquema de hashing deve ter um mecanismo de resolução de colisão. Esse mecanismo é diferente nas duas versões principais de hashing: hashing aberto (também chamado de encadeamento separado) e hashing fechado (também chamado de endereçamento aberto).
No hashing aberto, as chaves são armazenadas em listas vinculadas anexadas às células de uma tabela de hash. Cada lista contém todas as chaves com hash para sua célula.
No hashing fechado, todas as chaves são armazenadas na própria tabela de hash sem o uso de listas vinculadas.
-