- 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
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
onde
é o número de baldes (tamanho do array interno). O custo médio de uma busca bem sucedida é
Passo 3
O problema impõe que esse custo seja 2, isto é,
Logo,
Passo 4
Como
, temos