Baldes da tabela hash
Planeje 1.000 chaves com fator de carga de 0,75 e você precisa de pelo menos 1.334 baldes, que sobem para 2.048 como potência de dois. Você também vê a carga real, quantas chaves cabem e a folga que sobra. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- Itens
- 1.000
- Fator de carga
- 0,75
- Arredondamento
- Power of two
- Mínimo de buckets
- 1.334
- Buckets
- 2.048
- Fator de carga real
- 0,48828125
- Capacidade
- 1.536
Uma tabela hash só é rápida se o arranjo por trás dela tiver o tamanho certo. Se você guarda n chaves em m baldes, o fator de carga α = n / m decide quanto as cadeias crescem, quando o endereçamento aberto se agrupa e com que frequência um redimensionamento dispara. Se escolher um m pequeno demais, cada consulta percorre um monte de colisões. Se escolher um m grande demais, paga RAM por vagas vazias que não melhoram a latência. Esta calculadora de baldes de tabela hash recebe a contagem prevista de itens, um fator de carga alvo como o padrão 0.75 do Java HashMap e uma estratégia de arredondamento, e devolve a menor tabela alocável que mantém a ocupação nesse alvo ou abaixo dele. Primeiro calcula o teto bruto ceil(n / α) e depois arredonda esse piso para a próxima potência de dois ou o próximo primo — os dois tamanhos que os mapas de produção realmente alocam. Tamanhos potência de dois combinam com mapas baseados em máscara que indexam com o AND bit a bit do hash e (m menos um). Tamanhos primos combinam com mapas baseados em módulo que indexam com hash mod m.
Por que o fator de carga, e não um chute redondo, deve escolher os baldes
O fator de carga é o único número de ocupação que viaja entre linguagens. O Java HashMap usa 0.75 por padrão e redimensiona quando o tamanho supera a capacidade vezes esse fator. O Rust hashbrown e muitos portos de Swiss-table ficam perto de 0.875 antes de crescer.
O código clássico de ensino com encadeamento separado costuma mirar 0.5 ou 1.0. Em todos os casos a identidade de planejamento é a mesma: é preciso pelo menos ceil(n / α) vagas se n chaves devem ficar no alvo α ou abaixo dele. Esse teto bruto quase nunca é o número que se aloca.
Implementações baseadas em máscara exigem que m seja potência de dois para que o índice seja um único AND bit a bit, e por isso 1 000 chaves a 0.75 viram 2 048 baldes e não 1 334. Implementações baseadas em módulo preferem um primo para que um hash fraco ainda se espalhe pelas classes de resíduos, e por isso as mesmas 1 000 chaves viram o próximo primo em ou acima de 1 334. Use essas cinco cifras juntas.
Uma tabela que subiu bastante até a próxima potência de dois tem carga efetiva folgada e headroom amplo; uma que caiu num primo próximo fica mais justa e mais perto de um redimensionamento. Chutar 1 024 ou 4 096 porque esses números parecem de ciência da computação é como um serviço desperdiça uma página de RAM ou dispara um redimensionamento no primeiro minuto de tráfego.
Quando dimensionar uma tabela assim, e seus limites
Use a ferramenta do navegador quando for escolher a capacidade inicial de um HashMap, escrever um comentário que precise defender por que o arranjo é 2 048 e não 1 334, ou percorrer com uma revisão a diferença entre uma tabela de máscara e uma de módulo. Varra o fator de carga até o headroom cobrir o próximo pico de crescimento e conserve o m arredondado.
Contraste o resultado com uma calculadora de colisões esperadas depois que m for conhecido: essa irmã responde quantas chaves compartilham um balde, enquanto esta página responde quantos baldes alocar em primeiro lugar. As duas buscas são tickets distintos e não devem se canibalizar. Os resultados são plenamente determinísticos: os mesmos items, fator de carga e arredondamento produzem sempre o mesmo vetor, de modo que você pode fixar exemplos em testes e materiais de aula.
Não há modelo de linguagem, nem serviço externo de estatística, nem aleatoriedade.
Casos de uso
Capacidade inicial de HashMap e dicionário
Informe o tamanho previsto do conjunto de trabalho e 0.75 (ou o padrão do seu runtime) para obter o arranjo potência de dois que Java, Rust e a maioria dos mapas de máscara devem alocar.
Tabelas de módulo com tamanho primo
Dimensione mapas clássicos de encadeamento separado ou no estilo Hashtable que indexam com hash módulo m arredondando o piso de ocupação até o próximo primo.
Geradores, revisões e oráculos de CI
Geradores de código e plataformas de entrevista chamam um oráculo de dimensionamento determinístico que recusa uma contagem de itens ausente e devolve o mesmo campo buckets para os mesmos n e α.
Perguntas frequentes
Devo arredondar a contagem de baldes para uma potência de dois ou para um primo?
Use prime para mapas baseados em módulo como o Hashtable clássico do Java, para que um hash fraco ainda se espalhe pelas classes de resíduos.
A calculadora de baldes de tabela hash é gratuita?
A ferramenta do navegador roda grátis no seu dispositivo.
Qual fator de carga devo escolher?
Depende da tabela que você vai usar. O HashMap do Java usa 0,75 por padrão, muitos projetos no estilo Swiss table, como o hashbrown do Rust, ficam perto de 0,875, e códigos didáticos costumam mirar 0,5 ou 1,0. Ajuste a meta à tabela que vai guardar os dados.
O que significam capacidade e folga?
Capacidade é quantas chaves a tabela arredondada comporta antes de passar da carga alvo; folga é a capacidade menos as suas chaves. Com 1.000 chaves a 0,75 em 2.048 baldes, a capacidade é 1.536 e a folga, 536.
Por que a carga real fica abaixo da minha meta?
Porque o número de baldes é arredondado para cima até um tamanho que as tabelas realmente alocam. Subir de 1.334 para 2.048 deixa uma carga real de 0,48828125, bem abaixo de 0,75, e afasta o próximo redimensionamento.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/dev/hash-table-capacity \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"items":1000,"load_factor":0.75}'const res = await fetch("https://api.kit.forhosting.com/dev/hash-table-capacity", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"items": 1000,
"load_factor": 0.75
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/hash-table-capacity",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"items": 1000,
"load_factor": 0.75
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/hash-table-capacity", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"items":1000,"load_factor":0.75}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"items":1000,"load_factor":0.75}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/hash-table-capacity", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"items": 1000,
"load_factor": 0.75
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.hash_table_capacity",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Limites
max_items | 1000000000 |
min_load_factor | 0.05 |
max_load_factor | 1 |
max_buckets | 34359738368 |
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Por que o fator de carga, e não um chute redondo, deve escolher os baldes
Esta calculadora deixa explícita essa decisão em dois passos: informa min_buckets (o piso de ocupação), buckets (a alocação arredondada), actual_load_factor (n / m, sempre no alvo ou abaixo depois do arredondamento), capacity (quantas chaves cabem antes de cruzar o alvo) e headroom (capacity menos n).
Contrato de entrada, modos de arredondamento, fórmulas e erros
Potências de dois são achadas dobrando, não com truques de 32 bits, de modo que tamanhos acima de dois elevado a trinta e um continuam inteiros seguros exatos. Primos são achados por divisão de tentativa em candidatos ímpares. Envie por POST um corpo JSON com dois campos obrigatórios e um opcional. items é a contagem prevista de chaves, um inteiro de um a um bilhão; aceitam-se os aliases n, count, expected e keys. load_factor é a α alvo, um número finito de 0.05 a 1 inclusive; aceitam-se os aliases load e alpha. 0.75 é o exemplo e o padrão do Java; 1.0 é uma tabela cheia; valores abaixo de 0.05 são recusados porque descrevem um arranjo quase vazio, não um mapa de trabalho. rounding é um enum, power_of_two ou prime, e vale power_of_two quando omitido; aceitam-se os aliases mode e strategy. Um domínio finito pertence ao enum para o formulário pintar um seletor e a API recusar grafias inventadas. Depois da validação o motor calcula min_buckets = ceil(items / load_factor), corrige um único passo de ponto flutuante se o produto ainda ficar abaixo de n e define buckets como a próxima potência de dois ou o próximo primo em ou acima desse piso. O JSON repete items, load_factor e rounding e depois devolve min_buckets, buckets, actual_load_factor, capacity, headroom, is_power_of_two, is_prime, um campo bits só no caminho potência de dois (logaritmo na base dois de m) e uma cadeia formula. Se faltar items, o fator de carga ficar fora da faixa publicada, a contagem não for inteira ou o arredondamento for desconhecido, a tarefa falha com invalid_input nomeando o campo e não é cobrada. Isto é um oráculo de dimensionamento, não uma contagem de colisões esperadas: combine com uma ferramenta de ocupação de bolas em urnas se também precisar de quantas chaves vão compartilhar vaga depois de escolher m.
Onde uma API de contagem de baldes se paga, limites e preço
Use a API quando um gerador de código, um ambiente de entrevistas, um planejador de fragmentos de cache ou uma checagem de integração contínua precisar de JSON estável para muitos pares (n, α) sob o mesmo contrato. Cada solicitação correta é um item faturável a US$ 0,002; validação falha não consome saldo. As faixas publicadas mantêm cada contagem devolvida dentro de inteiros seguros IEEE-754 ordinários e cobrem todo mapa em memória que você dimensionaria à mão, de um exemplo de sala com oito chaves até uma tabela de internamento com um bilhão de entradas. Ligue o endpoint a tutoriais de tabela hash, backends de compilador que emitem uma tabela estática e modelos de serviço que precisam escolher uma capacidade antes da primeira inserção.
Perguntas técnicas
Como escolher o número de baldes de uma tabela hash a partir de n itens e um fator de carga?
Envie items (ou n) e load_factor (por exemplo 0.75). A calculadora devolve min_buckets = ceil(n/α) e buckets arredondado para a próxima potência de dois ou o próximo primo, mais a carga efetiva, capacity e headroom.
Qual é a diferença entre min_buckets e buckets?
min_buckets é o piso de ocupação ceil(items / load_factor). buckets é esse piso arredondado para um tamanho alocável. Assim actual_load_factor = items / buckets fica no alvo ou abaixo dele.
O que acontece se items estiver ausente ou o fator de carga estiver fora da faixa?
A solicitação falha com invalid_input nomeando o campo. items deve ser um inteiro de 1 a 1 000 000 000; load_factor deve ser um número finito de 0.05 a 1. Falhas de validação não são cobradas.