의 중요성에 GetHashCode

다른 사용자들은 이미 모든 사용자 정의 IEqualityComparer<T>구현 이 실제로 GetHashCode메소드를 포함해야 한다는 사실에 대해 언급했습니다 . 그러나 아무도 왜 상세하게 설명 할 필요가 없습니다.

이유는 다음과 같습니다. 귀하의 질문은 특히 LINQ 확장 방법을 언급합니다. 거의 모든 이들은 효율성을 위해 내부적으로 해시 테이블을 사용하기 때문에, 제대로 작동하려면 해시 코드에 의존하고 있습니다.

가지고 Distinct예를 들어. 이 확장 방법이 사용 된 Equals방법 중 하나라면이 확장 방법의 의미를 고려하십시오 . 가지고있는 항목이 이미 순서대로 스캔되었는지 어떻게 알 수 Equals있습니까? 이미 살펴본 전체 값 모음을 열거하고 일치하는지 확인합니다. 이것은 DistinctO (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커스텀 평등 비교기 를 사용하기 위한 완벽한 유스 케이스입니다 . Aku의 답변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의 답변 확대 :

여기에는 몇 가지 개선 사항이 있습니다.

1. 먼저, Func<T, TKey>대신에 Func<T, object>; 이렇게하면 실제 keyExtractor자체 에 값 유형 키가 박싱되지 않습니다.
2. 둘째, 실제로 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));
    }
}

답변

var foo = new List<string> { "abc", "de", "DE" };

// case-insensitive distinct
var distinct = foo.Distinct(new KeyEqualityComparer<string>( x => x.ToLower() ) );

public class KeyEqualityComparer<T> : IEqualityComparer<T>
{
    private readonly Func<T, object> keyExtractor;

    public KeyEqualityComparer(Func<T,object> keyExtractor)
    {
        this.keyExtractor = keyExtractor;
    }

    public bool Equals(T x, T y)
    {
        return this.keyExtractor(x).Equals(this.keyExtractor(y));
    }

    public int GetHashCode(T obj)
    {
        return this.keyExtractor(obj).GetHashCode();
    }
}

class Comparer<T>: IEqualityComparer<T>
{
    private readonly Func<T, T, bool> _comparer;

    public Comparer(Func<T, T, bool> comparer)
    {
        if (comparer == null)
            throw new ArgumentNullException("comparer");

        _comparer = comparer;
    }

    public bool Equals(T x, T y)
    {
        return _comparer(x, y);
    }

    public int GetHashCode(T obj)
    {
        return obj.ToString().ToLower().GetHashCode();
    }
}

...

Func<int, int, bool> f = (x, y) => x == y;
var comparer = new Comparer<int>(f);
Console.WriteLine(comparer.Equals(1, 1));
Console.WriteLine(comparer.Equals(1, 2));

public static class Equality<T>
{
    public static IEqualityComparer<T> CreateComparer<V>(Func<T, V> keySelector)
    {
        return CreateComparer(keySelector, null);
    }

    public static IEqualityComparer<T> CreateComparer<V>(Func<T, V> keySelector,
                                                         IEqualityComparer<V> comparer)
    {
        return new KeyEqualityComparer<V>(keySelector, comparer);
    }

    class KeyEqualityComparer<V> : IEqualityComparer<T>
    {
        readonly Func<T, V> keySelector;
        readonly IEqualityComparer<V> comparer;

        public KeyEqualityComparer(Func<T, V> keySelector,
                                   IEqualityComparer<V> comparer)
        {
            if (keySelector == null)
                throw new ArgumentNullException("keySelector");

            this.keySelector = keySelector;
            this.comparer = comparer ?? EqualityComparer<V>.Default;
        }

        public bool Equals(T x, T y)
        {
            return comparer.Equals(keySelector(x), keySelector(y));
        }

        public int GetHashCode(T obj)
        {
            return comparer.GetHashCode(keySelector(obj));
        }
    }
}

var comparer1 = Equality<Person>.CreateComparer(p => p.ID);
var comparer2 = Equality<Person>.CreateComparer(p => p.Name);
var comparer3 = Equality<Person>.CreateComparer(p => p.Birthday.Year);
var comparer4 = Equality<Person>.CreateComparer(p => p.Name, StringComparer.CurrentCultureIgnoreCase);

class Person
{
    public int ID { get; set; }
    public string Name { get; set; }
    public DateTime Birthday { get; set; }
}

public class FuncEqualityComparer<T> : IEqualityComparer<T>
{
    readonly Func<T, T, bool> _comparer;
    readonly Func<T, int> _hash;

    public FuncEqualityComparer( Func<T, T, bool> comparer )
        : this( comparer, t => t.GetHashCode())
    {
    }

    public FuncEqualityComparer( Func<T, T, bool> comparer, Func<T, int> hash )
    {
        _comparer = comparer;
        _hash = hash;
    }

    public bool Equals( T x, T y )
    {
        return _comparer( x, y );
    }

    public int GetHashCode( T obj )
    {
        return _hash( obj );
    }
}

public static class SequenceExtensions
{
    public static bool SequenceEqual<T>( this IEnumerable<T> first, IEnumerable<T> second, Func<T, T, bool> comparer )
    {
        return first.SequenceEqual( second, new FuncEqualityComparer<T>( comparer ) );
    }

    public static bool SequenceEqual<T>( this IEnumerable<T> first, IEnumerable<T> second, Func<T, T, bool> comparer, Func<T, int> hash )
    {
        return first.SequenceEqual( second, new FuncEqualityComparer<T>( comparer, hash ) );
    }
}

public static IEnumerable<T> Distinct<T>(this IEnumerable<T> list, Func<T, object>    keyExtractor)
{
    return list.Distinct(new KeyEqualityComparer<T>(keyExtractor));
}
var distinct = foo.Distinct(x => x.ToLower())