Bien que le modèle décrit dans la réponse de Jon Skeet fonctionne bien en général en tant que famille de fonctions de hachage, le choix des constantes est important et la graine de 17
et le facteur de 31
comme indiqué dans la réponse, ne fonctionnent pas bien du tout pour les cas d'utilisation courants. Dans la plupart des cas d'utilisation, les valeurs hachées sont beaucoup plus proches de zéro que des valeurs de int.MaxValue
et le nombre d'éléments soumis à un hachage commun est inférieur ou égal à quelques dizaines.
Pour le hachage d'un tuple entier {x, y}
donde -1000 <= x <= 1000
y -1000 <= y <= 1000
Il a un taux de collision abyssal de près de 98,5 %. A titre d'exemple, {1, 0} -> {0, 31}
, {1, 1} -> {0, 32}
, etc. Si nous étendons la couverture pour inclure également les n-tuples où 3 <= n <= 25
En revanche, il est moins mauvais avec un taux de collision d'environ 38%. Mais nous pouvons faire beaucoup mieux.
public static int CustomHash(int seed, int factor, params int[] vals)
{
int hash = seed;
foreach (int i in vals)
{
hash = (hash * factor) + i;
}
return hash;
}
J'ai écrit une boucle de recherche par échantillonnage de Monte Carlo qui a testé la méthode ci-dessus avec diverses valeurs pour la graine et le facteur sur divers n-tuples aléatoires d'entiers aléatoires. i
. Les plages autorisées sont les suivantes 2 <= n <= 25
(où n
était aléatoire mais biaisée vers le bas de la fourchette) et les -1000 <= i <= 1000
. Au moins 12 millions de tests de collision uniques ont été effectués pour chaque paire de semences et de facteurs.
Après environ 7 heures de fonctionnement, la meilleure paire trouvée (où la graine et le facteur étaient tous deux limités à 4 chiffres ou moins) était : seed = 1009
, factor = 9176
avec un taux de collision de 0,1131%. Dans les zones à 5 et 6 chiffres, il existe des options encore meilleures. Mais par souci de concision, j'ai sélectionné la meilleure option à 4 chiffres, qui fonctionne très bien dans tous les cas courants. int
y char
scénarios de hachage. Il semble également fonctionner correctement avec des nombres entiers beaucoup plus importants.
Il convient de noter que le fait d'être "premier" ne semble pas être une condition préalable générale pour obtenir de bons résultats en tant que semence et/ou facteur, bien que cela soit probablement utile. 1009
mentionné ci-dessus est en fait premier, mais 9176
ne l'est pas. J'ai explicitement testé des variantes de ce principe en modifiant factor
à divers nombres premiers proches de 9176
(tout en laissant seed = 1009
) et elles sont toutes moins performantes que la solution ci-dessus.
Enfin, j'ai également effectué une comparaison avec la famille générique de fonctions de recommandation de ReSharper, à savoir hash = (hash * factor) ^ i;
et l'original CustomHash()
comme indiqué ci-dessus, le surpasse largement. Le style XOR de ReSharper semble avoir des taux de collision de l'ordre de 20 à 30 % pour les hypothèses de cas d'utilisation courants et ne devrait pas être utilisé à mon avis.