Hashing | Conjunto 3 (endereçamento aberto)
É altamente recomendável consultar a postagem abaixo como um pré-requisito para isso.
Hashing | Conjunto 1 (Introdução)
Hashing | Conjunto 2 (encadeamento separado)
Endereçamento aberto
Como o encadeamento separado, o endereçamento aberto é um método para lidar com colisões. No Open Addressing, todos os elementos são armazenados na própria tabela hash. Portanto, em qualquer ponto, o tamanho da tabela deve ser maior ou igual ao número total de chaves (observe que podemos aumentar o tamanho da tabela copiando dados antigos, se necessário).
Inserir (k): Continue sondando até que um slot vazio seja encontrado. Assim que um slot vazio for encontrado, insira k.
Pesquisar (k): Continue sondando até que a chave do slot não se torne igual ak ou um slot vazio seja alcançado.
Excluir (k): A operação de exclusão é interessante . Se simplesmente excluirmos uma chave, a pesquisa pode falhar. Assim, os slots de chaves excluídas são marcados especialmente como “excluídos”.
A inserção pode inserir um item em um slot excluído, mas a pesquisa não para em um slot excluído.
O endereçamento aberto é feito das seguintes maneiras:
a) Teste Linear: No teste linear, testamos linearmente para o próximo slot. Por exemplo, a lacuna típica entre duas sondas é 1, conforme mostrado no exemplo abaixo.
Seja hash (x) o índice de slot calculado usando uma função hash e S o tamanho da tabela
If slot hash(x) % S is full, then we try (hash(x) + 1) % S If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S .................................................. ..................................................
Vamos considerar uma função hash simples como "mod de tecla 7" e uma sequência de teclas como 50, 700, 76, 85, 92, 73, 101.
Desafios em sondagem linear:
- Agrupamento primário: um dos problemas com a análise linear é o agrupamento primário, muitos elementos consecutivos formam grupos e começa a demorar para encontrar um slot livre ou para procurar um elemento.
- Clustering secundário : o clustering secundário é menos severo, dois registros só têm a mesma cadeia de colisão (Sequência de Sonda) se sua posição inicial for a mesma.
b) Sondagem quadrática Procuramos i 2 'slot na i'ésima iteração.
let hash(x) be the slot index computed using hash function. If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S .................................................. ..................................................
c) Hashing duplo Usamos outra função hash hash2 (x) e procuramos o slot i * hash2 (x) na i'ésima rotação.
let hash(x) be the slot index computed using hash function. If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S .................................................. ..................................................
Veja este para passo a passo diagramas.
Comparação dos três acima:
A análise linear tem o melhor desempenho de cache, mas sofre de armazenamento em cluster. Mais uma vantagem do teste linear é fácil de calcular.
A análise quadrática está entre os dois em termos de desempenho de cache e clustering.
O hash duplo tem baixo desempenho de cache, mas nenhum clustering. O hash duplo requer mais tempo de computação, pois duas funções de hash precisam ser calculadas.
S.No. | Encadeamento separado | Endereçamento Aberto |
---|---|---|
1 | O encadeamento é mais simples de implementar. | O endereçamento aberto requer mais computação. |
2 | No encadeamento, a tabela Hash nunca fica cheia, podemos sempre adicionar mais elementos à cadeia. | No endereçamento aberto, a tabela pode ficar cheia. |
3 | O encadeamento é menos sensível à função hash ou aos fatores de carga. | O endereçamento aberto requer cuidado extra para evitar agrupamento e fator de carga. |
4 | O encadeamento é usado principalmente quando não se sabe quantas e com que frequência as chaves podem ser inseridas ou excluídas. | O endereçamento aberto é usado quando a frequência e o número de chaves são conhecidos. |
5 | O desempenho do cache de encadeamento não é bom porque as chaves são armazenadas usando uma lista vinculada. | O endereçamento aberto fornece melhor desempenho do cache, pois tudo é armazenado na mesma tabela. |
6 | Perda de espaço (algumas partes da tabela de hash no encadeamento nunca são usadas). | No endereçamento aberto, um slot pode ser usado mesmo se uma entrada não for mapeada para ele. |
7 | O encadeamento usa espaço extra para links. | Nenhum link no endereçamento aberto |
Desempenho do endereçamento aberto:
como o encadeamento, o desempenho do hashing pode ser avaliado sob a suposição de que cada chave tem a mesma probabilidade de ser hash para qualquer slot da tabela (hashing uniforme simples)
m = Number of slots in the hash table n = Number of keys to be inserted in the hash table Load factor α = n/m ( < 1 ) Expected time to search/insert/delete < 1/(1 - α) So Search, Insert and Delete take (1/(1 - α)) time
? list = PLqM7alHXFySGwXaessYMemAnITqlZdZVE
Referências:
http://courses.csail.mit.edu/6.006/fall11/lectures/lecture10.pdf
https://www.cse.cuhk.edu.hk/irwin.king/_media/teaching/csc2100b /tu6.pdf
Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva