Please enable JavaScript.
Coggle requires JavaScript to display documents.
Conjuntos e dicionários, Hashing - Coggle Diagram
Conjuntos e dicionários
-
Um conjunto é definido por uma lista específica de elementos ou por uma propriedade específica que devem satisfazer todos os elementos do conjunto
-
O subconjunto de um conjunto U de tamanho n chamado S pode ser representado por uma string de tamanho n chamada vetor de string, onde a i-ésima posição é igual a 1 se o elemento existir em S e 0 caso contrário
-
Hashing
Tratamento de colisões:
Sondagem linear - Se a posição direcionada estiver ocupada ele checa a próxima até achar uma livre (caso chegue a última posição passa para a primeira)
Dispersão dupla - É usada uma outra função de dispersão para determinar um incremento fixo que será utilizado na primeira função para determinar sua posição caso haja colisão
O único divisor comum entre a função de incremento e o tamanho da tabela deve ser 1 (o que satisfaz automaticamente se m for primo)
A performance também se deteriora quando a tabela começa a ficar muito cheia, a solução é o rehashing, onde a tabela é escaneada e as chaves são realocadas numa tabela de tamanho maior
Open hashing (separate chaining) - As chaves são guardadas em listas encadeadas vinculadas as células da tabela de dispersão
Se uma função distribui n chaves em m espaços em uma tabela de dispersão as listas devem ter no máximo tamanho n/m, essa razão é chamada de fator de carregamento, que é fundamental para garantir a eficiência da dispersão
É baseado na ideia de distribuir uma chave ao longo de um vetor unidimensional H[0...m-1] chamado tabela de dispersão
A distribuição é feita por uma função predefinida chamada de função de dispersão e essa função atribui um inteiro de 0 a m-1 chamado de endereço da dispersão a uma chave
Uma tabela de dispersão não pode ser muito maior que o número de chaves mas tem que ser o suficiente para não comprometer a eficiência do tempo de implementação
-
-
Obviamente se o tamanho da tabela de dispersão for menor que o número de chaves vão haver colisões, mas colisões também são esperadas mesmo se o tamanho da tabela de dispersão for maior que o de chaves
Closed hashing (open addressing) - Todas as chaves são guardadas na tabela de dispersão, não existem listas encadeadas
Clustering - Acontece quando uma tabela de dispersão está perto de ficar cheia e para inserir uma chave há uma sequência grande de espaços ocupados
Hashing possui tempo O(1) no caso médio e O(n) nos piores casos, BST possui tempo O(log(n)) para os médios e piores casos