1. Você planeja inserir 1000 itens em uma tabela hash e quer um número médio de 2 acessos em uma busca com sucesso. Qual o tamanho do array interno que você pode utilizar considerando que a tabela tem endereçamento fechado e usa chaining para resolver os conflitos?

Passo 1

O enunciado diz que serão inseridos n=1000 itens em uma tabela hash com endereçamento fechado (encadeamento) e que desejamos um número médio de 2 acessos em uma busca com sucesso. Para resolver, vamos usar a teoria de custo médio de buscas bem sucedidas em tabelas com chaining.

Passo 2

Em tabelas com encadeamento, define-se a carga como
\alpha = \frac{n}{m},
onde m é o número de baldes (tamanho do array interno). O custo médio de uma busca bem sucedida é
1 + \frac{\alpha}{2}.

Passo 3

O problema impõe que esse custo seja 2, isto é,
1 + \frac{\alpha}{2} = 2.
Logo,
\frac{\alpha}{2} = 1 \quad\implies\quad \alpha = 2.

Passo 4

Como \alpha = n/m, temos
m = \frac{n}{\alpha} = \frac{1000}{2} = 500.

Resposta

500

Exercícios relacionados