Cases d'une table de hachage

Une table de hachage n'est rapide que si le tableau qui la sous-tend est bien dimensionné. Lorsque vous stockez n clés dans m cases, le facteur de charge α = n / m décide de la longueur des chaînes, du moment où l'adressage ouvert s'agglutine et de la fréquence d'un redimensionnement. Un m trop petit et chaque recherche parcourt un tas de collisions. Un m trop grand et vous payez de la RAM pour des emplacements vides qui n'améliorent pas la latence. Ce calculateur de nombre de cases prend le nombre d'éléments prévu, un facteur de charge cible tel que la valeur par défaut 0.75 de Java HashMap, et une stratégie d'arrondi, puis renvoie la plus petite table que l'on puisse allouer tout en maintenant l'occupation à cette cible ou en dessous. Il calcule d'abord le plafond brut ceil(n / α), puis arrondit ce plancher à la puissance de deux suivante ou au nombre premier suivant — les deux tailles que les maps de production allouent réellement. Les tailles puissance de deux correspondent aux maps à masque qui indexent avec le ET bit à bit du hachage et (m moins un). Les tailles premières correspondent aux maps à modulo qui indexent avec hash mod m.

Pourquoi le facteur de charge, et non un chiffre rond, doit choisir les cases

Le facteur de charge est le seul nombre d'occupation qui voyage d'un langage à l'autre. Java HashMap vaut 0.75 par défaut et se redimensionne lorsque la taille dépasse la capacité multipliée par ce facteur. Rust hashbrown et de nombreux ports Swiss-table se tiennent près de 0.875 avant de grandir.

Le code pédagogique classique à chaînage séparé vise souvent 0.5 ou 1.0. Dans tous les cas l'identité de planification est la même : il faut au moins ceil(n / α) emplacements si n clés doivent rester à la cible α ou en dessous. Ce plafond brut n'est presque jamais le nombre que l'on alloue.

Les implémentations à masque exigent que m soit une puissance de deux pour que l'index soit un seul ET bit à bit, d'où 1 000 clés à 0.75 deviennent 2 048 cases et non 1 334. Les implémentations à modulo préfèrent un premier afin qu'un hachage faible se répartisse encore entre classes de résidus, d'où les mêmes 1 000 clés deviennent le premier suivant supérieur ou égal à 1 334. Servez-vous de ces cinq chiffres ensemble.

Une table qui a beaucoup monté jusqu'à la puissance de deux suivante a une charge effective confortable et un headroom large ; une table tombée sur un premier voisin est plus serrée et plus proche d'un redimensionnement. Deviner 1 024 ou 4 096 parce que ces nombres ont l'air d'informatique, c'est ainsi qu'un service gaspille une page de RAM ou déclenche un redimensionnement dès la première minute de trafic.

Quand dimensionner ainsi une table, et ses limites

Servez-vous de l'outil du navigateur lorsque vous choisissez la capacité initiale d'un HashMap, rédigez un commentaire qui doit justifier pourquoi le tableau fait 2 048 et non 1 334, ou parcourez en revue la différence entre une table à masque et une table à modulo. Balayez le facteur de charge jusqu'à ce que le headroom couvre le prochain pic de croissance, puis conservez le m arrondi.

Contrastez le résultat avec un calculateur de collisions attendues une fois m connu : ce frère répond combien de clés partagent une case, tandis que cette page répond combien de cases allouer d'abord. Les deux recherches sont des tickets distincts et ne doivent pas se cannibaliser. Les résultats sont pleinement déterministes : les mêmes items, facteur de charge et arrondi produisent toujours le même vecteur, de sorte que vous pouvez figer des exemples dans les tests et le matériel pédagogique.

Il n'y a ni modèle de langage, ni service statistique externe, ni aléa. Branchez le point de terminaison sur des tutoriels de tables de hachage, des backends de compilateur qui émettent une table statique, et des modèles de service qui doivent choisir une capacité avant la première insertion.