Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets e Dicionários - Coggle Diagram
Sets e Dicionários
-
Sets
-
Em um set, os seus elementos não são repetidos, porém existe a estrutura multiset, que permite a existência de elementos idênticos em uma mesma coleção
Existem duas maneiras principais de representar um conjunto: vetor de bits e na forma de uma lista. O vetor de bits se utiliza de um conjunto universal para criar um array de bits onde 1 representa o pertencimento de tal elemento ao conjunto analisado e 0 o contrário.
Dentro da ADT do set, as funções utilizadas são procurar, adicionar e remover elementos e identificar a união ou interseção de conjuntos quaisquer.
Estrutura de dados que auxilia nas funções de inserção, remoção e identificação de elementos é o dicionário
Dicionários
Hashing
O hashing distribui chaves em um vetor unidimensional chamado hash table. Essas chaves são obtidas a partir de funções pré estruturadas, as hash functions. Essas funções atribuem um valor inteiro, hash adress, para cada chave
O conjunto pode ser de qualquer tipo: string, char, int, double etc
Uma função muito comum para valores inteiros é utilizar o mod, já que ele estabelece um limite de valores a serem obtidos
Colisões podem ocorrer quando duas chaves são associadas a um mesmo hash adress. Os métodos mais utilizados para superar esse problema são Open Hashing (Separate Chaining) e Closed Hashing(Open Adressing)
A Open Hashing associa uma linked list a cada endereço do hash, possibilitando o armazenamento de mais de uma chave por endereço.
Closed Hashing, ao detectar uma colisão, busca linearmente o próximo endereço vazio para inserir uma chave. Essa implementação se torna menos eficiente quando existe uma sequência grande de endereços ocupados (cluster) e, portanto exige alguns métodos como Double Hashing e Rehashing para melhorar sua eficiência temporal.
*Problemas com a remoção de elementos*.
-