¿Cómo compara HashSet elementos para la igualdad?

127

Tengo una clase que es 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);
    }
}

Cuando agrego una lista de objetos de esta clase a un conjunto de hash:

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

Todo está bien y ha.countestá 2, pero:

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

Ahora ha.countes 3.

  1. ¿Por qué no HashSetrespeta ael CompareTométodo?
  2. ¿Es HashSetla mejor manera de tener una lista de objetos únicos?
nima
fuente
Agregue una implementación de IEqualityComparer<T>en el constructor o impleméntelo en la clase a. msdn.microsoft.com/en-us/library/bb301504(v=vs.110).aspx
Jaider

Respuestas:

137

Utiliza un IEqualityComparer<T>(a EqualityComparer<T>.Defaultmenos que especifique uno diferente en la construcción).

Cuando agrega un elemento al conjunto, encontrará el código hash usando IEqualityComparer<T>.GetHashCodey almacenará tanto el código hash como el elemento (después de verificar si el elemento ya está en el conjunto, por supuesto).

Para buscar un elemento, primero usará IEqualityComparer<T>.GetHashCodepara encontrar el código hash, luego, para todos los elementos con el mismo código hash, usará IEqualityComparer<T>.Equalspara comparar la igualdad real.

Eso significa que tienes dos opciones:

  • Pase una costumbre IEqualityComparer<T>al constructor. Esta es la mejor opción si no puede modificarse a Tsí mismo o si desea una relación de igualdad no predeterminada (por ejemplo, "todos los usuarios con una ID de usuario negativa se consideran iguales"). Esto casi nunca se implementa en el tipo en sí (es decir, Foono se implementa IEqualityComparer<Foo>), sino en un tipo separado que solo se usa para comparaciones.
  • Implemente la igualdad en el tipo mismo, anulando GetHashCodey Equals(object). Idealmente, implemente también IEquatable<T>en el tipo, particularmente si es un tipo de valor. El método de comparación de igualdad predeterminado llamará a estos métodos.

Tenga en cuenta que nada de esto es en términos de una comparación ordenada , lo que tiene sentido, ya que ciertamente hay situaciones en las que puede especificar fácilmente la igualdad, pero no una ordenación total. Todo esto es lo mismo que Dictionary<TKey, TValue>, básicamente.

Si desea un conjunto que use el ordenamiento en lugar de solo las comparaciones de igualdad, debe usarlo SortedSet<T>desde .NET 4, que le permite especificar un en IComparer<T>lugar de un IEqualityComparer<T>. Esto usará IComparer<T>.Compare, lo que delegará IComparable<T>.CompareToo IComparable.CompareTosi está usando Comparer<T>.Default.

Jon Skeet
fuente
77
+1 También tenga en cuenta la respuesta de @ tyriker (que la OMI debería ser un comentario aquí) que señala que la forma más sencilla de aprovechar dicho IEqualityComparer<T>.GetHashCode/Equals()es implementar Equalsy GetHashCodesobre Tsí mismo (y mientras lo hace, también implementaría la contraparte fuertemente tipada : - bool IEquatable<T>.Equals(T other))
Ruben Bartelink
55
Aunque es muy precisa, esta respuesta puede ser algo confusa, especialmente para los nuevos usuarios, ya que no establece claramente que para el caso más simple se anule Equalsy GetHashCodesea ​​suficiente, como se menciona en la respuesta de @ tyriker.
BartoszKP
Imo, una vez que implemente IComparable(o IComparerpara el caso) no se le debe pedir que implemente la igualdad por separado (sino solo GetHashCode). En cierto sentido, las interfaces de comparabilidad deben heredar de las interfaces de igualdad. Entiendo los beneficios de rendimiento al tener dos funciones separadas (donde puede optimizar la igualdad por separado simplemente diciendo si algo es igual o no) pero aún así. Muy confuso de lo contrario cuando ha especificado cuándo las instancias son iguales en CompareTofunción y marco no considerará ese.
nawfal
@nawfal no todo tiene un orden lógico. si está comparando dos cosas que contienen una propiedad bool, es simplemente horrible tener que escribir algo como a.boolProp == b.boolProp ? 1 : 0o debería ser a.boolProp == b.boolProp ? 0 : -1o a.boolProp == b.boolProp ? 1 : -1. Yuk!
Simon_Weaver 01 de
1
@Simon_Weaver lo es. Quiero evitarlo de alguna manera en mi característica hipotética que estaba proponiendo.
nawfal 01 de
77

Aquí hay una aclaración sobre una parte de la respuesta que no se ha dicho: el tipo de objeto de tu HashSet<T>no tiene que implementarse, IEqualityComparer<T>sino que solo debe anularse Object.GetHashCode()y Object.Equals(Object obj).

En lugar de esto:

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

Tu hiciste esto:

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

Es sutil, pero esto me hizo tropezar la mayor parte del día tratando de hacer que HashSet funcione de la manera prevista. Y como han dicho otros, HashSet<a>terminará llamando a.GetHashCode()y a.Equals(obj)según sea necesario cuando trabaje con el conjunto.

tyriker
fuente
2
Buen punto. Por cierto, como se menciona en mi comentario sobre la respuesta de @JonSkeet, también debe implementar bool IEquatable<T>.Equals(T other)para un ligero aumento de la eficiencia, pero lo más importante es el beneficio de la claridad. Por razones obvias, además de la necesidad de implementar GetHashCodejunto IEquatable<T>, el documento de IEquatable <T> menciona que, para fines de coherencia, también debe anular el object.Equalsde coherencia
Ruben Bartelink
Intenté implementar esto. Las ovveride getHashcodeobras, pero override bool equalsobtiene el error: ningún método encontraron a anulación. ¿alguna idea?
Stefanvds
Finalmente la información que estaba buscando. Gracias.
Mauro Sampietro
De mis comentarios sobre la respuesta anterior: en su caso "En lugar de", podría tener public class a : IEqualityComparer<a> {, y luego new HashSet<a>(a).
HankCa
Pero vea los comentarios de Jon Skeets arriba.
HankCa
9

HashSetusos Equalsy GetHashCode().

CompareTo es para conjuntos ordenados.

Si desea objetos únicos, pero no le importa su orden de iteración, HashSet<T>suele ser la mejor opción.

CodesInChaos
fuente
5

El constructor HashSet recibe el objeto que implementa IEqualityComparer para agregar un nuevo objeto. si desea utilizar el método en HashSet, debe anular 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");
        }
    }
}
Nikolai Nechai
fuente
¿Qué pasa si el nombre es nulo? ¿Cuál es el valor hash de nulo?
Joe