Question

1.3. Sobre tabela hash, assinale a alternativa correta. Em uma tabela hash, temos uma função de espalhamento que mapeia uma determinada chave para um endereço de memória. Do ponto de vista teórico, isso permitiria obter o conteúdo desejado acessando este endereço de memória. Entretanto, do ponto de vista prático, não é possível converter chaves em endereço de memória, o que impede a implementação de tabelas hash. Em um cenário ideal sem colisões, implementar uma tabela se resumiria a criar uma função de espalhamento para indicar em qual posição de memória um elemento seria alocado. Em um cenário prático, a quantidade de colisões normalmente força o desenvolvedor a assumir que todos os elementos serão mapeados para uma mesma posição de memória. Por isso, costuma-se dizer que buscas em tabela hash não são melhores que buscas sequenciais. Ao implementar uma tabela hash internamente como um vetor e assumindo um cenário com colisões, o tratamento dessas colisões pode usar um espaço de memória adicional ou pode usar o espaço de memória do próprio vetor. Um exemplo de tratamento de colisões que usa um espaço de memória adicional é o encadeamento separado, e um exemplo de tratamento de colisões que usa o espaço do próprio vetor é o teste linear. Para tratar colisões, podemos usar uma estrutura interna como um vetor com tamanho muito maior do que o número de elementos que queremos adicionar. Como o vetor é muito grande, colisões não existirão e será possível gerar algoritmos mais simplificados. As tabelas hash são estruturas muito úteis para fazer inserção, remoção e busca de maneira eficiente. No caso da implementação interna como um vetor, mesmo com o tratamento usando teste linear que pode formar clusters de números um do lado do outro, é possível fazer uma busca eficiente usando o algoritmo de busca binária.

Answer 1

Resposta:

As tabelas hash são estruturas muito úteis para fazer inserção, remoção e busca de maneira eficiente. No caso da implementação interna como um vetor, mesmo com o tratamento usando teste linear que pode formar clusters de números um do lado do outro, é possível fazer uma busca eficiente usando o algoritmo de busca binária.