Tabelas de Dispersão: Funções, Colisões e Eficácia

Tabelas de Dispersão

Função de Dispersão

A função de dispersão converte a chave em um índice de alocação na tabela de dispersão, uma estrutura que associa chaves a valores. Ela calcula a posição onde a informação será inserida. Para ser eficiente, a função deve ser:

• Computacionalmente eficiente (fácil e rápida de calcular).
• Modular (calcular um valor dentro dos limites da tabela).
• Gerar boa dispersão, minimizando colisões.

Colisões

Uma dispersão ineficiente causa colisões, quando chaves diferentes resultam na mesma posição. Existem duas técnicas para resolver colisões:

Separate Chaining (Encadeamento)

Elementos que colidem são armazenados em uma lista ligada no slot correspondente. Se o slot estiver vazio, seu valor é nulo. A pesquisa envolve calcular o hash e buscar na lista. Com distribuição uniforme de chaves, a eficácia média depende do número médio de elementos nas listas.

Opções para armazenar elementos em colisão:

• Listas ordenadas (reduzem o custo médio de busca).
• BSTs autoequilibradas.

Caso Pior: Todas as chaves caem no mesmo slot (eficácia O(n) + tempo do cálculo do hash).

Caso Médio: Depende do número de colisões. Com distribuição uniforme, é O(n + α).

Open Addressing (Endereçamento Aberto)

Usado quando o número de elementos é previsível e menor que o tamanho da tabela. Para cada colisão, uma nova posição é buscada. A pesquisa envolve o cálculo do hash e a busca na nova posição.