Tabela de Dispersão Dinâmica

Imagine que você possui um pequeno móvel com quatro compartimentos:

Com o tempo, você percebe que o móvel está ficando cheio e decide comprar um novo móvel com o dobro do tamanho, para ter mais espaço e organização.

No novo móvel, os relógios podem ficar em posições diferentes, por exemplo, o Ferrari agora pode ser guardado no compartimento 6. Além disso, você adquire um novo relógio Rolex e o coloca no compartimento 5.

Mais tarde, você decide presentear seu melhor amigo com o relógio Xing-ling e vender o Casio. Para completar, um dos relógios acaba sendo roubado. Agora, dos oito compartimentos, apenas um está ocupado. Um grande desperdício de espaço.

Diante disso, você decide trocar novamente de móvel, voltando a um modelo menor, com quatro compartimentos, mais adequado à sua nova coleção.

Esse comportamento de aumentar ou diminuir o número de compartimentos conforme a quantidade de itens é exatamente o que ocorre em uma tabela hash dinâmica.

Em resumo, ela funciona como um “guarda-roupa inteligente” que se adapta automaticamente:

Essa capacidade de ajustar dinamicamente o tamanho permite que a tabela hash mantenha alto desempenho e uso eficiente de memória, independentemente do número de elementos armazenados.

Fator de Carga

O fator de carga (load factor) determina quando uma tabela hash deve ser expandida ou contraída. Ele é definido como a razão entre o número de elementos armazenados e o número total de buckets (ou posições disponíveis na tabela): \[\lambda = \frac{n}{m}\] onde \(n\) é o número de itens atualmente armazenados e \(m\) o tamanho da tabela.

O desempenho ideal de uma tabela hash depende de duas condições principais:

  • uma função hash eficiente, que distribua os elementos de forma uniforme;
  • um fator de carga baixo, que mantenha o número de colisões sob controle.

Se o fator de carga \(\lambda\) for muito alto, o número de colisões tende a crescer, e as operações de busca, inserção e remoção podem degradar de O(1) para O(n). Por outro lado, se \(\lambda\) for muito baixo, haverá desperdício de espaço, pois a tabela ficará com muitos buckets vazios.

O coração de uma tabela hash dinâmica é justamente o processo de redimensionamento, que ajusta o tamanho da tabela conforme o fator de carga ultrapassa (ou cai abaixo de) determinados limites predefinidos. Por exemplo,

  • expansão: quando \(\lambda>0.7\) ou \(\lambda>0.75\);
  • contração: quando \(\lambda<0.25\).

O processo de redimensionamento normalmente envolve três etapas principais:

1. Criação de uma nova tabela

Uma nova tabela é alocada, geralmente com o dobro (em caso de expansão) ou metade (em caso de contração) do tamanho atual.

2. Re-hashing dos elementos

Todos os elementos da tabela antiga são reprocessados por uma nova função hash e inseridos na nova tabela, agora com índices recalculados conforme o novo tamanho.

3. Substituição

A tabela antiga é descartada, e a nova tabela passa a ser usada nas próximas operações de inserção, busca e remoção.

Finalmente, podemos citar como vantagens e desvantagens da tabela hash dinâmica:

Otimização do espaço

A tabela se ajusta à quantidade de dados, evitando desperdício de memória quando há poucos itens e garantindo espaço suficiente para muitos itens.

Desempenho consistente

Ajuda a manter o fator de carga em níveis ótimos, garantindo que as operações de O(1) sejam mantidas na média.

Facilidade de uso

O desenvolvedor não precisa se preocupar em prever o tamanho da tabela, simplificando o desenvolvimento.

Custo do redimensionamento

A operação de redimensionamento pode ser custosa, pois envolve a criação de uma nova tabela e o re-hashing de todos os elementos. Isso pode levar a picos de latência inesperados.

Complexidade de implementação

É mais complexa de implementar do que uma tabela hash estática.

Cache ineficiente durante redimensionamento

Durante o re-hashing, os dados podem se espalhar por novas posições de memória, o que pode impactar o desempenho do cache da CPU temporariamente.

Nesta unidade, você aprendeu

✅ o que é uma tabela de dispersão dinâmica

✅ a calcular o fator de carga

✅ a importância do fator de carga no desempenho de uma tabela de dispersão

# O que caracteriza uma tabela hash dinâmica? > Pense na principal diferença em relação à tabela hash estática. 1. [ ] Uma tabela que nunca sofre colisões. 1. [x] Uma tabela que ajusta automaticamente seu tamanho conforme a quantidade de elementos. 1. [ ] Uma tabela que usa múltiplas funções hash ao mesmo tempo. 1. [ ] Uma tabela implementada apenas com encadeamento separado. # Quando uma tabela hash deve **expandir** seu tamanho? > Observe o limite superior do fator de carga. 1. [ ] Quando $\lambda < 0.25$ 1. [x] Quando $\lambda > 0.7$ 1. [ ] Quando $\lambda = 0$ 1. [ ] Quando $\lambda = 1$ # Quando uma tabela hash deve **contrair** seu tamanho? > O texto cita o limite inferior. 1. [x] Quando $\lambda < 0.25$ 1. [ ] Quando $\lambda > 0.7$ 1. [ ] Quando $\lambda > 1$ 1. [ ] Quando $\lambda = 0.75$ # O que representa o fator de carga $\lambda$? > Lembre-se da fórmula apresentada. 1. [x] A razão entre o número de elementos armazenados e o tamanho total da tabela. 1. [ ] A soma dos índices ocupados da tabela. 1. [ ] O número de colisões dividido pelo tamanho da tabela. 1. [ ] O tempo médio de inserção em O(n). # Quais são as etapas do processo de redimensionamento? > Coloque as três fases na ordem correta. 1. Criação de uma nova tabela. 2. Re-hashing dos elementos. 3. Substituição da tabela antiga. # Quais são vantagens da tabela hash dinâmica? > Elas estão listadas na seção de “Vantagens”. - [x] Otimização do uso de memória. - [x] Manutenção do desempenho médio em O(1). - [x] Facilidade de uso para o programador. - [ ] Nenhum custo de redimensionamento. # Quais são desvantagens da tabela hash dinâmica? > Observe os impactos durante o redimensionamento. - [x] Custo alto durante o redimensionamento. - [x] Maior complexidade de implementação. - [x] Possível perda temporária de desempenho de cache. - [ ] Impossibilidade de armazenar chaves duplicadas. # Se uma tabela tem 30 elementos e 50 posições, qual é o fator de carga $\lambda$? > Use $\lambda = \frac{n}{m}$. 1. [ ] 0,25 1. [x] 0,6 1. [ ] 1,25 1. [ ] 0,15 # Qual é a consequência de um fator de carga muito alto? > Relacione com o número de colisões. 1. [x] Aumento das colisões e degradação do desempenho. 1. [ ] Redução do número de colisões. 1. [ ] Melhoria no uso do cache da CPU. 1. [ ] Economia de memória. # Qual analogia do texto representa melhor o comportamento da tabela hash dinâmica? > Pense no exemplo do móvel. 1. [ ] Um armário que só aumenta e nunca diminui. 1. [x] Um móvel que expande e contrai conforme a quantidade de relógios. 1. [ ] Um cofre com compartimentos fixos. 1. [ ] Um sistema de arquivos linear.
De volta ao topo