Boost::hash_combine est-il la solution idéale pour combiner des valeurs de hachage ?

Plonger dans Boost::hash_combine : combiner efficacement les valeurs de hachage

La fonction boost::hash_combine a été saluée comme une méthode efficace pour combiner des valeurs de hachage. Cependant, sa supériorité va au-delà de la simple vitesse ; il permet également un mélange et une préservation améliorés de l'entropie.

Implémentation et nombre magique

La fonction, telle que présentée dans l'extrait de code ci-dessous, utilise une combinaison d'une fonction de hachage interne, xor-shifts , et un nombre magique (0x9e3779b9) :

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);
}

Problèmes avec l'implémentation originale

Malgré son utilisation généralisée, l'implémentation originale de boost::hash_combine n'était pas optimale en termes de distribution. Lorsqu'il est utilisé en conjonction avec une fonction de hachage mal distribuée comme std::hash, cela peut entraîner un nombre élevé de collisions.

Un algorithme modifié pour un mixage amélioré

Alors que le boost révisé : hash_combine dans la version 1.81 a résolu ces problèmes de distribution, explorons une approche alternative qui offre un mélange exceptionnel 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));
}

Cet algorithme modifié utilise plusieurs xor-shifts et une opération de rotation pour obtenir un mélange supérieur, ce qui entraîne un hachage plus uniformément réparti.

Conclusion

Bien que boost::hash_combine reste une option rapide, l'algorithme alternatif révisé offre un mélange amélioré et une préservation de l'entropie en implémentant plusieurs xor-shifts et opérations de rotation. Pour les applications nécessitant un hachage étendu, le nombre réduit de collisions et la distribution améliorée en font un choix plus fiable.

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!