Il existe différentes approches de la ici la en deux catégories principales, chacune avec généralement leurs propres avantages et inconvénients, en termes d'efficacité et de performance. Il est probablement préférable de choisir la plus simple de l'algorithme pour quelle application et d'utiliser uniquement la plus complexe des variantes, si nécessaire, quelle que soit la situation.
Notez que ces exemples utilisent EqualityComparer<T>.Default depuis qui traitera des éléments null proprement. Vous pourriez faire mieux que zéro pour la valeur null si désiré. Si T est contraint de struct il est également inutile. Vous pouvez hisser EqualityComparer<T>.Default de recherche de la fonction si vous le souhaitez.
Commutative Opérations
Si vous utiliser des opérations sur les hashcodes des entrées individuelles qui sont commutative alors cela conduira au même résultat quel que soit l'ordre.
Il y a plusieurs évident options sur les nombres:
XOR
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
foreach (T element in source)
{
hash = hash ^ EqualityComparer<T>.Default.GetHashCode(element);
}
return hash;
}
Un inconvénient de cette est que le hachage { "x", "x" } est le même que le hachage { "y", "y" }. Si ce n'est pas un problème pour votre situation de bien, c'est probablement la solution la plus simple.
Plus
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
foreach (T element in source)
{
hash = unchecked (hash +
EqualityComparer<T>.Default.GetHashCode(element));
}
return hash;
}
Le dépassement est très bien ici, d'où l'explicite unchecked contexte.
Il y a encore quelques méchants cas (par exemple, {1, -1} et {2, -2}, mais il est plus susceptible d'être d'accord, en particulier avec des chaînes. Dans le cas de listes susceptibles de contenir de tels entiers, vous pouvez toujours mettre en œuvre une coutume fonction de hachage (peut-être un qui prend l'indice de la récidive de la valeur en paramètre et retourne un unique code de hachage en conséquence).
Voici un exemple d'un tel algorithme qui permet de contourner le problème susmentionné d'une manière très efficace. Il a également l'avantage d'augmenter fortement la distribution des codes de hachage généré (voir l'article lié à la fin de l'explication). Mathématique/statistique de l'analyse de exactement comment cet algorithme produit "au mieux" des codes de hachage serait assez avancé, mais de le tester sur une large gamme de valeurs d'entrée et de tracer les résultats devraient vérifier assez bien.
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
int curHash;
int bitOffset = 0;
// Stores number of occurences so far of each value.
var valueCounts = new Dictionary<T, int>();
foreach (T element in source)
{
curHash = EqualityComparer<T>.Default.GetHashCode(element);
if (valueCounts.TryGetValue(element, out bitOffset))
valueCounts[element] = bitOffset + 1;
else
valueCounts.Add(element, bitOffset);
// The current hash code is shifted (with wrapping) one bit
// further left on each successive recurrence of a certain
// value to widen the distribution.
// 37 is an arbitrary low prime number that helps the
// algorithm to smooth out the distribution.
hash = unchecked(hash + ((curHash << bitOffset) |
(curHash >> (32 - bitOffset))) * 37);
}
return hash;
}
La Multiplication
Qui a peu d'avantages sur l'addition: un petit nombre et un mélange de nombres positifs et négatifs, ils peuvent conduire à une meilleure distribution de hachage bits. Comme un point négatif pour compenser ce "1" devient inutile entrée en contribuant rien et tout zéro de l'élément de résultats par un zéro.
Vous pouvez le cas à zéro non pour provoquer ce défaut majeur.
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 17;
foreach (T element in source)
{
int h = EqualityComparer<T>.Default.GetHashCode(element);
if (h != 0)
hash = unchecked (hash * h);
}
return hash;
}
D'abord
L'autre approche de base est d'appliquer certains de commande d'abord, puis utilisez l'une de hachage la fonction de combinaison vous le souhaitez. La commande elle-même est sans importance tant que c'est cohérent.
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
foreach (T element in source.OrderBy(x => x, Comparer<T>.Default))
{
// f is any function/code you like returning int
hash = f(hash, element);
}
return hash;
}
Cela a des avantages importants en ce que la combinaison des opérations possibles en f peut avoir nettement mieux de hachage (propriétés de la distribution de bits par exemple) mais cela se fait au coût nettement plus élevé. Le tri est O(n log n) et la copie de la collection est une allocation de mémoire que vous ne pouvez pas éviter que le désir d'éviter de modifier l'original. GetHashCode des implémentations devraient normalement éviter les allocations entièrement. Une implémentation possible de l' f serait similaire à celui donné dans le dernier exemple, en vertu de la section (par exemple, un nombre constant de bits quarts à gauche, puis par une multiplication par un premier - vous pouvez même utiliser des nombres premiers successifs à chaque itération, sans frais supplémentaires, ceux-ci doivent uniquement être généré à la fois).
Cela dit, si nous avions affaire à des cas où l'on pouvait calculer et de mettre en cache les valeurs de hachage et d'amortir le coût sur de nombreux appels d' GetHashCode cette approche peut donner supérieure de comportement. Aussi cette dernière approche est d'autant plus flexible car il permet d'éviter la nécessité d'utiliser l' GetHashCode sur les éléments si il sait leur type et au lieu d'utiliser par octet d'opérations pour un rendement encore meilleur de hachage de la distribution. Une telle approche serait probablement de l'utiliser uniquement dans le cas où la performance a été identifié comme étant un goulot d'étranglement important.
Enfin, si vous voulez une assez complet et plutôt non-mathématique aperçu des codes de hachage et de leur efficacité en général, ces messages de blog serait utile de lit, en particulier la mise en Œuvre d'un simple algorithme de hachage (pt II) de la poste.
