Как использовать IEqualityComparer <T>.Equals () в расширении ToLookUp <T>() - PullRequest
Новая
       54

Как использовать IEqualityComparer <T>.Equals () в расширении ToLookUp <T>()

1 голос
/ 05 августа 2011

Я наткнулся на статью , касающуюся Парадокса Дня Рождения и его последствий при переопределении метода GetHashCode, я попал в тупик.

В тестахМы обнаружили, что в вызовах к ToLookup() Extension используется только GetHashcode, несмотря на предоставление реализации для Equals.

Мне кажется, я понимаю , почему это происходит, внутренняя работа ToLookup, HashSet, Dictionary и т. Д. Использует HashCodes для хранения и / или индексации своих элементов?

Есть ли способ как-то обеспечить функциональность, чтобы сравнение на равенство выполнялось с использованием метода equals?Или я не должен быть обеспокоен столкновениями?Я сам не занимался математикой, но согласно первой статье, на которую я ссылался, вам нужно всего лишь 77 163 элемента в списке, прежде чем можно будет столкнуться с вероятностью 50%.

Если я правильно понимаю, Equals() Переопределение, которое сравнивает свойство по свойству, например 

Return (a.Property1 == b.Property1 && a.Property2 == b.Property2 && ...)

, должно иметь нулевую вероятность столкновения?Итак, как я могу получить мои ToLookup() для равенства сравнивать таким образом?

Если вам нужен пример того, что я имею в виду:

C # 

class Program
{

    static void Main(string[] args)
    {
        DoStuff();
        Console.ReadKey();
    }

    public class AnEntity
    {
        public int KeyProperty1 { get; set; }
        public int KeyProperty2 { get; set; }
        public int KeyProperty3 { get; set; }
        public string OtherProperty1 { get; set; }
        public List<string> OtherProperty2 { get; set; }
    }

    public class KeyEntity
    {
        public int KeyProperty1 { get; set; }
        public int KeyProperty2 { get; set; }
        public int KeyProperty3 { get; set; }
    }

    public static void DoStuff()
    {
        var a = new AnEntity {KeyProperty1 = 1, KeyProperty2 = 2, KeyProperty3 = 3, OtherProperty1 = "foo"};
        var b = new AnEntity {KeyProperty1 = 1, KeyProperty2 = 2, KeyProperty3 = 3, OtherProperty1 = "bar"};
        var c = new AnEntity {KeyProperty1 = 999, KeyProperty2 = 999, KeyProperty3 = 999, OtherProperty1 = "yada"};

        var entityList = new List<AnEntity> { a, b, c };

        var lookup = entityList.ToLookup(n => new KeyEntity {KeyProperty1 = n.KeyProperty1, KeyProperty2 = n.KeyProperty2, KeyProperty3 = n.KeyProperty3});

        // I want these to all return true
        Debug.Assert(lookup.Count == 2);
        Debug.Assert(lookup[new KeyEntity {KeyProperty1 = 1, KeyProperty2 = 2, KeyProperty3 = 3}].First().OtherProperty1 == "foo");
        Debug.Assert(lookup[new KeyEntity {KeyProperty1 = 1, KeyProperty2 = 2, KeyProperty3 = 3}].Last().OtherProperty1 == "bar");
        Debug.Assert(lookup[new KeyEntity {KeyProperty1 = 999, KeyProperty2 = 999, KeyProperty3 = 999}].Single().OtherProperty1 == "yada");
    }

}

VB 

Module Program

    Public Sub Main(args As String())
        DoStuff()
        Console.ReadKey()
    End Sub

    Public Class AnEntity
        Public Property KeyProperty1 As Integer
        Public Property KeyProperty2 As Integer
        Public Property KeyProperty3 As Integer
        Public Property OtherProperty1 As String
        Public Property OtherProperty2 As List(Of String) 
    End Class

    Public Class KeyEntity
        Public Property KeyProperty1 As Integer
        Public Property KeyProperty2 As Integer
        Public Property KeyProperty3 As Integer
    End Class

    Public Sub DoStuff()
        Dim a = New AnEntity With {.KeyProperty1 = 1, .KeyProperty2 = 2, .KeyProperty3 = 3, .OtherProperty1 = "foo"}
        Dim b = New AnEntity With {.KeyProperty1 = 1, .KeyProperty2 = 2, .KeyProperty3 = 3, .OtherProperty1 = "bar"}
        Dim c = New AnEntity With {.KeyProperty1 = 999, .KeyProperty2 = 999, .KeyProperty3 = 999, .OtherProperty1 = "yada"}

        Dim entityList = New List(Of AnEntity) From {a, b, c}

        Dim lookup = entityList.ToLookup(Function(n) New KeyEntity With {.KeyProperty1 = n.KeyProperty1, .KeyProperty2 = n.KeyProperty2, .KeyProperty3 = n.KeyProperty3})

        ' I want these to all return true
        Debug.Assert(lookup.Count = 2)
        Debug.Assert(lookup(New KeyEntity With {.KeyProperty1 = 1, .KeyProperty2 = 2, .KeyProperty3 = 3}).First().OtherProperty1 = "foo")
        Debug.Assert(lookup(New KeyEntity With {.KeyProperty1 = 1, .KeyProperty2 = 2, .KeyProperty3 = 3}).Last().OtherProperty1 = "bar")
        Debug.Assert(lookup(New KeyEntity With {.KeyProperty1 = 999, .KeyProperty2 = 999, .KeyProperty3 = 999}).Single().OtherProperty1 = "yada")
    End Sub

End Module

Я могу заставить это работать с переопределением GetHashcode(), никаких проблем.Но я не хочу использовать GetHashcode, потому что, если у меня есть, например, 109 125 элементов в моем списке, вероятно, у меня уже есть 75% шанс столкновения?Если бы он использовал вышеупомянутое Equals() переопределение, я думаю, я был бы на 0%?

Ответы [ 2 ]

2 голосов
/ 05 августа 2011

Статья, на которую вы ссылаетесь, полностью вводит в заблуждение (и многие из ее комментариев подчеркивают это).

GetHashCode используется там, где это возможно, потому что это быстро; если есть коллизии хешей, то Equals используется для устранения неоднозначности между сталкивающимися элементами. Если вы правильно реализуете Equals и GetHashCode - будь то в самих типах или в пользовательской реализации IEqualityComparer<T> - тогда проблем не будет.

Проблема с вашим примером кода состоит в том, что вы вообще не переопределяете Equals и GetHashCode. Это означает, что используются реализации по умолчанию, а реализации по умолчанию используют сравнения ссылок для ссылочных типов, а не сравнения значений.

Это означает, что вы не получаете хеш-коллизий, потому что объекты, с которыми вы сравниваете , отличаются от исходных объектов , даже если они имеют одинаковые значения. Это, в свою очередь, означает, что Equals просто не требуется вашим примером кода. Правильно переопределите Equals и GetHashCode или установите для этого IEqualityComparer<T>, и все начнет работать так, как вы ожидаете.

1 голос
/ 05 августа 2011

Парадокс дня рождения не применим в этой ситуации. Парадокс дня рождения относится к недетерминированным случайным множествам, тогда как вычисление хеш-кода является детерминированным. вероятность того, что 2 объекта с различным состоянием совместно используют один и тот же хэш-код, намного ближе к 1 на миллиард или около того, определенно не ниже 77 тысяч - поэтому я не думаю, что вам есть о чем беспокоиться.

...