Please enable JavaScript.
Coggle requires JavaScript to display documents.
M6 (Closed Hashing(Endereçamento livre), Open Hashing (encadeamento…
M6
Closed Hashing(Endereçamento livre)
Keys são armazenadas diretamente no array
Linear Probing
Checar se uma célula esta ocupada por outra key caso positivo inserir na célula seguinte do array até encontrar uma livre, caso chegar no fim voltar para o inicio
Procurar um elemento
Checar se a célula esta vazia
Caso positivo não foi encontrado
Caso negativo checar se as keys são iguais
Caso positivo foi encontrado
Caso negativo procurar na célula seguinte ate encontrar ou a célula estar vazia
Numero de acessos a tabela se a procura encontrar
Imagem retirada da página 273 do livro "Introduction to the Design and Analysis of Algorithms"-Anany V. Levitin
Numero de acessos a tabela se a procura não encontrar
Imagem retirada da página 273 do livro "Introduction to the Design and Analysis of Algorithms"-Anany V. Levitin
Remover
Usar "delete preguiçoso" marcar a célula com um simbolo indicando que aquela casa ja esteve ocupada
Cluster
Sequencia muito grande de células ocupadas que diminuem a eficiência do dicionário
Double Hashing
Para evitar colisões utilizar mais de uma função para determinar um incremento fixo no linear probing
Open Hashing (encadeamento separado)
Keys ficam armazenadas em lista encadeadas conectada a tabela de dispersão
α = n/m (load factor)
Inspeções de ponteiros
Caso encontre
≈ 1 + a/2
Caso não
=α
Adicionar
Adicionar um registro no final da lista
Θ(1)
Remover
Encontrar o registro e deleta-lo
Θ(1)
Melhora na questão espaço tempo
Aprimoramento de entrada
pré-processar a entrada do problema,
no todo ou em parte, e armazenar as informações adicionais obtidas
Pré-estruturação
Utilizar espaço extra para facilitar o acesso ao dado
Alguns processos são feitos antes da resolução do problema
Programação dinâmica
Análise de uma sequência de problemas mais simples do que o problema original para obter a resolução do mais difícil
Conjuntos e dicionários
Conjuntos
Uma coleção desordenada (pode estar vazia) de elementos distintos
2 maneiras de defini-los
Ou então as propriedades que todos elementos devem cumprir
Definido de maneira explicita(quais elementos estão nesse conjunto)
Principais operações
Checar se um determinado elemento está no conjunto
Encontrar a união de dois conjuntos
Encontrar a interseção de dois conjuntos
2 implementações
Subconjunto de um grande conjunto U (conjunto universal)
Se o conjunto U tiver N elementos, qualquer subconjunto S de U pode ser representado por uma string de bits de tamanho N
O elemento na posição I é 1 se e somente se o elemento na posição I de U está incluído no conjunto S
Rápido porém consome muita memória
Uma lista que contém todos elementos do conjunto
Dicionários
Estrutura de dados que implementa
Procurar um elemento
Adicionar um elemento
Remover um elemento
Formas de Implementação
Array
Hashing
Balanced search trees
Hashing
Tabela de dispersão
Array de uma dimensão com as keys dos registros
Por meio de uma função de dispersão a key é associada a um valor de 0 até o tamanho da tabela de dispersão -1
A tabela de dispersão não deve ser muito maior que o número de keys mas deve ser grande o suficiente para não comprometer a eficiência temporal e evitar colisões(adicionar dois registros em uma mesma posição)
A função deve ser de fácil de ser calculada
A função tem que distribuir as keys de maneira uniforme(se possível)
Armazenar registros geralmente esses registros apresentam identificadores
