Fator de carga em tabelas hash
O fator de balanceamento (ou load factor) é uma medida que indica o grau de ocupação de uma tabela hash.
Ele informa quantas posições da tabela hash já estão ocupadas em relação ao total disponível.
É calculado com a fórmula:
Por exemplo:
- Se uma tabela hash tem capacidade para 10 posições e 5 delas estão ocupadas, o fator de balanceamento será:
Para que serve o Fator de Balanceamento?
O fator de balanceamento é importante porque ajuda a controlar a eficiência da tabela hash. Ele indica quando é necessário ajustar a estrutura para evitar problemas como colisões excessivas (quando muitos elementos são mapeados para a mesma posição) e perda de desempenho.
1. Controle de Colisões:
- À medida que o fator de balanceamento aumenta (a tabela fica mais cheia), as chances de colisões também aumentam.
- Colisões podem tornar a busca, inserção e remoção mais lentas, especialmente em métodos como encadeamento ou endereçamento aberto.
2. Rehashing (Redimensionamento):
- Quando o fator de balanceamento atinge um valor crítico (geralmente próximo de 0,7 ou 70%), pode ser necessário aumentar o tamanho da tabela.
- Esse processo é chamado de rehashing, em que os elementos são reorganizados em uma tabela maior.
- Isso reduz o fator de balanceamento e melhora o desempenho.
3. Eficiência do Algoritmo:
- Um fator de balanceamento muito baixo (
) pode indicar desperdício de espaço, porque a tabela está muito grande para poucos elementos. - O ideal é encontrar um equilíbrio entre espaço disponível e número de elementos.