Calculadora do Fator de Carga de uma Tabela de Dispersão (Sondagens Esperadas: Linear, Dupla, Encadeamento)
O fator de carga de uma tabela de dispersão e o número médio de sondagens de uma pesquisa — em sondagem linear, dispersão dupla e encadeamento — mais o tamanho da tabela que a mantém abaixo de uma carga escolhida.
Resultados
A linha tracejada marca o valor que escreveu.
O que faz esta ferramenta
Uma tabela de dispersão só é rápida enquanto não está demasiado cheia. Com sondagem linear, procurar uma chave que não existe custa em média 2,5 sondagens com fator de carga 0,5, mas 50,5 com 0,9; a dispersão dupla é mais branda (10 a 0,9) e o encadeamento degrada-se suavemente, já que uma carga acima de 1 só quer dizer cadeias mais compridas. As tabelas de endereçamento aberto redimensionam-se por isso muito antes de encher — muitas vezes entre 50 % e 75 % de carga. São as médias de Knuth para uma boa função de dispersão.
Fórmula
α = n ÷ m · linear probing: hit ½(1 + 1/(1−α)), miss ½(1 + 1/(1−α)²) · double hashing: hit (1/α) ln(1/(1−α)), miss 1/(1−α) · chaining: hit 1 + α/2, miss α
Variáveis
| Símbolo | Significado | Unidade |
|---|---|---|
n | Elementos guardados | — |
m | Tamanho da tabela (posições ou baldes) | — |
ml | Maior fator de carga que quer permitir | — |
LU | Sondagem linear: sondagens se o elemento não existe | — |
LF | Fator de carga α (elementos ÷ posições) | — |
LS | Sondagem linear: sondagens para encontrar um elemento | — |
DS | Dispersão dupla: sondagens para encontrar um elemento | — |
DU | Dispersão dupla: sondagens se o elemento não existe | — |
CS | Encadeamento: comparações para encontrar um elemento | — |
CU | Encadeamento: comparações se o elemento não existe | — |
SZ | Tamanho da tabela que mantém a carga no seu limite | — |
Exemplo resolvido
- Elementos guardados700
- Tamanho da tabela (posições ou baldes)1000
- Maior fator de carga que quer permitir0,7
- Sondagem linear: sondagens se o elemento não existe6,06
- Fator de carga α (elementos ÷ posições)0,700
- Sondagem linear: sondagens para encontrar um elemento2,17
- Dispersão dupla: sondagens para encontrar um elemento1,72
- Dispersão dupla: sondagens se o elemento não existe3,33
- Encadeamento: comparações para encontrar um elemento1,35
- Encadeamento: comparações se o elemento não existe0,70
- Tamanho da tabela que mantém a carga no seu limite1000
Limitações
- A fórmula assume condições ideais: sem perdas por atrito, sem resistência do ar e sem perdas de rendimento, a não ser que as introduza.
- O resultado é uma estimativa baseada apenas nos valores que introduziu. Situações reais incluem muitas vezes fatores que esta calculadora desconhece.