Suponha que existam 𝑛 chaves a serem armazenadas em uma tabela 𝑇, sequencial e de dimensão 𝑚. As ...

Alternativa (E) - Compartimento 3

Introdução

A questão aborda o conceito fundamental de funções de dispersão (hash functions) e colisões em tabelas hash, um tópico essencial na área de estruturas de dados e algoritmos. Funções de dispersão são utilizadas para mapear chaves de um domínio geralmente grande para índices de uma tabela de tamanho limitado, permitindo acesso eficiente aos dados.

Desenvolvimento

Tabelas hash são estruturas de dados que armazenam pares chave-valor, onde a localização de armazenamento de um valor é determinada aplicando uma função de dispersão à chave. Essa função transforma a chave em um índice dentro do intervalo das posições da tabela. O objetivo é distribuir as chaves de forma uniforme para minimizar colisões. Colisões ocorrem quando duas ou mais chaves distintas são mapeadas para o mesmo índice na tabela, exigindo um procedimento especial para o armazenamento (como encadeamento, sondagem linear, sondagem quadrática, entre outros).

A função de dispersão dada é h(x) = x mod 5. O operador módulo (mod ou %) retorna o resto da divisão inteira de x por 5. O resultado estará sempre no intervalo [0, 4], o que corresponde aos possíveis compartimentos da tabela, dado que m (a dimensão da tabela) é 5 (pois o módulo é 5, e os compartimentos vão de 0 a m-1).

Para determinar qual compartimento causará uma colisão, precisamos aplicar a função h(x) a cada uma das chaves fornecidas: 78 e 13.

Análise

Vamos aplicar a função de dispersão h(x) = x mod 5 a cada chave fornecida:

1. Para a chave x = 78:

   • Calculamos h(78) = 78 mod 5.
   • Ao dividir 78 por 5, obtemos: 78 ÷ 5 = 15 com um resto de 3.
   • Portanto, h(78) = 3. Isso significa que a chave 78 seria armazenada no compartimento de índice 3.

2. Para a chave x = 13:

   • Calculamos h(13) = 13 mod 5.
   • Ao dividir 13 por 5, obtemos: 13 ÷ 5 = 2 com um resto de 3.
   • Portanto, h(13) = 3. Isso significa que a chave 13 também seria armazenada no compartimento de índice 3.

Como ambas as chaves, 78 e 13, são mapeadas para o mesmo compartimento (o compartimento de índice 3), isso configura uma colisão. O compartimento 3 será o local onde a colisão ocorrerá quando tentarmos armazenar essas duas chaves consecutivamente.

Vamos comparar os resultados com as alternativas apresentadas:

| Alternativa | Compartimento | Justificativa | | :---------- | :------------ | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | | (A) | 5 | Incorreto. Uma função de dispersão x mod 5 mapeia chaves para índices no intervalo [0, 4], pois o resto de uma divisão por 5 nunca será 5. | | (B) | 1 | Incorreto. 78 mod 5 = 3 e 13 mod 5 = 3. Nenhuma das chaves resulta em 1. | | (C) | 4 | Incorreto. 78 mod 5 = 3 e 13 mod 5 = 3. Nenhuma das chaves resulta em 4. | | (D) | 2 | Incorreto. 78 mod 5 = 3 e 13 mod 5 = 3. Nenhuma das chaves resulta em 2. | | (E) | 3 | Correto. Ambas as chaves (78 e 13) são mapeadas para o compartimento 3 pela função h(x) = x mod 5 (78 mod 5 = 3 e 13 mod 5 = 3), indicando que uma colisão ocorrerá neste compartimento. |

Conclusão

Ao aplicar a função de dispersão h(x) = x mod 5 às chaves 78 e 13, verificamos que ambas as chaves são mapeadas para o compartimento 3. Essa situação, onde chaves diferentes são mapeadas para o mesmo compartimento, caracteriza uma colisão. Portanto, o compartimento 3 será o local onde a colisão ocorrerá. A gestão de colisões é um aspecto crítico na implementação de tabelas hash eficientes para garantir o bom desempenho da estrutura de dados.

Alternativa (E).