Embed Size (px)
DESCRIPTION
HASHING. Katia Guimarães. HASHING. Suponha que você pudesse criar um array onde qualquer item pudesse ser localizado através de acesso direto. Isso seria ideal em aplicações do tipo Dicionário , onde gostaríamos de fazer consultas aos elementos da tabela em tempo constante . - PowerPoint PPT Presentation
Citation preview
HASHING
Suponha que você pudesse criar um array onde qualquer item pudesse ser localizado através de acesso direto.
Isso seria ideal em aplicações do tipo Dicionário, onde gostaríamos de fazer consultas aos elementos da tabela em tempo constante. Ex: Tabela de símbolos em compiladores.
O Tamanho de uma tabela HASH
Ex: Se fosse uma tabela de nomes com 32 caracteres por nome, teríamos 2632 > 1632 = (24)32 = 2128 possíveis elementos.
Um problema é que – como o espaço de chaves, ou seja, o número de possíveis chaves, é muito grande – este array teria que ter um tamanho muito grande.
Haveria também o desperdício de espaço, pois a cada execução somente uma pequena fração das chaves estarão de fato presentes.
Para que serve Hashing?
O objetivo de hashing é mapear um espaço enorme dechaves em um espaço de inteiros relativamente pequeno.
Isso é feito através de uma função chamada hash function.
O inteiro gerado pela hash function é chamado hash code e é usado para encontrar a localização do item.
Exemplo de Hashing
Suponha que 1. O espaço de chaves são os números inteiros de quatro dígitos, e 2. Deseja-se traduzí-los no conjunto {0, 1, ..., 7}.
Uma hash function poderia ser: f(x) = (5 • x) mod 8.
Exemplo de Hashing
Se o conjunto de dados for constituído pelos anos: 1055, 1492, 1776, 1812, 1918 e 1945, a hash function f (x) = (5 • x) mod 8 gerará o seguinte mapeamento:
Ex: f (1055) = (5 • 1055) mod 8 = 5275 mod 8 = 3
Ex: f (2002) = (5 • 2002) mod 8 = 10010 mod 8 = 2
Índice: 0 1 2 3 4 5 6 7 Chave: 1776 1055 1492 1945 1918 1812
2002
ColisãoNo exemplo anterior dizemos que entre as chaves 1492 e 1812 ocorreu uma colisão, isto é estas duas chaves geraram o mesmo hash code, ou seja, foram mapeadas no mesmo índice.
Índice: 0 1 2 3 4 5 6 7 Chave: 1776 2002 1055 1492 1945 1918 1812
Resolvendo ColisõesO desejável seria que a função fosse injetiva, de forma a evitar colisões, mas como isso é muito difícil, há vários esquemas para trabalhar a ocorrência de colisões.
Há duas grandes classes de abordagens: 1. Closed Address Hashing (endereçamento fechado) 2. Open Address Hashing (endereçamento aberto)
Closed Address Hashing (endereçamento fechado)
Closed Address Hashing ou hashing encadeadoé a forma mais simples de tratamento de colisão.
Cada entrada H[i] da tabela hash é uma lista ligada, cujos elementos têm hash code i.
Para inserir um elemento na tabela: 1. Compute o seu hash code i, e 2. Insira o elemento na lista ligada H[i].
Closed Address Hashing (endereçamento fechado) Problemas com o comprimento da lista ligada
Embora uma função hash bem escolhida promova um bom balanceamento, não se pode garantir que as listas terão tamanhos próximos.
Seria possível substituir a lista ligada por estruturas mais eficientes de busca, como árvores balanceadas, mas isso não se faz na prática.
Open Address Hashing (endereçamento aberto)
É uma estratégia para guardar todas as chaves na tabela, mesmo quando ocorre colisão.
H[i] contém uma chave, ao invés de um link.
Tem a vantagem de não usar espaço extra.
Em caso de colisão, um novo endereço é computado. Esse processo é chamado rehashing.
Rehashing por Linear Probing
A forma mais simples de rehashing é linear probing.
Se o hash code f (K) = i, e alguma outra chave já ocupa a posição H[i], então a próxima posição disponível na tabela H será ocupada pela chave K : rehash (i) = (i+1) mod h.
Rehashing por Linear Probing
rehash (4) = (4+1) mod 8 = 5 para a chave 1812.
Índice: 0 1 2 3 4 5 6 7 Chave:
Ex: Se o conjunto de dados for constituído pelos anos: 1055, 1492, 1776, 1812, 1918 e 1945, a hash function f (x) = (5 • x) mod 8, e usando linear probing na colisão.
rehash (5) = (5+1) mod 8 = 6rehash (6) = (6+1) mod 8 = 7
1055 149217761812
1812 191819451945
1945
Para a chave 1945:
Rehashing por Linear Probing
Note que:
1. É possível que uma posição i da tabela Hash já esteja ocupada com alguma chave cujo hash code é diferente de f (K).
2. Rehashing por linear probing não depende do valor da chave K.
Rehashing por Linear Probing
Para recuperar uma chave:
1. Compute o valor de f (K) = i.
2. Se H[i] está vazia, então K não está na tabela.
3. Se H[i] contém alguma chave diferente de K, então compute rehash (i) = i1 = (i + 1) mod h.
4. Se H[i1] está vazia, então K não está na tabela. Senão, se H[i1] contém alguma chave diferente de K, então rehash (i1), etc ...
Rehashing por Linear Probing
Rehashing por Linear Probing pode trazer sérios problemas de colisão se houver uma alta taxa de ocupação na tabela Hash.
Para um bom desempenho é importante manter a taxa de ocupação da tabela próxima a 0,5 (50% do espaço).
Rehashing por Double Hashing
Um método mais efetivo de fazer rehashing é por Double Hashing.
Ao invés de fazer os incrementos de 1 invariavelmente, os incrementos são feitos por um valor d, que depende da chave K.
Ex: d = HashIncr (K) rehash (j, d) = (j+d) mod h.
Rehashing por Double Hashing
Índice: 0 1 2 3 4 5 6 7 Chave:
1055 149217761812
1812 19181945
Ex: Conjunto de dados: 1055, 1492, 1776, 1812, 1918 e 1945 Hash function f (x) = (5 • x) mod 8 Colisões resolvidas por double hashing com HashIncr(K) = (K mod 7) + 1
rehash (4, 7) = (4 + 7) mod 8 = 3HashIncr (1812) = (1812 mod 7) + 1 = 6 + 1 = 7
f (1812) = (5 • 1812) mod 8 = (9060 mod 8) = 4
rehash (3, 7) = (3 + 7) mod 8 = 2
Removendo Elementos da Tabela
A remoção é uma operação delicada em tabelas Hash.
Usa-se um bit para indicar se a posição está, de fato, ocupada por um elemento válido da tabela, ou se o dado que se encontra naquela entrada não faz parte da mesma.
