Considere agora a tabela de hash simples com tamanho variável, que é expandida caso a sua ocupação chegue à metade do seu tamanho e que também permite remoção de elementos. Para isso tem o indicador de ativo ou removido proposto no exercício 3. Acrescente a função Encolha() que diminui o tamanho da tabela, caso a sua ocupação chegue a
do seu tamanho.
Passo 1
Ok, vamos lá! O exercício pede para a gente trabalhar com uma tabela de hash que pode mudar de tamanho. Essa tabela já muda de tamanho quando fica com a metade das posições ocupadas (50%) e permite remover elementos usando um indicador de “ativo” ou “removido”. Agora, a gente tem que adicionar uma função chamada Encolha() que diminui o tamanho da tabela quando só 25% das posições estão ocupadas. Vamos precisar entender como as tabelas de hash funcionam, como gerenciar o tamanho delas e como implementar essa lógica de encolher a tabela.
Passo 2
Primeiro, vamos lembrar o que é uma tabela de hash. É uma estrutura de dados que usa uma função de hash para mapear chaves a índices de um array. Isso permite buscas, inserções e remoções rápidas. Quando a tabela fica muito cheia (50% no nosso caso), a gente aumenta o tamanho dela para evitar colisões e manter a eficiência.
Passo 3
Agora, como a tabela já aumenta de tamanho quando a ocupação chega a 50%, queremos adicionar a possibilidade de diminuir o tamanho quando a ocupação cai para 25%. Isso é importante para economizar espaço quando não estamos usando tanto da tabela.
Passo 4
Para implementar a função Encolha(), vamos seguir alguns passos:
- Verificar a ocupação atual: Precisamos saber quantas posições estão realmente ocupadas na tabela.
- Calcular a taxa de ocupação: Dividimos o número de elementos ativos pelo tamanho total da tabela.
- Decidir se encolher: Se a taxa de ocupação for menor ou igual a 25%, podemos diminuir o tamanho da tabela.
- Reduzir o tamanho da tabela: Geralmente, dobramos ou dobramos o tamanho, mas no caso de encolher, vamos dividir o tamanho atual por um fator, como 2.
- Rehashing dos elementos: Depois de mudar o tamanho, precisamos reorganizar os elementos na nova tabela usando a função de hash novamente.
Passo 5
Vamos detalhar cada passo:
-
Verificar a ocupação atual:
- Conte quantos elementos estão ativos na tabela.
-
Calcular a taxa de ocupação:
- Use a fórmula:
- Use a fórmula:
-
Decidir se encolher:
- Se
, então precisamos encolher a tabela.
- Se
-
Reduzir o tamanho da tabela:
- Por exemplo, se o tamanho atual for
, o novo tamanho pode ser . - Certifique-se de que o novo tamanho não seja menor que um mínimo pré-estabelecido.
- Por exemplo, se o tamanho atual for
-
Rehashing dos elementos:
- Crie uma nova tabela com o tamanho reduzido.
- Percorra a tabela antiga e insira os elementos ativos na nova tabela usando a função de hash.
- Isso é necessário porque os índices podem mudar com o novo tamanho.
Passo 6
Vamos imaginar como seria o código dessa função Encolha():
def Encolha():
elementos_ativos = contar_elementos_ativos()
taxa_ocupacao = elementos_ativos / tamanho_tabela
if taxa_ocupacao <= 0.25 and tamanho_tabela > tamanho_minimo:
novo_tamanho = tamanho_tabela // 2
nova_tabela = criar_nova_tabela(novo_tamanho)
for elemento in tabela_antiga:
if elemento.ativo:
inserir_na_nova_tabela(nova_tabela, elemento.chave, elemento.valor)
tabela = nova_tabela
Passo 7
Explicando o código:
- contar_elementos_ativos(): Função que conta quantos elementos estão ativos na tabela.
- tamanho_tabela: Tamanho atual da tabela de hash.
- tamanho_minimo: Um limite inferior para o tamanho da tabela, para não diminuir demais.
- criar_nova_tabela(novo_tamanho): Cria uma nova tabela com o tamanho reduzido.
- inserir_na_nova_tabela(): Reinsere os elementos na nova tabela usando a função de hash.
Resposta
Implementamos a função Encolha() que verifica se a taxa de ocupação da tabela de hash está abaixo ou igual a 25%. Se estiver, a função reduz o tamanho da tabela pela metade e reorganiza os elementos ativos na nova tabela para manter a eficiência. Dessa forma, garantimos que a tabela de hash seja otimizada tanto para operações de inserção quanto para economia de espaço.