INF1010 3WB – Lista 5: Tabela de dispersão (hash table).

Exercícios

1. Considere cada um dos caracteres da palavra P E S Q U I S A como sendo informações que devam ser armazenadas em uma tabela de dispersão (hash table) utilizando a seguinte função:
   

   h(char) = (ordem de char no alfabeto)%7
   

   Desenhe como ficaram a tabela de dispersão e as listas encadeadas.
2. A solução das colisões com listas encadeadas adotada na questão anterior é chamada de "encadeamento exterior". Existe outra solução mais eficiente quando sabemos de antemão um bom limite superior das informações que vamos armazenar. Ela consiste em armazenar na própria tabela as informações. Nesta solução, denominada de "endereçamento aberto", quando uma chave x é endereçada para uma posição já ocupada da tabela uma sequencia de posições h₁(x), h₂(x), h₃(x), ... alternativas é escolhida. A primeira disponível recebe a informação. Se nenhuma das posições: h₁(x), h₂(x), h₃(x), ..., posição estiver vazia então a tabela está cheia e não podemos inserir x. Refaça o exercício 1 aumentando a tabela para 13 elementos com as seguintes função de disperção:
   1. h_j(char) = (ordem de char no alfabeto+j)%13
   2. h_j(char) = (ordem de char no alfabeto+j²)%13
3. Mostre que o resultado da inserção das chaves 19, 38, 64, 100, 81, 47, 27, 31 em uma tabela de dispersão de tamanho m = 17, sendo que as colisões são tratadas por endereçamento aberto. A sequência de tentativas é dada por:
   1. h'(x) = x % m
   2. h(x, k) = (h'(x) + k) % m, 0 < k ≤ m-1
4. Explique a função de dispersão que você utilizou no trabalho e justifique porque ela é melhor que a que já existia no módulo hash fornecido.