о важности GetHashCode
Другие уже прокомментировали тот факт, что любая пользовательская IEqualityComparer<T> реализация должна действительно включать GetHashCode метод ; но никто не удосужился объяснить почему в деталях.
Вот почему. В вашем вопросе конкретно упоминаются методы расширения LINQ; почти все из них полагаются на хэш-коды для правильной работы, потому что они используют хеш-таблицы для эффективности.
Взять, например, Distinct. Рассмотрим последствия этого метода расширения, если все, что он использовал, был Equals метод. Как вы определяете, был ли элемент уже отсканирован в последовательности, если у вас есть только Equals? Вы перечисляете всю совокупность значений, которые вы уже просматривали, и проверяете соответствие. В результате Distinct будет использовать алгоритм O (N 2 ) в худшем случае вместо алгоритма O (N)!
К счастью, это не так. Distinct не просто использовать Equals; он также использует GetHashCode. Фактически, это абсолютно не работает должным образом без IEqualityComparer<T>, который поставляет правильные GetHashCode. Ниже приведен надуманный пример, иллюстрирующий это.
Скажем, у меня есть следующий тип:
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);
}
}
Теперь скажите, что у меня есть List<Value>, и я хочу найти все элементы с разными именами. Это идеальный вариант использования Distinct с использованием пользовательского компаратора равенства. Итак, давайте воспользуемся Comparer<T> классом из ответа Аку :
var comparer = new Comparer<Value>((x, y) => x.Name == y.Name);
Теперь, если у нас есть набор Value элементов с одинаковым свойством Name, все они должны свернуться в одно значение, возвращаемое Distinct, верно? Посмотрим ...
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);
}
Выход:
x: 1346013431
x: 1388845717
x: 1576754134
x: 1104067189
x: 1144789201
x: 1862076501
x: 1573781440
x: 646797592
x: 655632802
x: 1206819377
Хм, это не сработало, не так ли?
А как насчет GroupBy? Давайте попробуем это:
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);
}
}
Выход:
[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
Опять же: не работает.
Если подумать, для Distinct имеет смысл использовать HashSet<T> (или его эквивалент) внутри, а для GroupBy использовать что-то вроде Dictionary<TKey, List<T>> для внутреннего использования. Может ли это объяснить, почему эти методы не работают? Давайте попробуем это:
var uniqueValues = new HashSet<Value>(values, comparer);
foreach (Value x in uniqueValues)
{
Console.WriteLine(x);
}
Выход:
x: 1346013431
x: 1388845717
x: 1576754134
x: 1104067189
x: 1144789201
x: 1862076501
x: 1573781440
x: 646797592
x: 655632802
x: 1206819377
Да ... начинает иметь смысл?
Надеюсь, из этих примеров понятно, почему включение GetHashCode в любую реализацию IEqualityComparer<T> так важно.
Оригинальный ответ
Расширение orip's answer :
Здесь можно сделать несколько улучшений.
- Во-первых, я бы взял
Func<T, TKey> вместо Func<T, object>; это предотвратит упаковку ключей типа значения в сам фактический keyExtractor.
- Во-вторых, я бы на самом деле добавил ограничение
where TKey : IEquatable<TKey>; это предотвратит упаковку в вызове Equals (object.Equals принимает параметр object; вам нужна реализация IEquatable<TKey> для получения параметра TKey без его упаковки). Очевидно, что это может накладывать слишком жесткие ограничения, поэтому вы можете создать базовый класс без ограничения и производный класс с ним.
Вот как может выглядеть полученный код:
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));
}
}