Collisioni hash attese

Quando si disperdono n chiavi distinte in modo uniforme in m contenitori, alcune condividono uno slot anche con un fattore di carico modesto. L'intuizione sottostima l'occupazione: si ricorda la probabilità del paradosso dei compleanni che almeno una coppia collida e si tratta quella probabilità come se fosse un conteggio. Questa calcolatrice delle collisioni hash attese risponde a un'altra domanda di dimensionamento. Impiega il modello classico delle palline e delle urne — ciascun elemento sceglie uno degli m contenitori in modo indipendente e uniforme — e restituisce il numero atteso di chiavi in collisione, cioè quelle che non sono sole nel proprio contenitore. Accanto a quella cifra principale riporta chiavi singleton, contenitori occupati e vuoti, chiavi di trabocco oltre il primo occupante, collisioni a coppie e il fattore di carico n diviso per m. L'aritmetica è un'identità in forma chiusa valutata nello spazio logaritmico, pienamente deterministica, senza campionamento Monte Carlo e senza modello linguistico. Serve a dimensionare una tabella hash, regolare un fattore di carico, confrontare uno spazio hash a 32 bit con uno più stretto o verificare un'affermazione di occupazione da manuale prima di impegnare memoria.

Cosa misurano le chiavi in collisione attese nel modello palline e urne

Lanci n palline in modo indipendente e uniforme in m urne e ottiene il modello standard di un hash uniforme. Una chiave in collisione è una pallina che condivide l'urna con almeno un'altra. Non è la stessa grandezza della probabilità del paradosso dei compleanni che almeno due palline condividano un'urna, né il numero di coincidenze a coppie.

Per pianificare la capacità di solito si vuole un conteggio: quante chiavi, in media, non ottengono uno slot privato, quanti contenitori restano vuoti mentre altri traboccano, e quante chiavi extra si accatastano sul primo occupante. La linearità del valore atteso dà risposte pulite senza simulazione. Fissi una chiave qualsiasi.

Le altre n meno una mancano il contenitore di quella chiave con probabilità uno meno uno su m, così la chance che la chiave scelta sia singleton è (1 − 1/m) elevata a n meno uno. Moltiplichi per n e ottiene il numero atteso di chiavi singleton. Sottragga da n e ottiene il numero atteso di chiavi in collisione: n volte uno meno (1 − 1/m) alla n meno uno.

Lo stesso argomento di occupazione produce il numero atteso di contenitori vuoti, m volte (1 − 1/m) alla n, e quindi quello dei contenitori occupati. Le chiavi di trabocco sono gli elementi oltre il primo in ciascun contenitore occupato, uguali a n meno occupati. Le collisioni a coppie equivalgono a n su due diviso per m, perché qualsiasi coppia specifica cade insieme con probabilità uno su m.

Il fattore di carico è semplicemente n su m. Insieme, queste cifre dicono se una tabella proposta è a corto di contenitori, è solo occupata, o sta già pagando una tassa di lunghezza di catena che un m maggiore toglierebbe.

Contratto di ingresso, formule, stabilità numerica ed errori

Invii due interi obbligatori: n, il numero di elementi, e m, il numero di contenitori. Entrambi i valori devono essere interi finiti entro i limiti pubblicati: n da uno a un bilione, e m da uno a un bilione, il che copre esempi d'aula, mappe in memoria e uno spazio hash a 32 bit completo di quattro miliardi duecento novantaquattro milioni novecentosessantasette mila duecentonovantasei slot.

Dopo la convalida il motore valuta le potenze di uno meno uno su m in spazio logaritmico come l'esponenziale dell'esponente per log1p di meno uno su m, così n e m grandi non vanno in underflow verso uno zero silenzioso come farebbe un ciclo ingenuo di moltiplicazioni.

I casi speciali restano esatti: un solo elemento non collide mai; un solo contenitore con due o più elementi fa collidere ogni chiave; un esponente zero è trattato come uno affinché (1 − 1/m) alla potenza zero non diventi uno zero alla zero indeterminato. È un oracolo di conteggio atteso sotto un hash uniforme e indipendente, non un simulatore di una particolare funzione hash né una calcolatrice di probabilità di collisione.

Pianificazione della capacità, limiti, prezzo e dove servono i numeri

Usi lo strumento del browser quando sceglie la dimensione di una tabella, confronta fattori di carico o spiega a un gruppo perché un fattore di carico pari a uno lascia ancora una quota ampia di chiavi a condividere un contenitore. Aumenti m finché le chiavi in collisione attese o quelle di trabocco scendono sotto il bilancio di livello di servizio, poi tenga un margine di crescita.

Confronti il risultato con una probabilità del paradosso dei compleanni se le serve anche la chance che esista una collisione; quella probabilità satura vicino a uno molto prima che il conteggio atteso di chiavi in collisione diventi grande, ed è per questo che i due strumenti rispondono a ticket diversi. I risultati sono pienamente deterministici: gli stessi n e m producono sempre lo stesso vettore di occupazione, così può fissare esempi in prove e materiali didattici. Non c'è modello linguistico, né servizio esterno di statistica, né casualità.