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 25 % 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:
  1. Verificar a ocupação atual: Precisamos saber quantas posições estão realmente ocupadas na tabela.
  2. Calcular a taxa de ocupação: Dividimos o número de elementos ativos pelo tamanho total da tabela.
  3. Decidir se encolher: Se a taxa de ocupação for menor ou igual a 25%, podemos diminuir o tamanho da tabela.
  4. 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.
  5. 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:
  1. Verificar a ocupação atual:
    • Conte quantos elementos estão ativos na tabela.
  2. Calcular a taxa de ocupação:
    • Use a fórmula: Taxa de Ocupação = Número de e<=mentos ativosTamanho da tabela çãú
  3. Decidir se encolher:
    • Se Taxa de Ocupação <= 0,25çã, então precisamos encolher a tabela.
  4. Reduzir o tamanho da tabela:
    • Por exemplo, se o tamanho atual for N, o novo tamanho pode ser N/2.
    • Certifique-se de que o novo tamanho não seja menor que um mínimo pré-estabelecido.
  5. 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.

Exercícios relacionados