Inicio > .NET Framework, C#, Tutorial > Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Hashtable

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Hashtable


Retomando la serie de las colecciones, tras un período de silencio… Hoy me gustaría comenzar a hablar sobre los diccionarios. Este tema es un poquito más complicado que las listas. Ya en otra entrada había hablado un poco sobre diccionarios. Ahora me interesa ver lo que probablemente sea el diccionario más sencillo (y quizás uno de los más potentes) que existe desde la primera versión del .NET Framework: Hashtable.

Esta clase se define en el espacio de nombres System.Collections. Y lo primero que hay que tener en cuenta es que es un diccionario, y por lo tanto funciona como cualquier otro diccionario. El siguiente ejemplo muestra cómo utilizar el Hashtable.

using System;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
  enum Gender { Male, Female }

  class God
  {
    public string Name { get; set; }
    public Gender Gender { get; set; }
    public string Influence { get; set; }

    public God()
      : this(string.Empty, Gender.Female, string.Empty)
    {
    }

    public God(string name, Gender gender, string influence)
    {
      Name = name ?? string.Empty;
      Gender = gender;
      Influence = influence;
    }

    public override string ToString()
    {
      return string.Format("{0} ({1}) - {2:C}", Name, Gender, Influence);
    }
  }

  class Program
  {    
    static void Main(string[] args)
    {
      Hashtable hash = new Hashtable();
      hash.Add("Odin", new God("Odin", Gender.Male, "Cielo"));
      hash.Add("Freyja", new God("Freyja", Gender.Female, "Fertilidad"));
      hash.Add("Thor", new God("Thor", Gender.Male, "Humanos"));
      hash.Add("Skadi", new God("Skadi", Gender.Female, "Muerte"));
      hash.Add("Loki", new God("Loki", Gender.Male, "Aire"));

      Console.WriteLine(hash["Odin"]);
      Console.WriteLine(hash["Loki"]);
      Console.WriteLine(hash["Thor"]);
      Console.WriteLine();

      foreach (DictionaryEntry entry in hash)
      {
        Console.WriteLine("{0} - {1}", entry.Key, entry.Value);
      }

      Console.ReadKey(true);
    }
  }
}

Este código no tiene mucha ciencia. Inicializamos una instancia de la clase Hashtable y le agregamos algunos elementos, que son objetos de la clase God que creamos unas líneas arriba y que representan uno de los dioses nórdicos Asgard. Al agregar un elemento, especificamos la llave (que en nuestro caso, sería el nombre del dios nórdico que representa el objeto). Tras agregas cinco objetos, vemos que podemos obtener el objeto en cuestión dada su llave. Esto era de esperarse, ya que Hashtable es un diccionario.

Ahora bien, hay algunas cosillas a considerar. En primer lugar, para iterar sobre los elementos de un diccionario, lo tenemos que hacer sobre objetos de tipo DictionaryEntry. Esta clase contiene dos propiedades: Key y Value, que contienen la llave y el valor.

Por otra parte, si no queremos usar DictionaryEntry, también podemos iterar sobre todas las llaves disponibles, a través de Hashtable.Keys, y con eso obtener el valor usando el indexador:

foreach (string key in hash.Keys)
{
    Console.WriteLine("{0} - {1}", key, hash[key]);
}

y obtenemos el mismo resultado.

Una cuestión importante del Hashtable es la forma en la que el diccionario ordena los elementos. Internamente, cuando se agrega un nuevo elemento, el diccionario lo guarda especialmente utilizando lo que se conoce como “hash code”, el cual es un número que no debe de cambiar bajo las mismas condiciones. Por ejemplo, si genero un hash code para un entero cuyo valor es igual a 5, otro entero con el mismo valor me debe regresar el mismo hash code. Esta técnica hace que los objetos (siempre de forma interna) se almacenen en ciertas ubicaciones de memoria, lo cual hace que cuando queremos obtener el valor dada una llave determinada, se obtenga dicha ubicación por medio del hash code sin tener que hacer tantas comparaciones de las llaves. Y esto es lo que hace del Hashtable uno de los diccionarios más eficientes.

De lo anterior se desprenden tres cosas. Primero, el objeto que se usa como llave debe permanecer inmutable mientras actúe como tal, si no se pueden obtener resultados erróneos. Segundo, por consiguiente, las llaves no pueden ser nulas. Y tercero, es imprescindible que cuando dos llaves contengan el mismo valor (o que se encuentren en el mismo estado) el hash code regresado sea el mismo. En otras palabras, cuando dos objetos obj1 y obj2 son iguales (es decir, obj1.Equals(obj2) regresa true) entonces los hash codes de ambos deben ser iguales.

Ahora bien, ¿cómo se regresa ese hash code? Hay dos formas que son esencialmente las mismas. Habrás notado que la clase object define unos cuántos métodos como ToString, GetType e Equals. Pues bien, el otro método es ni más ni menos que GetHashCode. Hashtable utiliza el valor retornado por GetHashCode. Así, el primer método consiste en sobreescribir GetHashCode y que éste valor regrese un número apropiado. Y por las reglas que establece .NET, al sobreescribir GetHashCode es necesario sobreescribir Equals. A la luz de lo expuesto, ésto tiene lógica: si dos llaves son iguales, entonces el hash code debe ser el mismo.

La segunda forma consiste en implementar la interfaz IEqualityComparer (a partir de .NET 2; en .NET 1 y .NET 1.1 las interfaces son IHashCodeProvider y IComparer). Esta interfaz define (tatatatáaaan) dos métodos. Equals y GetHashCode. Por lo que es prácticamente lo mismo que usar la primera técnica. Nota mental: yo pienso que la única ventaja de implementar IEqualityComparer es que ésta se puede implementar de forma explícita, de tal suerte que se puede dejar la versión original de Equals y GetHashCode tal cual.

En .NET framework y C#, todos los tipos de datos primitivos que son tipos-valor (estructuras) son naturalmente inmutables. Un int, un decimal y un float lo son (asignarle un valor a una variable implica crear una nueva instancia del tipo de dato). Y por definición, ningún tipo-valor puede ser nulo. Finalmente, cada tipo de dato primitivo implementa GetHashCode en función del valor mismo, de tal suerte que éstos siempre serán únicos. Por lo que todos los tipos de datos primitivos que son tipo-valor se pueden emplear sin problemas como llaves para un Hashtable.

Adicionalmente, los tipos de datos string, a pesar de ser referencias, también son inmutables (la especificación de tipos de datos comunes así lo garantiza), y además implementan como cabría esperar GetHashCode, de tal suerte que siempre que una cadena no sea nula, será también susceptible de emplearse en un Hashtable. Es por esto que nuestro ejemplo anterior funciona correctamente.

Los problemas pueden comenzar cuando queramos utilizar nuestras propias clases como llaves para nuestro Hashtable. En este caso, será nuestra responsabilidad que la clase que usemos como llave implemente Hashtable de forma correcta.

A guisa de ejemplo para ilustrar lo anterior, imaginemos este escenario. Supongamos que queremos hacer una relación entre dioses nórdicos y el equivalente dios (o semidiós) romano. Por ejemplo, queremos relacionar a Odín con Júpiter, a Thor con Hércules y a Freyja con Venus. En este caso, usaremos la clase God como llave y como valor, por lo que tenemos que implementar GetHashCode. Tomemos estos objetos:

God odin = new God("Odín", Gender.Male, "Cielo");
God thor = new God("Thor", Gender.Male, "Humanos");
God freyja = new God("Freyja", Gender.Female, "Fertilidad");

God jupiter = new God("Júpiter", Gender.Male, "Cielo");
God hercules = new God("Hércules", Gender.Male, "Humanos");
God venus = new God("Venus", Gender.Female, "Fertilidad");

Entonces, para garantizar que nuestro Hashtable siempre funcione (especialmente cuando tenemos muchas llaves) de forma eficiente, tenemos que garantizar que dos instancias con “Odín”, Gender.Male, “Cielo” siempre regresen verdadero y que además el hash code que retornen sea el mismo. Si hacemos:

Console.WriteLine(odin.Equals(jupiter));
Console.WriteLine(odin.GetHashCode() == jupiter.GetHashCode());

pues ya valió queso, porque al ejecutar ambas líneas de código, se escribirá “False” dos veces. Entonces no queda remedio más que implementar GetHashCode, y por añadidura, Equals.

Una buena regla a seguir consiste en pensar primero en Equals. ¿De qué forma dos objetos como los anteriores serían iguales? La primera respuesta natural que viene a la mente es que las propiedades de ambos objetos sean iguales. Así, la implementación de Equals en la clase God podría quedar como sigue.

public override bool Equals(object obj)
{
    God god = obj as God;
    return god != null
        && Name == god.Name
        && Gender == god.Gender
        && Influence == god.Influence;
}

Ahora bien, si la igualdad es determinada por las tres propiedades, suena lógico que GetHashCode la implementemos con base en estas tres. Pero necesitamos garantizar que éstas sean siempre iguales cuando Equals sea igual. ¿Cómo se te ocurre que podría ser?

Si pensamos, al combinar los caracteres de las tres propiedades (representadas como cadena de texto)  siempre serán las mismas cuando Equals regrese true (por ejemplo, “OdínMaleCielo”). Y como el hash code de una cadena de texto garantiza ser el mismo para todas, pues ya estuvo: podemos usar esta técnica y GetHashCode luciría así:

public override int GetHashCode()
{
    string code = string.Format("{0}{1}{2}", Name, Gender, Influence);
    return code.GetHashCode();
}

Supremo, ¿no? Ahora sí, podemos probar este código:

God odin1 = new God("Odín", Gender.Male, "Cielo");
God odin2 = new God("Odín", Gender.Male, "Cielo");
Console.WriteLine(odin1.Equals(odin2));
Console.WriteLine(odin1.GetHashCode() == odin2.GetHashCode());

Y obtendremos dos valores True en la consola. Ahora sí, ya podemos usar sin temor alguno la clase God como llave en el Hashtable. El programa completo luce algo similar a esto:

using System;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
    enum Gender { Male, Female }

    class God
    {
        public string Name { get; set; }
        public Gender Gender { get; set; }
        public string Influence { get; set; }

        public God()
            : this(string.Empty, Gender.Female, string.Empty)
        {
        }

        public God(string name, Gender gender, string influence)
        {
            Name = name ?? string.Empty;
            Gender = gender;
            Influence = influence;
        }

        public override string ToString()
        {
            return string.Format("{0} ({1}) - {2:C}", Name, Gender, Influence);
        }

        public override int GetHashCode()
        {
            string code = string.Format("{0}{1}{2}", Name, Gender, Influence);
            return code.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            God god = obj as God;
            return god != null
                && Name == god.Name
                && Gender == god.Gender
                && Influence == god.Influence;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            God odin = new God("Odín", Gender.Male, "Cielo");
            God thor = new God("Thor", Gender.Male, "Humanos");
            God freyja = new God("Freyja", Gender.Female, "Fertilidad");

            God jupiter = new God("Júpiter", Gender.Male, "Cielo");
            God hercules = new God("Hércules", Gender.Male, "Humanos");
            God venus = new God("Venus", Gender.Female, "Fertilidad");

            Hashtable hash = new Hashtable();
            hash.Add(odin, jupiter);
            hash.Add(thor, hercules);
            hash.Add(freyja, venus);

            Console.WriteLine("Odín: {0}", hash[odin]);
            Console.WriteLine("Thor: {0}", hash[thor]);
            Console.WriteLine("Freyja: {0}", hash[freyja]);
            Console.WriteLine();

            Console.ReadKey(true);
        }
    }
}

Evidentemente, la forma en la que determinemos los valores de GetHashCode a emplear lo determina la semántica de la clase. Por ejemplo, en el código anterior puedes pensar que un dios que tenga el mismo nombre sean siempre iguales sin importar su género y su influencia. En este caso, Equals compararía nada más la propiedad Name, y GetHashCode regresaría el hash code devuelto por Name. Esto puede parecer ilógico, pero es natural cuando trabajamos con clases que representan objetos de negocio cuyo contenido se extrae de una base de datos: las llaves de la tabla son las que definen los valores únicos del regristro. Por lo que cabría esperar que Equals y GetHashCode se definan en función de las propiedades que representan las llaves de la tabla.

Y ya para finalizar este artículo, me gustaría comentar algunas propiedades y métodos útiles con los que cuenta Hastable. Es decir, adicionales a las esperadas en un diccionario. En primera instancia, tenemos que los métodos ContainsKey y ContainsValue se pueden usar para saber si una llave o un valor existen dentro de la colección. CopyTo, por su parte, copia los elementos a un array unidimensional.

Bueno mis estimados, hemos visto ya cómo utilizar Hashtable, así como las bondades que nos ofrece, pero también los cuidados que hemos de proporcionarle. Sin embargo, hay que reconocerlo, en la mayoría de los casos no necesitamos diccionarios tan eficientes como Hashtable. Existen otras opciones de diccionarios introducidas a partir de .NET 2, sobresaliendo System.Generics.Dictionary<T, T>, el cual además tiene la ventaja de contar con llaves y valores fuertemente tipados. Pero esto será tema de otro post. Así que hasta aquí llegamos. Espera la continuación de esta serie en unos días.

Anuncios
Categorías:.NET Framework, C#, Tutorial Etiquetas: ,
  1. Kary
    junio 6, 2012 en 9:34 pm

    hola :D

    Este blog esta genial!! felicidades!

    Tengo una pregunta: Para saber si una llave es unica en un hashtable los métodos: equals, getype y tostring() funcionan? por que leí que el GetHashCode GetHashCode no garantiza valores devueltos únicos para objetos diferentes.

    espero tú respuesta ….

    • junio 7, 2012 en 9:50 am

      Hola Kary, gracias por tus comentarios.

      En efecto, la implementación de Object.GetHashCode no garantiza que los valores devueltos sean únicos. Es responsabilidad de la clase derivada implementarlo. Por ejemplo, Int32 implementa su propio GetHashCode, que devuelve el valor numérico tal cual. Otras clases lo que hacen es hacer un or de bits (^) sobre las variables miembro que definen el estado, o bien sobre el GetHashCode de dichas variables miembro. Por ejemplo:

      public class Foo
      {
      public string A { get; set; }
      public string B { get; set; }

      public override int GetHashCode() {
      return A.GetHashCode() ^ B.GetHashCode();
      }
      }

      Pero nuevamente, es responsabilidad de cada clase implementarlo.

      ¡Saludos!

  1. noviembre 30, 2010 en 8:39 pm
  2. mayo 26, 2011 en 10:30 pm

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s