Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hashing, Solução para hashing duplo - Coggle Diagram
Hashing
Hashing
key
usada para identificar entidades em um registreo
Letras, numeros, palavras
Distribui
keys
numa matriz unidimensional
matriz chamada de
Tabela hash
função hash
São valores de uma função dados à cada
key
da
tabela hash
Função
função atribui números de 0 até o comprimento da matriz chamado de
Endereço hash
Depende de todos os bits da key
colisões
Duas ou mais keys sendo hash da mesma célula
pior caso
Todas as key forem transferidas para a mesma célula
Deve existir uma mecanismo de resolução de colisão
Inserção e exclusão é feita com ajuda de funções
Importante em aplicações de IA
Espaço e tempo
Aprimoramento de entrada
Pré-processar em partes ou no todo, e armazenar informações de problemas de entrada
Pré-estruturação
utiliza mais espaço de armazenamento, deixando o acesso mais rapido
Programação dinâmica
Solução de problemas gravados, a partir de uma tabela
Tempo de espaço
Hashing aberto
As chaves são armazenadas em listas ligadas anexadas as tabelas hash
Pesquisa de hash em dicionarios
a eficiência da pesquisa depende do comprimento dos da lista ligada
The Ratio a= n/m
n=numero de chaves, m= numero de celular
Hashing fechado
key são armazenadas na própria tabela hash
Resolução de Colisões
Verifica se a próxima célula esta vazia caso sim armazena a informação nela
Chamada de
sondagem linear
Hashing duplo
superior a sondagem linear
seu desempenho deteriora quando o mesa esta cheia
Rehashing
a mesa é verificada de estiver cheia as keys são realocadas para uma maior
Dicionários e conjuntos
conjunto
Uma coleção de itens distintos, possivelmente vazia
associação de conjuntos
intersecção de conjuntos
Aplicações em computadores
Conjunto que são subconjuntos
Vetor de bits
conjunto pode ser representados po bits
U= {1,2,3,4,5,6,7,8,9} e S={2,3,5,7}
igual a 011010100
indicar elementos na estrutura lista
multiset ou bolsa
conjunto de elementos não necessariamente distintos não ordenados
Dicionarios
Estrutura de dados
procura, adiciona e exclui determinado item de uma coleção
Utilizadoss em array
Não eficiente
Utilizados em
hash
e pesquisa de arvore
Forma eficiente
Solução para hashing duplo