Questão nº 56
Questão de Análise de Sistemas · CESGRANRIO BNDES 01/2024 (nº 56)
Considere o seguinte código em uma linguagem de programação hipotética que possui função de hashing.
```javascript
// Linguagem Hipotética (exemplo de hashing)
class TabelaHash {
constructor(size) {
this.size = size;
this.table = new Array(size);
}
hash(key) {
return key % this.size;
}
inserir(key, value) {
const index = this.hash(key);
this.table[index] = value;
}
buscar(key) {
const index = this.hash(key);
return this.table[index];
}
}
const hashTable = new TabelaHash(10);
hashTable.inserir(15, "valor1");
hashTable.inserir(25, "valor2");
console.log(hashTable.buscar(15)); // Saída 1
console.log(hashTable.buscar(25)); // Saída 2
console.log(hashTable.buscar(35)); // Saída 3
```
Considerando-se esse código, sobre o hashing, verifica-se que a(o)
- Afunção de hash é responsável por transformar chaves distintas em índices distintos.
- Bfunção de hash garante que todas as chaves serão distribuídas uniformemente na tabela de hash.
- Ctabela de hash pode usar qualquer função de hash, independentemente do tamanho da tabela.
- Dtabela de hash poderá sobrescrever o valor existente com o novo valor se duas chaves tiverem o mesmo valor de hash. (alternativa correta)
- Evalor da chave anterior será mantido na tabela de hash se duas chaves resultarem no mesmo índice após a aplicação da função de hash.
Resposta comentada
Gabarito Alternativa D
Conceito-chave: A função de hash mapeia chaves para índices de uma tabela, mas não garante que chaves diferentes gerem índices diferentes. Quando isso acontece, chamamos de colisão, e o tratamento depende da implementação — neste código, a colisão simplesmente sobrescreve o valor anterior.
- (A) Incorreta: A função de hash não transforma chaves distintas em índices distintos; ela pode gerar o mesmo índice para chaves diferentes (colisão), como 15 e 25 com
% 10(ambos dão 5). - (B) Incorreta: A função de hash não garante distribuição uniforme; ela apenas calcula
key % size, que pode concentrar valores em poucos índices. - (C) Incorreta: A função de hash depende do tamanho da tabela (usa
% this.size), e escolher uma função inadequada ao tamanho aumenta colisões. - (D) Correta: Se duas chaves tiverem o mesmo valor de hash (ex.: 15 e 25), o
inserircalcula o mesmo índice e sobrescreve o valor anterior — por issobuscar(15)retorna "valor2" após inserir 25. - (E) Incorreta: O valor anterior não é mantido; ele é substituído pelo novo valor, como mostrado no código (a tabela armazena apenas um valor por índice).
Armadilha da banca (distrator mais tentador): A letra E parece plausível, pois sugere que a tabela "guarda" o valor antigo, mas o código não implementa listas encadeadas ou sondagem — ele apenas atribui this.table[index] = value, apagando o valor anterior. A pegadinha é confundir "colisão" com "tratamento de colisão": colisão existe, mas o tratamento aqui é por substituição, não por preservação.
Fonte: CESGRANRIO BNDES 01/2024 Analista - Análise de Sistemas (Desenvolvimento) (Caderno Prova 3). Reproduzida para fins de estudo.