lunes, 8 de septiembre de 2008

Hashtables, diccionarios e igualdad en las colecciones.

Hashtables, diccionarios e igualdad en las colecciones

Existen algunas colecciones que se utilizan para trabajar con elementos que vamos considerar diferentes a partir de alguna característica que los identifica, que los hace únicos, se llaman diccionarios, y justamente la interface IDictionary es la que nos permite implementar este tipo de funcionalidad, veamos un poco cómo es:

public interface IDictionary : ICollection, IEnumerable
{
    // Methods
    void Add(object key, object value);
    void Clear();
    bool Contains(object key);
    IDictionaryEnumerator GetEnumerator();
    void Remove(object key);

    // Properties
    bool IsFixedSize { get; }
    bool IsReadOnly { get; }
    object this[object key] { get; set; }
    ICollection Keys { get; }
    ICollection Values { get; }
}

El método Add nos permite agregar un elemento indicando dos cosas, "key" la clave que nosotros consideramos el atributo que identifica a nuestro elemento frente a otros y "value" el objeto en sí, como vemos en esta implementación ambos parámetros son del tipo object, dentro de Generics tenemos una implementación de IDictionary tipificada.

Entonces podemos llamar al método Contains y preguntar por una "key" en particular y la colección nos debería contestar si existe dentro de la colección.

Implementación del método GetEnumerator

El método GetEnumerator como vimos antes se encuentra dentro de la interface IEnumerable, pero no en este caso, porque la interface IDictionary define su propio método GetEnumerator, por lo tanto oculta la definición de IEnumerable, ok, ¿por qué IDictionary tiene su propia versión de GetEnumerator? porque IEnumerable.GetEnumerator devuelve una interface IEnumerator que es así

public interface IEnumerator
{
    bool MoveNext();
    object Current { get; }
    void Reset();
}

El problema es que en IDictionary trabajamos con objetos + un elemento que los identifica (la "key") y el método Current de IEnumerator devuelve un object, por lo tanto no nos alcanza para saber la "key" y el "value" por separado (como lo ingresamos a través del método Add), entonces veamos qué nos devuelve la implementación de GetEnumerator de IDictionary

public interface IDictionaryEnumerator : IEnumerator
{
    DictionaryEntry Entry { get; }
    object Key { get; }
    object Value { get; }
}

Vemos que hereda de IEnumerator y además agrega algunas propiedades para trabajar con "key" y "value" y con un tipo DictionaryEntry

public struct DictionaryEntry
{
    private object _key;
    private object _value;
    public DictionaryEntry(object key, object value);
    public object Key { get; set; }
    public object Value { get; set; }
}

Lo mismo, "value" y "key" por separado, ahora todo cierra, bien, explicado esto nos damos cuenta que podemos iterar sobre un IDictionary y además recuperar información de clave-valor del elemento actual así.

foreach (DictionaryEntry item in hashTable)
{
    Console.WriteLine(item.Key);
    Console.WriteLine(item.Value);
}

Igualdad en los diccionarios

Como dije antes los diccionarios nos aseguran tener sólo elementos diferentes dentro de ella basandose para determinar qué es diferente en la "key", bien, pero esto tiene algunos detalles a tener un cuenta siempre que se trabaje con diccionarios.

Imaginemos que tenemos esta clase

public class Persona
{
    private string _nombre;
    private int _dni;

    public int Dni
    {
        get { return _dni; }
        set { _dni = value; }
    }

    public string Nombre
    {
      get { return _nombre; }
      set { _nombre = value; }
    }
}

Sencilla, bien, y creamos una Hashtable y hacemos esto

Hashtable hashTable = new Hashtable();

Persona persona1 = new Persona() { Nombre = "Leonardo", Dni=123};
Persona persona2 = new Persona() { Nombre = "Leonardo", Dni=123};

hashTable[persona1] = persona1;
hashTable[persona2] = persona2;

Console.WriteLine(hashTable.Count);

Muy bien, creamos dos objetos iguales (al menos desde nuestro punto de vista) y le decimos en dos ocaciones a la Hashtable su valor (el mismo) sin embargo cuando corremos la aplicación vemos que tenemos dos elementos dentro de la Hashtable, ¿por qué?

¿GetHashCode y Equals cómo funcionan en los diccionarios?

Bueno, lo que pasa es que primeramente Hashtable se fija en el resultado del método GetHashCode de cada objeto para saber si es igual a otro, bien, nosotros no dijimos cómo debe comportarse este método, pero como todos los objetos (o sea todo) en .NET hereda de object éste tiene su implementación de GetHashCode que devuelve un Hash diferente para cada instancia de object, como resultado podemos crer n instancias de Personas iguales y todas van a retornar un hash diferente.

Entonces para implementar correctamente GetHashCode tenemos que pensar bien, en función de nuestro dominio cuándo dos objetos de la misma clase se consideran diferentes, en el caso de Persona el nombre no hace diferentes a dos personas (puede haber muchos habitantes con el mismo nombre) sin embargo el Dni (en Argentina es el nro de documento único) sí hace únicas a las personas, entonces es un buen candidato para determinar cuándo dos objetos de la clase Persona son diferentes o no.

public class Persona
{
    private string _nombre;
    private int _dni;

    public int Dni
    {
        get { return _dni; }
        set { _dni = value; }
    }

    public string Nombre
    {
        get { return _nombre; }
        set { _nombre = value; }
    }

    public override int GetHashCode()
    {
        return _dni.GetHashCode();
    }
    public override bool Equals(object obj)
    {
        return ((Persona)obj).Dni.Equals(_dni);
    }
}

Perfecto, ahora sí funciona, ya que para nosotros el Dni es la propiedad que determina si dos Persona son iguales utilizamos el hash del mismo (la clase int devuelve el mismo hash para dos números con el mismo valor), prestemos atención que también he sobre-escrito el método Equals porque la Hashtable lo consulta en caso de que el resultado de GetHashCode sea igual, por lo tanto, sino lo sobre-escribimos tampoco va a considerar ambos elementos iguales.

La interfece IEqualityComparer

Hay otra forma de indicar a la Hashtable cómo determinar si dos elementos son iguales, esto es especialmente útil si nos encontramos con una condición de igualdad particular (ya que si suministramos IEqualityComparer la Hashtable no va  a llamar a los métodos GetHashCode y Equals de los objetos) o si no queremos o podemos implementar GetHashCode y Equals en la clase, veamos su firma.

public interface IEqualityComparer
{
    bool Equals(object x, object y);
    int GetHashCode(object obj);
}

La idea es como vemos hacer lo mismo (definir GetHashCode y Equals) pero en otra clase y pasársela a la Hashtable, entonces para el ejemplo anterior la cosa sería así

public class ComparadorPersonas : IEqualityComparer
{
    public int GetHashCode(object obj)
    {
        return ((Persona)obj).Dni.GetHashCode();
    }

    public new bool Equals(object x, object y)
    {
        return ((Persona)x).Dni.Equals(((Persona)y).Dni);
    }
}

Y se utiliza así

private void Test()
{
    Hashtable hashTable = new Hashtable(new ComparadorPersonas());

    Persona persona1 = new Persona() { Nombre = "Leonardo", Dni = 123 };
    Persona persona2 = new Persona() { Nombre = "Leonardo", Dni = 123 };

    hashTable[persona1] = persona1;
    hashTable[persona2] = persona2;

    Console.WriteLine(hashTable.Count);
}

Y listo, funciona.

Conclusión

Los diccionarios nos permite manipular una lista de elementos únicos, utiliza una propiedad "key" para identificar los elementos. Es muy importante implementar correctamente los métodos GetHashCode y Equals para que la Hashtable pueda controlar la repetición de los elementos. Podemos utilizar la interface IEqualityComparer para realizar comparaciones personalizadas o por fuera de la clase. Hasta la próxima.

Referencias

Interface IDictionary (MSDN)

Hashtabls (MSDN)

 

 

2 comentarios:

knocte dijo...

Te recomiendo que uses genéricos (es decir, por ejemplo, Dictionary<,> en lugar de HashTable).

Leonardo Micheloni dijo...

Gracias knote, cada tanto leo tu blog es excelente, sobre los genéricos, ya lo sé, si lees el post con detenimiento hago mención, es simplemente un primer paso, estoy recorriendo de a poco todas las colecciones del framework, ahora bien, es cierto que no tiene mucho sentido la Hashtable existiendo el Dictionary, pero bueno, hay que saberlo. Gracias nuevamente y saludos desde Argentina.