Colisões de hash esperadas

Quando n chaves distintas são dispersas de modo uniforme em m baldes, algumas compartilham vaga mesmo com um fator de carga modesto. A intuição subestima a ocupação: as pessoas lembram a probabilidade do paradoxo do aniversário de que pelo menos um par colida e tratam essa probabilidade como se fosse uma contagem. Esta calculadora de colisões de hash esperadas responde a outra pergunta de planejamento. Usa o modelo clássico de bolas em urnas — cada item escolhe um dos m baldes de forma independente e uniforme — e devolve o número esperado de chaves em colisão, ou seja, as que não estão sozinhas no próprio balde. Ao lado dessa cifra principal informa chaves singleton, baldes ocupados e vazios, chaves de transbordo além do primeiro ocupante, colisões aos pares e o fator de carga n dividido por m. A aritmética é uma identidade de forma fechada avaliada em espaço logarítmico, totalmente determinística, sem amostragem Monte Carlo e sem modelo de linguagem. Serve para dimensionar uma tabela hash, ajustar um fator de carga, comparar um espaço de hash de 32 bits com outro mais estreito ou conferir uma afirmação de ocupação de livro antes de comprometer memória.

O que as chaves em colisão esperadas medem no modelo de bolas em urnas

Lance n bolas de forma independente e uniforme em m urnas e você terá o modelo padrão de um hash uniforme. Uma chave em colisão é uma bola que compartilha urna com pelo menos outra. Isso não é a mesma grandeza que a probabilidade do paradoxo do aniversário de que pelo menos duas bolas compartilhem urna, nem o número de coincidências aos pares.

No planejamento de capacidade costuma-se querer uma contagem: quantas chaves, em média, não conseguem uma vaga privativa, quantos baldes ficam vazios enquanto outros transbordam, e quantas chaves extras se empilham sobre o primeiro ocupante. A linearidade da esperança dá respostas limpas sem simulação. Fixe uma chave qualquer.

As outras n menos uma erram o balde dessa chave com probabilidade um menos um sobre m, de modo que a chance de a chave escolhida ser singleton é (1 − 1/m) elevada a n menos um. Multiplique por n e você terá o número esperado de chaves singleton. Subtraia de n e você terá o número esperado de chaves em colisão: n vezes um menos (1 − 1/m) na n menos um.

O mesmo argumento de ocupação produz o número esperado de baldes vazios, m vezes (1 − 1/m) na n, e portanto o de baldes ocupados. As chaves de transbordo são os itens além do primeiro em cada balde ocupado, iguais a n menos ocupados. As colisões aos pares equivalem a n escolhe dois dividido por m, porque qualquer par específico cai junto com probabilidade um sobre m.

O fator de carga é simplesmente n sobre m. Juntas, essas cifras dizem se uma tabela proposta está faminta de baldes, apenas ocupada ou já paga um imposto de comprimento de cadeia que um m maior removeria.

Contrato de entrada, fórmulas, estabilidade numérica e erros

Envie dois inteiros obrigatórios: n, o número de itens, e m, o número de baldes. Ambos os valores devem ser inteiros finitos dentro dos limites publicados: n de um a um trilhão, e m de um a um trilhão, o que cobre exemplos de sala, mapas em memória e um espaço de hash de 32 bits completo de quatro bilhões duzentos e noventa e quatro milhões novecentos e sessenta e sete mil duzentos e noventa e seis vagas.

Após a validação o motor avalia potências de um menos um sobre m em espaço logarítmico como a exponencial do expoente vezes log1p de menos um sobre m, para que n e m grandes não sofram underflow até um zero silencioso como faria um laço ingênuo de multiplicações.

Os casos especiais permanecem exatos: um único item nunca colide; um único balde com dois ou mais itens faz todas as chaves colidirem; um expoente zero é tratado como um para que (1 − 1/m) na potência zero não se torne um zero elevado a zero indeterminado. Este é um oráculo de contagem esperada sob um hash uniforme e independente, não um simulador de uma função hash particular nem uma calculadora de probabilidade de colisão.

Planejamento de capacidade, limites, preço e onde os números valem

Use a ferramenta do navegador quando for escolher o tamanho de uma tabela, comparar fatores de carga ou explicar a uma equipe por que um fator de carga igual a um ainda deixa uma fração grande de chaves compartilhando balde. Aumente m até que as chaves em colisão esperadas ou as de transbordo fiquem abaixo do orçamento de nível de serviço, e reserve uma folga para o crescimento.

Contraste o resultado com uma probabilidade do paradoxo do aniversário se também precisar da chance de existir alguma colisão; essa probabilidade satura perto de um bem antes de a contagem esperada de chaves em colisão ficar grande, por isso as duas ferramentas respondem a chamados diferentes. Os resultados são totalmente determinísticos: os mesmos n e m sempre produzem o mesmo vetor de ocupação, de modo que você pode fixar exemplos em testes e materiais didáticos. Não há modelo de linguagem, serviço externo de estatística nem aleatoriedade.