Exercícios com tabela hash

Exercícios com tabela HASH
Questões:
1. Veja três casos: nenhuma colisão, pior caso, colisão normalmente encontrada. Descreva exemplos para cada uma destas situações e indique seu impacto na utilização deste recurso em uma situação real.

Nenhuma colisão

Neste exemplo podemos observar uma situação de melhor caso (sem colisão), onde a funcão de mapeamento gerou índices diferentes para todos os conjuntos de chaves providos. A função de mapeamento aplicada neste caso é H(x) = xmod16, onde x é a soma dos resultados obtidos na conversão das chaves para ASCII e 16 é o número de posições da tabela hash. Observe abaixoo calculo dos índices obtidos:

Pior caso

Neste exemplo podemos observar uma situação de pior caso, onde a funcão de mapeamento gerou o mesmo índice para todos os conjuntos de chaves providos. A função de mapeamento aplicada neste caso é H(x) = xmod16, onde x é a soma dos resultados obtidos na conversão das chaves para ASCII e 16 é o número de posições da tabela hash. Observe abaixoo calculo dos índices obtidos:

Colisão normalmente encontrada

Neste exemplo podemos observer uma situação de eventual colisão, onde a funcão de mapeamento gerou o mesmo índice para alguns dos conjuntos de chaves providos. A função de mapeamento aplicada neste caso é H(x) = xmod16, onde x é a soma dos resultados obtidos na conversão das chaves para ASCII e 16 é o número de posições da tabela hash. Observe abaixoo calculo dos índices obtidos:

Impacto na utilização de tabelas hash em uma situação real

As tabelas hash apresentam em média um ótimo desempenho, entretanto, no pior caso, apresentam desempenho semelhante ao de uma lista encadeada não ordenada. Em função disto, a implementação de tabelas hash em sistemas de tempo real se torna inviável, pois tais sistemas precisam garantir um determinado tempo de resposta mesmo diante do pior