Na implementação de tabelas Hash, quando as chaves não são perfeitamente distribuídas, é preciso lidar com as potenciais colisões que ocorrem quando:
- A)o espaço de endereçamento é superior ao número de chaves armazenadas;
Errada: o fato de o espaço de endereçamento ser maior que o número de chaves não define colisão, porque colisão ocorre quando chaves distintas caem no mesmo índice.
- B)duas ou mais chaves têm o mesmo índice na tabela;
Certa: há colisão quando duas ou mais chaves diferentes geram o mesmo índice na tabela Hash.
- C)as chaves são exclusivamente numéricas;
Errada: o tipo da chave não determina colisão; chaves numéricas também podem colidir dependendo da função Hash.
- D)as chaves são exclusivamente alfanuméricas;
Errada: chaves alfanuméricas também podem gerar colisões, então o formato da chave não resolve o problema.
- E)há duplicação de chaves.
Errada: duplicação de chaves pode ser um problema lógico de dados, mas colisão em Hash é quando chaves diferentes compartilham o mesmo índice.
Gabarito: B
Em tabelas Hash, a ideia é transformar uma chave em um índice da tabela para buscar e armazenar dados rapidamente. O problema aparece quando duas chaves diferentes acabam apontando para o mesmo índice. Isso é o que se chama de colisão, e acontece justamente porque a distribuição das chaves não é perfeita. Quando isso ocorre, a estrutura precisa de um mecanismo para tratar esse choque de endereço, como encadeamento ou endereçamento aberto. Perceba que colisão não tem relação com a chave ser numérica ou alfanumérica, nem com haver duplicação de chaves. O ponto central é o mapeamento para o mesmo índice. Em outras palavras: chaves diferentes, mesmo endereço. A tabela Hash até tenta ser organizada, mas às vezes duas visitas chegam na mesma cadeira ao mesmo tempo. Por isso, o gabarito é a letra B. Se duas ou mais chaves têm o mesmo índice na tabela, há colisão e ela precisa ser tratada. Esse é o conceito clássico de hashing apresentado em livros de estrutura de dados e fundamentos de organização de arquivos e acesso rápido a registros.