Carregando...
Carregando...
Ajude a melhorar a plataforma
Suponha que existam 𝑛 chaves a serem armazenadas em uma tabela 𝑇, sequencial e de dimensão 𝑚. As posições da tabela se situam no intervalo [0,m−1][0, m-1]. Em um caso simples, onde o número de chaves nn n é igual ao número de compartimentos 𝑚, os valores das chaves são 0, 1, ..., m−1m-1 Utiliza-se diretamente o valor de cada chave como seu índice na tabela, técnica conhecida como acesso direto. No entanto, para resolver a questão de armazenamento eficiente quando n<mn e m−nm-n é grande, emprega-se a função de dispersão h(x)h(x), que transforma cada chave 𝑥 em um valor no intervalo [0,m−1][0, m-1]. Se o compartimento h(x)h(x) estiver ocupado, ocorre uma colisão, é um procedimento especial é usado para o armazenamento de 𝑥.
Dada a função de dispersão h=xmod5h = x \bmod 5 e as chaves 78 e 13, qual é o compartimento da tabela que causará a colisão?
Explique melhor esta questão
Abre o Tutor com o enunciado e as alternativas já no campo — você revisa e envia.
Esta questão foi verificada por um de nossos administradores.
Alternativa (E) - Compartimento 3
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.
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.
Vamos aplicar a função de dispersão h(x) = x mod 5 a cada chave fornecida:
Para a chave x = 78:
h(78) = 78 mod 5.78 ÷ 5 = 15 com um resto de 3.h(78) = 3. Isso significa que a chave 78 seria armazenada no compartimento de índice 3.Para a chave x = 13:
h(13) = 13 mod 5.13 ÷ 5 = 2 com um resto de 3.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. |
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).