Pourquoi y a-t-il un « nombre magique » dans boost::hash_combine ?

Que signifie le « nombre magique » dans boost::hash_combine ?

Question :

Le boost : La fonction hash_combine intègre un « nombre magique » (0x9e3779b9) dans son opération de hachage. Quel est le but et la signification de ce nombre ?

Réponse :

Le nombre magique dans boost::hash_combine est une valeur de 32 bits dérivée de l'inverse du nombre d'or (phi). Il ne contient aucun modèle perceptible et a une distribution à peu près égale de 0 et de 1. Son inclusion remplit plusieurs fonctions :

• Randomisation : Le nombre magique agit comme un flipper de bits aléatoire, affectant chaque bit du hachage de graine. Cela augmente la probabilité que des valeurs similaires soient mappées à distance, réduisant ainsi les collisions de tables de hachage.
• Propagation : Le nombre magique est ajouté au hachage de la valeur combinée (hash_value(v) ) et les versions décalées de la graine elle-même ((seed << 6) (seed >> 2)). Cela garantit que même si hash_value(v) a une plage limitée, les différences entre les valeurs consécutives seront réparties sur tous les bits de la graine au fil du temps.

En combinant la randomisation et la propagation, le nombre magique aide répartissez les valeurs uniformément dans les tables de hachage, atténuant ainsi le potentiel de dégradation des performances causée par le clustering.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!