Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hashing - Coggle Diagram
Hashing
Hashing
Requirements para uma Hash
A função Hash deve distribuir uniformente as keys na hash table
A hash funtion deve ser facilmente computada
Não pode ter um tamanho muito superior ao numero de keys
Open Hashing
Todas as keys são colocadas em linked lists que apontam para as células da hash table
Para pesquisar um determinado elemento, o coloca sobre a função hash para descobrir sua key e então vê se a key existe
Alguns elementos podem possuir a mesma key, ocorrendo uma colisão e dificuldade em encontrar os elementos
Componentes
Records: são conjuntos de dados que contém vários elementos, Struct
Keys: são formas de representar o indice de algo nos records
Hash Table: Um array de dimensão linear
Closed hashing
As keys são guardadas na própria hash table sem uso de linked list
É feita a checagem para ver se o espaço esta vazio e então é inserido a key, caso não, checa o próximo espaço, se todos estiverem cheios a key é colocada no inicio
Para encontrar uma key, é aplicado a hash function e então comparado ao local onde a key fica, caso estaja vazio, será um falha, caso tenha item ele deve continuar comparando até encontrar uma celula vazia
O sistema perde eficiencia a medida que a table vai ficando completa, formando cluster que são a união de várias keys lado a lado
Double hashing: Uma forma de diminuir colisions, consiste em usar uma segunda function quando encontrar uma colisão, para isso a função nova deve ser prima com o numero de tamanho da lista
s(k) = m − 2 − k mod (m − 2)
and s(k) = 8 − (k mod 8) for small tables and s(k) = k mod 97 + 1 for larger ones.
Rehashing: ato de mover as keys para uma outra hash table maior para diminuir os clusters
Sets
São conjuntos de elementos de ordenação e propriedades definidos
Operações
Encontrar a união de 2 sets
Encontrar a interseção entre 3 sets
Checar se um elemento faz parte do set
Implementação
Universal set: É dado um universo de elementos e uma string para representar quais elementos do universo estão no set
Ex: U= { 1,2,3,4,5,6,7,8,9 }, S= { 2,3,5,7 }
String = 011010100
Muito rápido mas pode consumir grande memória
List Set - Pode admitir valores repetidos o que não ocorre no set, é também possivel alterar a ordem dos elementos
Um set envolve um conjunto de operações de pesquisa e manipulação num contexto dinâmico, ao implementarmos isso temos um dictionary, adt para sets
Space for time trade off
Formas de tornar um algortimo mais rápido por meio do espaço
Input Enhacement: Manter o total ou parcialmente resolvido o input para acelerar o tempo de processamento
Prestructuring: Aumentar o espaço utilizado para acessar determinados dados mais facilmente
Progamação Dinâmica: Recordar Soluções de subproblemas para então resolver o problema maior