Как HashSet сравнивает элементы на равенство?

Question

У меня есть класс IComparable:

public class a : IComparable
{
    public int Id { get; set; }
    public string Name { get; set; }

    public a(int id)
    {
        this.Id = id;
    }

    public int CompareTo(object obj)
    {
        return this.Id.CompareTo(((a)obj).Id);
    }
}

Когда я добавляю список объектов этого класса в хэш-набор:

a a1 = new a(1);
a a2 = new a(2);
HashSet<a> ha = new HashSet<a>();
ha.add(a1);
ha.add(a2);
ha.add(a1);

Все хорошо, а ha.count - это 2, но:

a a1 = new a(1);
a a2 = new a(2);
HashSet<a> ha = new HashSet<a>();
ha.add(a1);
ha.add(a2);
ha.add(new a(1));

Теперь ha.count - это 3.

1. Почему HashSet не уважает метод a CompareTo.
2. Является ли HashSet лучшим способом получить список уникальных объектов?

Answer 1

Используется IEqualityComparer<T> (EqualityComparer<T>.Default, если вы не укажете другой в строительстве).

Когда вы добавляете элемент в набор, он найдет хеш-код, используя IEqualityComparer<T>.GetHashCode, и сохранит как хеш-код, так и элемент (конечно, после проверки, есть ли элемент в наборе).

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

Это означает, что у вас есть два варианта:

• Передайте пользовательский IEqualityComparer<T> в конструктор. Это лучший вариант, если вы не можете изменить сам T или если вы хотите установить отношение равенства не по умолчанию (например, «все пользователи с отрицательным идентификатором пользователя считаются равными»). Это почти никогда не реализовано в самом типе (то есть Foo не реализует IEqualityComparer<Foo>), но в отдельном типе, который используется только для сравнения.
• Реализуйте равенство в самом типе, переопределяя GetHashCode и Equals(object). В идеале, следует также реализовать IEquatable<T> в типе, особенно если это тип значения. Эти методы будут вызываться компаратором равенства по умолчанию.

Обратите внимание, что все это не относится к упорядоченному сравнению - что имеет смысл, поскольку, безусловно, существуют ситуации, когда вы можете легко указать равенство, но не общее упорядочение. Это все то же самое, что и Dictionary<TKey, TValue>, в основном.

Если вам нужен набор, который использует порядок вместо простого сравнения на равенство, вы должны использовать SortedSet<T> из .NET 4 - что позволяет вам указать IComparer<T> вместо IEqualityComparer<T>. Это будет использовать IComparer<T>.Compare - который будет делегировать IComparable<T>.CompareTo или IComparable.CompareTo, если вы используете Comparer<T>.Default.

Answer 2

Вот пояснение к части ответа, которая осталась недосказанной: тип объекта вашего HashSet<T> не должен реализовывать IEqualityComparer<T>, а вместо этого просто должен переопределить Object.GetHashCode() и Object.Equals(Object obj).

Вместо этого:

public class a : IEqualityComparer<a>
{
  public int GetHashCode(a obj) { /* Implementation */ }
  public bool Equals(a obj1, a obj2) { /* Implementation */ }
}

Вы делаете это:

public class a
{
  public override int GetHashCode() { /* Implementation */ }
  public override bool Equals(object obj) { /* Implementation */ }
}

Это неуловимо, но это сбило меня с толку большую часть дня, пытаясь заставить HashSet функционировать так, как это было задумано. И, как уже говорили другие, HashSet<a> в конечном итоге вызовет a.GetHashCode() и a.Equals(obj) по мере необходимости при работе с множеством.

Answer 3

HashSet использует Equals и GetHashCode().

CompareTo для упорядоченных наборов.

Если вам нужны уникальные объекты, но вам нет дела до их итерациипорядок, HashSet<T>, как правило, лучший выбор.

Answer 4

Конструктор HashSet получает объект, который реализует IEqualityComparer для добавления нового объекта. если вы хотите использовать метод в HashSet, вы должны переопределить Equals, GetHashCode

namespace HashSet
{
    public class Employe
    {
        public Employe() {
        }

        public string Name { get; set; }

        public override string ToString()  {
            return Name;
        }

        public override bool Equals(object obj) {
            return this.Name.Equals(((Employe)obj).Name);
        }

        public override int GetHashCode() {
            return this.Name.GetHashCode();
        }
    }

    class EmployeComparer : IEqualityComparer<Employe>
    {
        public bool Equals(Employe x, Employe y)
        {
            return x.Name.Trim().ToLower().Equals(y.Name.Trim().ToLower());
        }

        public int GetHashCode(Employe obj)
        {
            return obj.Name.GetHashCode();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<Employe> hashSet = new HashSet<Employe>(new EmployeComparer());
            hashSet.Add(new Employe() { Name = "Nik" });
            hashSet.Add(new Employe() { Name = "Rob" });
            hashSet.Add(new Employe() { Name = "Joe" });
            Display(hashSet);
            hashSet.Add(new Employe() { Name = "Rob" });
            Display(hashSet);

            HashSet<Employe> hashSetB = new HashSet<Employe>(new EmployeComparer());
            hashSetB.Add(new Employe() { Name = "Max" });
            hashSetB.Add(new Employe() { Name = "Solomon" });
            hashSetB.Add(new Employe() { Name = "Werter" });
            hashSetB.Add(new Employe() { Name = "Rob" });
            Display(hashSetB);

            var union = hashSet.Union<Employe>(hashSetB).ToList();
            Display(union);
            var inter = hashSet.Intersect<Employe>(hashSetB).ToList();
            Display(inter);
            var except = hashSet.Except<Employe>(hashSetB).ToList();
            Display(except);

            Console.ReadKey();
        }

        static void Display(HashSet<Employe> hashSet)
        {
            if (hashSet.Count == 0)
            {
                Console.Write("Collection is Empty");
                return;
            }
            foreach (var item in hashSet)
            {
                Console.Write("{0}, ", item);
            }
            Console.Write("\n");
        }

        static void Display(List<Employe> list)
        {
            if (list.Count == 0)
            {
                Console.WriteLine("Collection is Empty");
                return;
            }
            foreach (var item in list)
            {
                Console.Write("{0}, ", item);
            }
            Console.Write("\n");
        }
    }
}