Sur l'importance de l' GetHashCode
D'autres ont déjà commenté sur le fait que de coutume IEqualityComparer<T> mise en œuvre devrait vraiment inclure un GetHashCode méthode; mais personne n'est donné la peine d'expliquer pourquoi dans le détail.
Voici pourquoi. Votre question mentionne expressément l'extension LINQ méthodes; presque tous les elles reposent sur des codes de hachage pour fonctionner correctement, parce qu'ils utilisent des tables de hachage interne pour plus d'efficacité.
Prendre en Distinct, par exemple. Considérer les conséquences de cette méthode d'extension si tout c'utilisés ont été un Equals méthode. Comment déterminez-vous si un élément a déjà été analysés dans une séquence si vous n'avez qu' Equals? Vous énumérer sur l'ensemble de la collection de valeurs que vous avez déjà regardé et vérifier pour un match. Cela aurait pour conséquence Distinct à l'aide d'un pire cas O(N2) algorithme au lieu de O(N)!
Heureusement, ce n'est pas le cas. Distinct n'est pas juste utiliser Equals; il utilise GetHashCode . En fait, c'est absolument ne pas fonctionner correctement sans un IEqualityComparer<T> qui fournit un bon GetHashCode. Ci-dessous est un exemple artificiel pour illustrer cela.
Dire que j'ai du type suivant:
class Value
{
public string Name { get; private set; }
public int Number { get; private set; }
public Value(string name, int number)
{
Name = name;
Number = number;
}
public override string ToString()
{
return string.Format("{0}: {1}", Name, Number);
}
}
Maintenant dire que j'ai un List<Value> et je veux trouver tous les éléments avec un nom distinct. C'est un parfait cas d'utilisation de Distinct l'aide personnalisée comparateur d'égalité. Nous allons donc utiliser l' Comparer<T> classe de Aku réponse:
var comparer = new Comparer<Value>((x, y) => x.Name == y.Name);
Maintenant, si nous avons un tas d' Value éléments avec le même Name de la propriété, ils doivent tous s'effondrer en une seule valeur retournée par Distinct, droite? Voyons voir...
var values = new List<Value>();
var random = new Random();
for (int i = 0; i < 10; ++i)
{
values.Add("x", random.Next());
}
var distinct = values.Distinct(comparer);
foreach (Value x in distinct)
{
Console.WriteLine(x);
}
Sortie:
x: 1346013431
x: 1388845717
x: 1576754134
x: 1104067189
x: 1144789201
x: 1862076501
x: 1573781440
x: 646797592
x: 655632802
x: 1206819377
Hmm, ça ne marche pas, il l'a fait?
Qu'en GroupBy? Essayons:
var grouped = values.GroupBy(x => x, comparer);
foreach (IGrouping<Value> g in grouped)
{
Console.WriteLine("[KEY: '{0}']", g);
foreach (Value x in g)
{
Console.WriteLine(x);
}
}
Sortie:
[KEY = 'x: 1346013431']
x: 1346013431
[KEY = 'x: 1388845717']
x: 1388845717
[KEY = 'x: 1576754134']
x: 1576754134
[KEY = 'x: 1104067189']
x: 1104067189
[KEY = 'x: 1144789201']
x: 1144789201
[KEY = 'x: 1862076501']
x: 1862076501
[KEY = 'x: 1573781440']
x: 1573781440
[KEY = 'x: 646797592']
x: 646797592
[KEY = 'x: 655632802']
x: 655632802
[KEY = 'x: 1206819377']
x: 1206819377
Encore une fois: n'a pas fonctionné.
Si vous pensez à ce sujet, il serait judicieux Distinct à utiliser un HashSet<T> (ou l'équivalent) en interne, et pour GroupBy à utiliser quelque chose comme un Dictionary<TKey, List<T>> en interne. Cela pourrait-il expliquer pourquoi ces méthodes ne fonctionnent pas? Essayons ceci:
var uniqueValues = new HashSet<Value>(values, comparer);
foreach (Value x in uniqueValues)
{
Console.WriteLine(x);
}
Sortie:
x: 1346013431
x: 1388845717
x: 1576754134
x: 1104067189
x: 1144789201
x: 1862076501
x: 1573781440
x: 646797592
x: 655632802
x: 1206819377
Ouais... en commençant à donner un sens?
Espérons-le, à partir de ces exemples, il est clair pourquoi l' GetHashCode dans tout IEqualityComparer<T> mise en œuvre est si important.
Réponse originale à cette question
L'expansion sur orip réponse:
Il y a quelques améliorations qui peuvent être faites ici.
- Tout d'abord, je voudrais prendre un
Func<T, TKey> au lieu de Func<T, object>; cela permettra d'éviter de boxe de type de la valeur des clés dans le réel keyExtractor lui-même.
- Deuxièmement, je voudrais ajouter un
where TKey : IEquatable<TKey> la contrainte; cela permettra d'éviter la boxe dans l' Equals appel (object.Equals prend un object paramètre; vous avez besoin d'un IEquatable<TKey> de la mise en œuvre de prendre un TKey paramètre sans la boxe). Manifestement, cela peut poser trop de gravité de la restriction, de sorte que vous pourrait faire une classe de base sans la contrainte et une classe dérivée.
Voici ce que le code résultant peut ressembler à:
public class KeyEqualityComparer<T, TKey> : IEqualityComparer<T>
{
protected readonly Func<T, TKey> keyExtractor;
public KeyEqualityComparer(Func<T, TKey> keyExtractor)
{
this.keyExtractor = keyExtractor;
}
public virtual bool Equals(T x, T y)
{
return this.keyExtractor(x).Equals(this.keyExtractor(y));
}
public int GetHashCode(T obj)
{
return this.keyExtractor(obj).GetHashCode();
}
}
public class StrictKeyEqualityComparer<T, TKey> : KeyEqualityComparer<T, TKey>
where TKey : IEquatable<TKey>
{
public StrictKeyEqualityComparer(Func<T, TKey> keyExtractor)
: base(keyExtractor)
{ }
public override bool Equals(T x, T y)
{
// This will use the overload that accepts a TKey parameter
// instead of an object parameter.
return this.keyExtractor(x).Equals(this.keyExtractor(y));
}
}
