Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Hashing, Space and Time Trade-Offs - Coggle Diagram
Sets and Dictionaries
Set: A noção de um conjunto tem um papel muito importante na matemática. Um conjunto pode ser descrito como um coleção não ordenada (possivelmente vazia) de itens chamados de elementos do conjunto. Um conjunto específico é definido por uma listagem explícita de seus elementos ou especificando uma propriedade que todos os elementos do conjunto e somente eles satisfazem.
A segunda e mais comum maneira de representar um conjunto para fins de computação é usar a estrutura de lista para indicar elementos de conjunto. Claro, esta opção, também, é viável apenas para conjuntos finitos; felizmente ao contrário da matemática este é o tipo de conjunto que a maioria dos aplicativos de computador precisa. Note, entretanto, os dois principais pontos entre conjuntos e listas
-
Second: Um conjunto, é um coleção de itens não ordenados; portanto, mudar a ordem dos elementos não muda o conjunto. Uma lista, definida como uma coleção ordenada de elementos, é exatamente o oposto.
Universal set: Considera apenas conjuntos que são subconjuntos de algum conjunto grande U. Se o conjunto U tiver n elementos, então qualquer subconjunto S de U poder ser representado por uma string de bits do tamanho n, chamada de 'bit vector', em que o ith elemento é o 1 se e somente se o elemento ith de U é incluído no conjunto S.
Em computação , as operações que precisamos realizar para um conjunto ou um multiconjunto(um coleção não ordenada de itens que não são necessariamente distintos) na maioria das vezes procurar por um dado item, adicionar novo item, e deletar um item da coleção. Uma estrutura de dados que implementa essas 3 operações é chamada de dicionário. Obviamente, estamos lidando aqui com procurar em um contexto dinâmico. Consequentemente um implementação eficiente de um dicionário tem que chegar em um meio-termo entre a eficiência da pesquisa e as eficiências das outras duas operações. Há várias maneiras de se 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
Hashing: É baseado na ideia de distribuir chaves entre um array uni-dimensional H[0.. m - 1] chamado de 'hash table'. A distribuição é feita calculando, para cada uma das chaves, o valor de alguma função predefinida h chamada de hash function. Esta função atribui um inteiro entre 0 e m -1, chamado de hash address, para um chave. Em geral, uma função hash precisa satisfazer requisitos um tanto conflitantes:
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.)
-
O tamanho de uma 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 do tempo de implementação
Obviamente, se escolhermos o tamanho m de uma tabela de hash menor do que o número de chaves n, teremos colisões - um fenômeno de duas (ou mais) chaves sendo hashed na mesma célula da tabela de hash. Mas colisões devem ser esperadas mesmo se m for consideravelmente maior que n. De fato, no pior caso, todas as chaves poderiam ser 'hashed' para a mesma célula da hash table.
Closed Hashing: todas as chaves são armazenadas na própria tabela de hash sem o uso de listas ligadas. (Claro, isso implica que o tamanho da tabela m deve ser pelo menos tão grande quanto o número de chaves n.)
Linear probling : verifica a célula seguinte àquela onde ocorre a colisão. Se essa célula estiver vazia, a nova chave é instalada lá; se a próxima célula já estiver ocupada, a disponibilidade do sucessor imediato dessa célula é verificada e assim por diante
Open Hashing:as chaves são armazenadas em listas ligadas anexadas às células de uma tabela hash. Cada lista contém todas as chaves com hash para sua célula.
-