.net - 将委托(delegate)包装在 IEqualityComparer 中

Question

多个 Linq.Enumerable 函数采用 IEqualityComparer<T> 。是否有一个方便的包装类来适应 delegate(T,T)=>bool实现IEqualityComparer<T> ？编写一个很容易(如果您忽略定义正确的哈希码的问题)，但我想知道是否有开箱即用的解决方案。

具体来说，我想对 Dictionary 进行集合操作s，仅使用 Key 来定义成员资格(同时根据不同的规则保留值)。

Answer 1

论GetHashCode的重要性

其他人已经评论过任何自定义 IEqualityComparer<T>实现应该真正包括 GetHashCode方法；但没有人愿意详细解释原因。

原因如下。您的问题特别提到了 LINQ 扩展方法；几乎所有这些都依赖哈希码才能正常工作，因为它们在内部利用哈希表来提高效率。

拿 Distinct ， 例如。考虑一下这个扩展方法的含义，如果它使用的只是 Equals方法。如果您只有 Equals，如何确定某个项目是否已按顺序扫描过？您枚举您已经查看过的整个值集合并检查是否匹配。这将导致 Distinct使用最坏情况的 O(N²) 算法而不是 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>来自 Aku's answer 的类(class):

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

Hmm, that didn't work, did it?

What about GroupBy? Let's try that:

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

Again: didn't work.

If you think about it, it would make sense for Distinct to use a HashSet<T> (or equivalent) internally, and for GroupBy to use something like a Dictionary<TKey, List<T>> internally. Could this explain why these methods don't work? Let's try this:

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

Yeah... starting to make sense?

Hopefully from these examples it's clear why including an appropriate GetHashCode in any IEqualityComparer<T> implementation is so important.

---

Original answer

Expanding on orip's answer:

There are a couple of improvements that can be made here.

1. First, I'd take a Func<T, TKey> instead of Func<T, object>; this will prevent boxing of value type keys in the actual keyExtractor itself.
2. Second, I'd actually add a where TKey : IEquatable<TKey> constraint; this will prevent boxing in the Equals call (object.Equals takes an object parameter; you need an IEquatable<TKey> implementation to take a TKey parameter without boxing it). Clearly this may pose too severe a restriction, so you could make a base class without the constraint and a derived class with it.

Here's what the resulting code might look like:

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