Pourquoi boost::hash_combine n'est-il pas le meilleur moyen de combiner des valeurs de hachage en C ?

Meilleure façon de combiner des valeurs de hachage en C : Démystifier boost::hash_combine

Dans le monde du C, boost::hash_combine est souvent présenté comme la méthode optimale pour combiner les valeurs de hachage. Cela soulève la question : pourquoi est-ce la meilleure approche ?

Comprendre boost::hash_combine

La fonction boost::hash_combine prend deux arguments : une valeur de départ et un valeur à hacher. Il utilise ensuite une série de manipulations de bits pour combiner les valeurs, ce qui donne lieu à une nouvelle graine qui intègre l'entropie du hachage précédent.

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

Pourquoi n'est-il pas le meilleur ?

Étonnamment, boost::hash_combine n'est pas aussi optimal qu'il y paraît.

1. Mauvaise distribution : Lorsqu'il est utilisé en conjonction avec des fonctions de hachage mal distribuées comme std : :hash, boost::hash_combine peut présenter un taux élevé de collisions.
2. Perte d'entropie : Si toute l'entropie est concentrée dans la graine, une partie de l'entropie peut être perdue dans le calcul.

Une meilleure alternative

Une fonction alternative de combinaison de hachage peut offrir à la fois une bonne distribution et une préservation de l'entropie :

template <class T>
inline size_t hash_combine(std::size_t& seed, const T& v)
{
    return rotl(seed, std::numeric_limits<size_t>::digits/3) ^ distribute(std::hash<T>{}(v));
}

Cette fonction utilise :

• Rotation des bits : Fait pivoter la graine pour rendre l'ordre de calcul de hachage pertinent.
• Bonne distribution : Utilise une fonction de distribution personnalisée pour une meilleure distribution de hachage.
• Préserve l'entropie : Fait pivoter la graine avant de la combiner pour éviter la perte d'entropie.

Considérations relatives aux performances

Bien que boost::hash_combine soit rapide, la fonction alternative sacrifie un peu de vitesse pour une qualité de hachage améliorée. Cependant, ce compromis en matière de vitesse est généralement négligeable pour la plupart des applications.

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!