Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Hashing - Coggle Diagram
Sets and Dictionaries
SET
Pode ser entendio como uma coleção não ordenada de itens distintos chamada de elementos do conjunto.
Um conjunto específico é definido de forma de listagem explicita de um elemento.
S = {2,3,5,7}
Ou por especificar uma propriedade que somente um conjuntos de elementos apresenta.
Por exemplo, o conjunto dos números primos.
As operações mais importantes são
Checar se um item pertence ao conjunto.
Encontrar a união de dois conjuntos que compreende todos os elementos de um ou de ambos os conjuntos.
Encontrar a interserção de dois conjuntos, no qual, compreende todos os elementos comuns dos conjuntos.
Há duas maneiras de implementar a ideia de conjuntos para uma aplicação no computador.
O primeiro é considerar que somente um conjunto é um subconjunto de um um conjunto U muito maior, o conjunto Universo
Se U tem n elem., então um subconjunto S de U pode ser representado por um bit de string de tamanho n, chamado de bit vetor.
Exemplo:
Se U = {1,2,3,4,5,6,7,8,9} então S{2,3,5,7} é representado por um bit de string 011010100
A segunda maneira é representar o conjunto como uma estrutura de lista para indicar o conjunto dos elementos
É para ser usada para conjuntos finitos.
Vamos esclarecer os principais pontos que diferem lista para conjuntos(
sets
).
Um
set
NÃO pode conter elementos idênticos.
SET
é um conjunto não medido pela coleção de itens, logo, mudar a medida dos itens não acarretará mudanças no conjunto.
As operações que podemos efetuar com o
set
.
Procurar um item;
Add um novo item;
Deletar um item;
A estrutuda de dados que contêm essas operações é chamada de
dictionary
Hashing
Há duas versões para implementar o hashing.
Open Hashing (Separate Chaining)
As chaves são armazenadas em listas ligadas apegadas para as células de uma hash table.
Cada lista contêm todas as keys hashed de suas células.
Se a hash function distribuiur n keys por meio de m células de uma hash table uniformemente, cada lista terá
n/m
chaves comprimento.
A proporção
alpha = n / m
chamada de
load factor
da hash table lançará uma regra crucial para a eficiência de
hashing
.
O número médio de ponteiros inspecionados com procuras com sucesso, S, e insucesso, U, será :
S ~= 1 +
alpha/2
U =
alpha
O resultado é quase igual a uma procura sequêncial em uma lista ligada.
Normalmente não queremos que o valor de load factor esteja longe de um.
Caso
load factor
for um núm. muito pequeno, isso implicaria em muitos espaços vazias na lista ligada, o que significa uma ineficiência espacial.
Agora um
load factor
muito grande, implica em uma extensa lista ligada, o qual acarreta uma ineficiência temporal.
Caso add uma comparação, nós precisariamos gastar mais tempo para calcular o valor de uma função de hash por uma procura de keys.
As dicitionarys operations
Insertion
Quase idêntica a de procura de chaves
Normalmente feita no final da lista.
Deletion
É performada pela procura da chave que será deletada.
Closed Hashing(Open Addressing)
Todas as chaves são armazenas na própria tabela hash sem precisas das listas ligadas.
Diferentes estratégias podem ser aplicadas para resolver o problema de
colisões
.
Linear probing
Verificar a célula seguinte aquela que ocorre a colisão.
Se a cell estiver vazia, instalar uma chave lá.
Se a cell estiver ocupada, então a avaliação será feita da cell. sucessora e assim por diante.
Caso tenha chegado no fim da tabela de hash, a procurá retornará no inicio da tabela, tratando-se de ua forma como um array circular.
As operações do tipo
searching
e
insertion
são diretas, ao contrário da
deletion
.
Lazy deletion
É usado a fim de contornar o problema deixado pela deletação, que seria uma cell. vazia.
Basicamente ocupar previametente o local com um símbolo distinto par diferenciar essa localização das demais.
A análise matemática dos problemas é mais dificil dos que separação em série.
Uma versão mais simplificada dos casos médios é
A medida que a tabela de hash vai aproximando-se de estar lotada, a performance do linear probing deteriora-se devido ao fenômeno de clustering (agrupamento).
Um cluster em linear probing pe uma sequência de cell. ocupadas
1 more item...
Hashing
é baseado na ideia de distribuir keys por meio de um array unidimensional chamado de
hash table
.
A distribuição é feita pela computação de cada chave, o valor de algumas funções pré-definidas
h
são chamadas de
hash function
. Essas funções alocadas entre um inteiro 0 e m - 1, chamado de
hash address
.
Em geral,
hash function
precisam satisfazer algumas requesitos um tanto que conflitantes,
O tamanho de
hash table
não deveria ser excessivamente grande comparado ao tamanho do número de chaves, mas deverá ser o suficiente para não compremeter a eficiência temporal da implementação.
Uma
hash function
precisa distribuir as chaves por meio das células da
hash table
como uniformemente todas as possibilidades.
Um
hash function
tem que fácil para computar.
Se nós escolhermos uma
hash table
de tamanho m para ser menor que o número n de chaves, nós teremos
collisions
.
COLLISIONS
é um fenomeno no qual duas ou mais chabves apontam para a mesma célula da hash table.
No pior caso, teremos que todas as chaves será hashed para uma mesma célula da hash table.
É um caminho muito mais eficiente para implementar dictionaries.
