Hashing

Livro de Sedgewick e Wayne: sec.3.4, p.458.  Website do livro: resumo sec.3.4, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.princeton.edu/code/.

Esta página trata da implementação de TSs (tabelas de símbolos) por meio de tabelas de dispersão e tabelas de hash.  A teoria é simples mas o sucesso das implementações depende de truques práticos. Pode-se dizer que essas implementações envolvem mais arte que ciência.

Hashing tem dois ingredientes fundamentais: uma função de hashing e um mecanismo de resolução de colisões.

Resumo:

Pré-requisitos:

Ideias preliminares

Exercícios 1

  1. Qual a diferença entre o exemplo dos CPFs acima e a implementação BinarySearchST já discutida?
  2. Qual a diferença entre o exemplo das listas ligadas de nomes e a implementação SequentialSearchST já discutida?

Funções de hashing

Função de hashing modular

Exercícios 2

  1. Qual o valor da expressão  key % M  se key é negativo?
  2. Por que convém evitar overflow no cálculo do valor hash de uma string?
  3. (SW 3.4.4)  Escreva um programa para encontrar valores de  a  e  M ,  com M o menor possível, tais que a função de hashing  (a * k) % M , que transforma a k-ésima letra do alfabeto em um valor hash, não produza colisões quando aplicada às chaves  S E A R C H X M P L .  (Isso é conhecido como função de hashing perfeita.)

Os métodos hashCode de Java

O que se espera de uma função de hashing ideal

Exercícios 3

  1. Elimine as palavras repetidas de tale.txt. Depois, faça um histograma como o mostrado acima mas usando M = 100.
  2. Faça um histograma como o mostrado acima para as palavras de tale.txt (sem repetições), com M = 97, mas alguma função de hashing diferente da usada acima.
  3. Faça um histograma como o acima para as palavras de quincasborba.txt (depois de eliminadas as repetidas).
  4. É fácil implementar operações como min(), max(), floor() e ceiling() em tabelas de símbolos implementadas com tabelas de hash?

Implementação 1: hashing com encadeamento

Análise

Exercícios 4

  1. Podemos ter alpha < 1 numa tabela de hash com encadeamento?
  2. (SW 3.4.1)  Insira as chaves  E A S Y Q U T I O N ,  nessa ordem, usando hashing com encadeamento, em uma tabela com M = 5 listas. Use a função de hashing   11*k % M   para transformar a k-ésima letra do alfabeto em um índice da tabela de hash.
  3. Repita os experimentos com o livro tale.txt usando valores de M diferentes de 997 (tente valores que são potência de 2, por exemplo).
  4. (SW 3.4.9)  Acrescente um método delete() à classe SeparateChainingHashST. O seu método deve ser ansioso: ele deve remover o chave solicitada imediatamente (e não simplesmente marcá-la com null para remoção posterior).
  5. (SW 3.4.19)  Acrescente um iterador keys() à classe SeparateChainingHashST.
  6. Acrescente um método a SeparateChainingHashST que calcule o custo médio de uma busca bem-sucedida, supondo que cada chave tem a mesma probabilidade de ser buscada. (O custo da busca é o número de comparações de chaves.)
  7. Acrescente um método a SeparateChainingHashST que calcule o custo médio de uma busca malsucedida sob a hipótese de hashing uniforme. (O custo da busca é o número de comparações de chaves.)
  8. (SW 3.4.36) Faixa de comprimentos de listas. Escreva um programa que insira N chaves inteiras (números int) aleatórias em uma tabela de tamanho N/100 usando hashing com encadeamento e depois determine o comprimento da lista mais curta e da mais longa. Faça isso para N igual a 103, 104, 105, 106.  (Faça um pequeno relatório sobre os resultados e acrescente o relatório, como comentário, ao final do seu programa.)

Implementação 2: hashing com sondagem linear

Análise

Exercícios 5

  1. Por que a análise das buscas malsucedidas e bem-sucedidas é feita em separado?
  2. (SW 3.4.10)  Insira as chaves  E A S Y Q U T I O N ,  nessa ordem, usando hashing com sondagem linear, em uma tabela com M = 16 posições. Use a função de hashing   11*k % M   para transformar a k-ésima letra do alfabeto em um índice da tabela de hash.  Repita o exercício com M = 10.
  3. Quero acrescentar à classe LinearProbingHashST um método delete() que remova uma dada chave key da tabela. Mostre, por meio de um exemplo simples, que o código a seguir não resolve o problema.
        public void delete(Key key) {
            if (!contains(key)) return;
            int i = hash(key);
            while (!key.equals(keys[i]))
                i = (i + 1) % M;
            keys[i] = null;
            vals[i] = null;
        }
    
  4. (SW 3.4.17, p.471) Acrescente à classe LinearProbingHashST um método delete() que remova uma dada chave (e o valor associado).
  5. (SW 3.4.19)  Acrescente um iterador keys() à classe LinearProbingHashST.
  6. (SW 3.4.20)  Acrescente à classe LinearProbingHashST um método que calcule o custo médio de uma busca bem-sucedida, supondo que cada chave da tabela tem a mesma probabilidade de ser buscada.  (O custo da busca é o número de sondagens, ou seja, o número de posição visitadas da tabela de hash.)  Use o código de LinearProbingHashST sem redimensionamento. Escreva um cliente CustoSondagemLinear.java que teste o novo método usando um gerador de números aleatórios.  Use VisualAccumulator para fazer um gráfico de custos em função do número N de chaves.  Superponha o gráfico com as previsões dadas na Proposição M.
  7. (SW 3.4.21)  Acrescente à classe LinearProbingHashST um método que calcule o custo médio de uma busca malsucedida supondo uma função de hashing aleatória. (O custo da busca é o número de sondagens, ou seja, o número de posição visitadas da tabela de hash.)  (Observação: Não é necessário calcular nenhum função de hash para resolver essa questão.) Use o código de LinearProbingHashST sem redimensionamento. Escreva um cliente CustoSondagemLinear.java que teste o novo método usando um gerador de números aleatórios.  Use VisualAccumulator para fazer um gráfico de custos em função do número N de chaves.  Superponha o gráfico com as previsões dadas na Proposição M.

Redimensionamento da tabela de sondagem linear

Exercícios 6

  1. Escreva uma versão de SeparateChainingHashST que faça redimensionamento da tabela de hash.
  2. (SW 3.4.26) Remoção preguiçosa sob sondagem linear. Acrescente um método delete() à classe LinearProbingHashST. Para remover uma chave da tabela, o método deve atribuir null ao valor associado à chave e adiar a efetiva remoção da chave (e do valor associado) até o momento em que a tabela for redimensionada. (Observação: Você deve sobrescrever o valor null se uma operação put() subsequente associar um novo valor à chave.) O desafio é decidir quando resize() deve ser chamado. Para tomar a decisão de redimensionar, seu método deve levar em conta não só o número de posições vagas da tabela mas também o número de posições mortas.

Perguntas e respostas


Valid CSS! Valid HTML 4.01 Strict