Contenitori tabella hash

Una tabella hash è veloce solo se l'array che la sostiene ha la misura giusta. Se Lei memorizza n chiavi in m contenitori, il fattore di carico α = n / m decide quanto si allungano le catene, quando l'indirizzamento aperto si agglomera e con quale frequenza scatta un ridimensionamento. Un m troppo piccolo e ogni ricerca attraversa un mucchio di collisioni. Un m troppo grande e Lei paga RAM per slot vuoti che non migliorano la latenza. Questo calcolatore del numero di contenitori prende il conteggio previsto degli elementi, un fattore di carico obiettivo come il valore predefinito 0.75 di Java HashMap e una strategia di arrotondamento, poi restituisce la tabella assegnabile più piccola che tiene l'occupazione a quel traguardo o sotto. Calcola prima il soffitto grezzo ceil(n / α) e poi arrotonda quel pavimento alla potenza di due successiva o al primo successivo — le due misure che le mappe di produzione assegnano davvero. Le misure potenza di due coincidono con le mappe a maschera che indicizzano con l'AND bit a bit dell'hash e (m meno uno). Le misure prime coincidono con le mappe a modulo che indicizzano con hash mod m.

Perché il fattore di carico, e non un numero tondo, deve scegliere i contenitori

Il fattore di carico è l'unico numero di occupazione che viaggia tra i linguaggi. Java HashMap vale 0.75 per impostazione predefinita e si ridimensiona quando la dimensione supera la capacità per quel fattore. Rust hashbrown e molti porting Swiss-table restano vicino a 0.875 prima di crescere.

Il codice didattico classico a concatenamento separato mira spesso a 0.5 o 1.0. In ogni caso l'identità di pianificazione è la stessa: servono almeno ceil(n / α) slot se n chiavi devono restare al traguardo α o sotto. Quel soffitto grezzo quasi mai è il numero che si assegna.

Le implementazioni a maschera esigono che m sia una potenza di due così l'indice è un solo AND bit a bit, ed è per questo che 1 000 chiavi a 0.75 diventano 2 048 contenitori e non 1 334. Le implementazioni a modulo preferiscono un primo così un hash debole si sparge ancora tra le classi di residui, ed è per questo che le stesse 1 000 chiavi diventano il primo successivo maggiore o uguale a 1 334. Usi insieme quelle cinque cifre.

Una tabella salita di molto fino alla potenza di due successiva ha un carico effettivo comodo e un headroom ampio; una caduta su un primo vicino è più stretta e più prossima a un ridimensionamento. Indovinare 1 024 o 4 096 perché quei numeri sembrano informatica è il modo in cui un servizio spreca una pagina di RAM o subisce un ridimensionamento nel primo minuto di traffico.

Quando dimensionare così una tabella, e i suoi limiti

Usi lo strumento del browser quando sceglie la capacità iniziale di un HashMap, scrive un commento che deve difendere perché l'array è 2 048 e non 1 334, o guida una revisione attraverso la differenza tra una tabella a maschera e una a modulo. Percorra il fattore di carico finché il headroom copre il prossimo picco di crescita, poi tenga l'm arrotondato.

Confronti il risultato con un calcolatore di collisioni attese una volta noto m: quel fratello risponde quante chiavi condividono un contenitore, mentre questa pagina risponde quanti contenitori assegnare per primi. Le due ricerche sono ticket distinti e non devono cannibalizzarsi. I risultati sono pienamente deterministici: gli stessi items, fattore di carico e arrotondamento producono sempre lo stesso vettore, così Lei può fissare esempi in prove e materiali didattici.

Non c'è modello linguistico, né servizio statistico esterno, né casualità.