Twitter Facebook Google + RSS Feed

Tablas de dispersión, de la teoría a la práctica

0
.NETAlgoritmos/TAD

Viernes, 05 de diciembre de 2008 a las 14:06hs por Dario Krapp

Poco uso práctico tendría la elaboración de programas, si dichos programas no pudiesen interactuar con la información brindada por sus usuarios, dicha información define el problema puntual que un programa o grupo de programas debe resolver, sin importar la clase de problema a solucionar o tipo de algoritmo implementado, los datos que un programa toma para generar cualquier solución y como dichos datos son manejados, son en muchas ocasiones el factor determinante de su éxito o fracaso.
Cuando la cantidad de datos que un algoritmo debe manejar son pocos, la forma de almacenarlos y recuperarlos no determina un factor influyente en la performance del programa. Pero a medida que la cantidad de datos a manejar se incrementa, la velocidad con la que los datos son almacenados y recuperados se vuelve en ocasiones el mayor de los problemas, posiblemente por esta cuestión, es que este problema ha sido abordado en miles de ocasiones por infinidad de personas y no en vano, han encontrado algunas soluciones que podrían sernos de utilidad. Veamos en primera instancia la solución más inocente para el almacenamiento de una gran cantidad de datos, la idea más sencilla para almacenar un grupo de elementos, es sin ninguna duda emplear un arreglo donde en cada posición se almacenará un elemento, esto ya trae problemas desde el principio debido a que no es frecuente conocer cuántos elementos se deben almacenar, y no es muy performante la idea de ir copiando el arreglo cuando una redimension es necesaria.
La algoritmia y diseño de estructuras de datos permite crear a partir de las unidades de almacenamiento más elementales como arreglos y punteros, tipos de datos cada vez más complejos y abstractos como listas, árboles, diccionarios, etc., apoyados unos sobre otros al igual que los ladrillos en una pared. Empleando estructuras de datos es posible intentar resolver el problema de la redimension de los arreglos empleando quizás una lista, de la cuales hay diversas opciones a elegir(simplemente encadenada, doblemente encadenada, circular, etc.) dependiendo del tipo de problema que se deba resolver, esta opción resuelve el problema de la redimension en forma eficiente, ya que es posible crear y eliminar elementos con un costo mínimo, pero no resuelve otro problema que es el de la búsqueda de elementos, es claro que en una lista encontrar un elemento es bastante costoso, ya que se debe ir recorriendo elemento por elemento hasta poder encontrar el deseado, si existen n elementos, el algoritmo deberá recorrer los n elementos (en el peor caso claro está) para encontrar el elemento buscado, esto suele denominarse como O(n) o como que el orden del algoritmo es n, el orden de un algoritmo determina su eficiencia.
En este punto es donde se ha intentado minimizar el problema de las búsquedas. la algoritmia y diseño de estructuras de datos ha aportado diversas soluciones a este problema, por ejemplo la búsqueda binaria ha permitido mejorar el orden desde n a log2(n), un orden logarítmico es una solución bastante buena en contraposición al orden lineal que habíamos obtenido previamente. Un punto a considerar es que en el caso de la búsqueda binaria hay un costo extra en el momento de la inserción de elementos, debido a que los valores deben insertarse ordenadamente, dependiendo de la cantidad de inserciones en contraposición a las búsquedas esta solución puede ser interesante. Otra opción es emplear una Tabla de dispersión, que es una solución que bajo ciertas condiciones resuelve el problema con una performance aceptable y una ventaja que posee es que es relativamente sencilla de implementar.

Para comprender la técnica supongamos que tenemos e1, e2… ei elementos pertenecientes al conjunto E, donde E es el conjunto con el total de elementos con los que operaremos.

Conjunto de elementos

supongamos también que existe una función H capaz de tomar un elemento ei y devolver otro elemento de otro tipo (no importa que tipo sea mientras que soporte la operación de comparación, debe ser posible determinar si dos elementos que devuelve la función H son iguales o no lo son) esta idea es bastante similar a la noción de función matemática que se estudiaba en la escuela primaria, donde existen un dominio, una imagen y una función capaz de relacionar uno o varios elementos del dominio con otro de la imagen, el secreto de esta técnica es la idea de que con nuestra función podamos dividir el conjunto total de elementos E en varios subconjuntos (también llamados “buckets”) para poder buscar entre menos valores, con esta idea tendremos entonces todo el conjunto E dividido en subconjuntos menores donde cada subconjunto posee la siguiente particularidad, para cada uno de sus elementos la función H devuelve el mismo valor, o sea, existe una relación de equivalencia entre los elementos de cada subconjunto.

División en subconjuntos

Aunque aún no conocemos quién es la función H, sabemos que cuanto más podamos dispersar el grupo de elementos de E mejor será la función ya que cuando deseemos encontrar un elemento tendremos que buscarlo entre menor cantidad de elementos dentro de algún subconjunto.
A continuación veremos una de las implementaciones más clásica de tablas de disperción, la misma emplea como estructura soporte de datos un arreglo de subconjuntos.

Arreglo de subconjuntos de E

A la vez cada subconjunto suele implementarse sobre una lista simplemente encadenada, aunque podrían emplearse otras estructuras de datos.

Arreglo de listas encadenadas

La idea de esta implementación es que cada celda del arreglo o bucket contenga un subconjunto de E, si dado un elemento la función de dispersión es capaz de seleccionar una celda dentro del arreglo, simplemente deberemos incluir el elemento en el bucket correspondiente y el problema quedará resuelto, la búsqueda es similar.
La cantidad de buckets a emplear (longitud del arreglo de subconjuntos) también influirá en la performance, en muchas implementaciones es posible elegir la cantidad de buckets que desean emplearse al momento de crear la instancia de la clase.
No cabe duda que la elección de la función de dispersión es el punto clave de la implementación, una mala elección podría hacer que los elementos se almacenen por completo dentro de un mismo bucket quedando todos los demás vacios y en ese caso la estructura que estaríamos utilizando seria una lista simplemente encadenada, pero con aun mas complejidad agregada, hay mucha investigación en este campo y pueden encontrase algunas funciones de hash clásicas, un ejemplo para elementos del tipo de dato cadena de caracteres es djb2, presentada por Dan Bernstein en comp.lang.c

unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;
    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash;
}

Y pueden encontrase miles más como sdbm, lose lose, one at time, etc. Cada una de ellas realizando las operaciones más extraordinarias imaginables sobre los datos de entrada, un punto importante es que la función H sirve para solo algunos tipos de datos, si los elementos son un tipo complejo, como por ejemplo “automovil”, “empleado” la función de hash planteada previamente no podrá realizar ningún cálculo.
El uso de funciones de dispersión criptográficas, como por ejemplo SHA-1 también pueden utilizarse, ya que da un buen resultado, aunque su cálculo puede ser costoso.
Existen diversos modelos de tablas de dispersión, en nuestro primer caso estamos viendo el modelo de dispersión abierta (open hashing), pero existen también: Chaining, Coalesced hashing, Perfect hashing, Dynamic perfect hashing, Probabilistic hashing, Robin Hood hashing, etc. Chaining o Hashing cerrado lo veremos más adelante.
Un uso frecuente para las tablas de dispersión es el modelado de diccionarios, un diccionario es una estructura de datos compuesta por un grupo de elementos que poseen una clave y un valor, un diccionario permiten almacenar, buscar, eliminar, determinar si existen valores a través de su clave, la cual debe ser única por cada elemento del diccionario, en estos casos las operaciones de dispersión se efectúan sobre la clave.
Debe quedar claro que si bien los diccionarios pueden implementarse muy bien sobre una tabla de dispersión, también pueden existir otros tipos de datos que podrían implementarse sobre esta estructura como por ejemplo un conjunto, así como también un diccionario podría implementarse sobre un árbol o sobre una lista encadenada (lo cual no sería una muy buena idea en el común de los casos).
Muchos lenguajes modernos utilizan tablas de dispersión, un ejemplo es C# que proporciona una implementación en System.Collections.Generic.Dictionary.
Otra implementación puede encontrarse en System.Collections.Hashtable, pero la misma difiere un poco de lo comentado y la veremos luego.

En el caso de Dictionary de .NET se implementa un diccionario fuertemente tipado (Generics) sobre una tabla de dispersión abierta, siguiendo la idea de valor clave mencionada previamente. un punto interesante es la función de hash, funciona sobre cualquier tipo de dato, por ejemplo:

Dictionary<SampHashKey, string> oD1
Dictionary<int, string> oD2
Dictionary<string, int> oD3

Para poder tener una función de dispersión genérica .NET hace lo siguiente, la clase object posee un método llamado GetHashCode que devuelve un valor entero (int) con un código, la función GetHashCode de alguna forma permite mapear cualquier objeto a un numero entero, GetHashCode es empleado cuando se agrega, busca u opera con un elemento en la tabla de dispersión, para darle una entrada a la función de hash. Quien no esté totalmente convencido puede hacer la siguiente prueba:

public struct SampHashKey
{
    public int a { set; get; }
    public int b { set; get; }
    public int c { set; get; }
    public int d { set; get; }
}

public override int GetHashCode()
{
    MessageBox.Show("llamando a GetHashCode");
    return base.GetHashCode();
}

public void Test()
{
    Dictionary<SampHashKey, string> oD = new Dictionary<SampHashKey, string>();
    oD.Add(sSHK1, "s");
}

Al invocarse al método Add de oD, aparecerá el cuadro de texto con el mensaje “llamando a GetHashCode”. Esta es una idea inteligente y quizás la única posibilidad de poder emplear una misma función de hash para cualquier tipo de dato, permitiéndole a la instancia tabla de dispersión sobre la cual se encuentra implementado el Dictionary seleccionar un bucket donde almacenar los datos para toda clave posible. Esta metodología elegante y simple, sigue apoyándose una buena elección de función de dispersión y en una buena elección de función GetHashCode. Intuitivamente nos es lógico pensar que más allá de lo que haga la función de dispersión con el código de hash que devuelve GetHashCode, si varios objetos devuelven el mismo GetHashCode, todos ellos irán a parar inevitablemente al mismo bucket.¿Pero es posible que varios elementos tengan un mismo HashCode?, consideremos el siguiente ejemplo:

public struct SampHashKey
{
    public int a { set; get; }
    public int b { set; get; }
    public int c { set; get; }
    public int d { set; get; }
}

public void Test()
{
    SampHashKey sSHK1 = new SampHashKey() { a = 1, b = 2, c = 3, d = 4 };
    SampHashKey sSHK2 = new SampHashKey() { a = 2, b = 1, c = 3, d = 4 };
    SampHashKey sSHK3 = new SampHashKey() { a = 2, b = 3, c = 1, d = 4 };
    SampHashKey sSHK4 = new SampHashKey() { a = 2, b = 3, c = 4, d = 1 };
    SampHashKey sSHK5 = new SampHashKey() { a = 3, b = 2, c = 4, d = 1 };
    SampHashKey sSHK6 = new SampHashKey() { a = 3, b = 4, c = 2, d = 1 };

    Hashtable oHT = new Hashtable();
    oHT.Add(sSHK1, "Valor1");
    oHT.Add(sSHK2, "Valor2");
    oHT.Add(sSHK3, "Valor3");
    oHT.Add(sSHK4, "Valor4");
    oHT.Add(sSHK5, "Valor5");
    oHT.Add(sSHK6, "Valor6");

    int iSHK1Hash = sSHK1.GetHashCode();
    int iSHK2Hash = sSHK2.GetHashCode();
    int iSHK3Hash = sSHK3.GetHashCode();
    int iSHK4Hash = sSHK4.GetHashCode();
    int iSHK5Hash = sSHK5.GetHashCode();
    int iSHK6Hash = sSHK6.GetHashCode();

    if (sSHK1.GetHashCode() == sSHK2.GetHashCode() &&
        sSHK2.GetHashCode() == sSHK3.GetHashCode() &&
        sSHK3.GetHashCode() == sSHK4.GetHashCode() &&
        sSHK4.GetHashCode() == sSHK5.GetHashCode() &&
        sSHK5.GetHashCode() == sSHK6.GetHashCode())
        MessageBox.Show("¡Ouch!"); 
}

Para quien no tenga ganas de cargar el IDE y probar el código en un WinForm, le comento que al invocar al método Test, un cuadro de texto aparecerá en pantalla indicando que varios objetos distintos pueden tener un mismo HashCode y no es para sorprenderse, ya que el ejemplo fue preparado para que esto sucediera.
En casos del mundo real las posibilidades de que esto suceda son menores, en realidad dependerán del objeto key seleccionado y los valores que el mismo posea, pero de todas formas es bueno saber que puede suceder y mejor aun, es saber que se puede solucionar gracias a la flexibilidad del diseño de las clases de .NET.

Consideremos lo siguiente:

public struct SampHashKey
{
    public int a { set; get; }
    public int b { set; get; }
    public int c { set; get; }
    public int d { set; get; }
 
    public override int GetHashCode()
    {
        return a +
            Convert.ToInt32(Math.Pow(b, 2)) +
            Convert.ToInt32(Math.Pow(c, 3)) +
            Convert.ToInt32(Math.Pow(d, 4));
    }
}

Sobrecargando el método GetHashCode apropiadamente, hemos conseguido devolver nuevos y distintos valores. Una vez más cabe mencionar que esta sobrecarga de la función GetHashCode sirve solo para este ejemplo puntual, seguramente debe funcionar desastrosamente para otro conjunto de valores. Pero si un caso de este tipo se diera en la vida real, se deberá enfocar hacia una solución similar, evaluar el conjunto de valores posibles y puntualmente encontrar un reemplazo adecuado para el método GetHashCode, la complejidad u orden de este diccionario solo puede calcularse en forma estadística, ya que en el peor de los casos será o(n) cuando todos los elementos se agrupen en un mismo bucket, pero claro que esto no es muy probable. el orden en promedio de un Dictionary es o(n/m) siendo n la cantidad de elementos y m la cantidad de buckets.

Como ya hemos mencionado, existen otros tipos de tablas de dispersión, en las tablas de dispersión cerradas, cada bucket puede contener un solo elemento, por lo que cuando otro elemento es mapeado al mismo bucket se produce una colisión la cual debe resolverse, en tal caso se emplean funciones de rehashing para encontrar una nueva ubicación para el elemento, la función de rehashig suele incluir como parámetro de entrada el numero de intento, ya que no es sabido cuantas colisiones se producirán hasta finalmente poder alojar al elemento.

Como ya habíamos mencionado .NET ofrece otra implementación de tabla de dispersión, pero en este caso no se implementa sobre una tabla de hash abierta. La clase de System.Collections.HashTable que es débilmente tipada sigue empleando el método GetHashCode para poder mapear cualquier objeto, y es otro diccionario implementado sobre una tabla de dispersión con ciertas particularidades, la estructura de datos permite alojar un elemento por celda, por lo que cuando otro elemento sea mapeado a la misma celda se producirá una colisión, la clase empleará una funciones de rehashing hasta que el ítem pueda reubicarse, este esquema posee también lo que se denomina factores de carga “Load Factors” y que se manifiesta como una proporción siendo un valor numérico entre 0.1 y 1.0 (que se establece en el constructor de la clase) e indica la máxima proporción de elementos en los buckets, por ejemplo un factor de carga de 0.5 indica que a lo sumo, la tabla de dispersión tendrá la mitad (0.5) de buckets completa, lo ideal sería pensar que el valor óptimo es 1, ya que le pide a la tabla de hash que intente llenar todos los buckets, pero el valor mágico es 0.72 y es el que se emplea por defecto si no se le establece otro en el constructor, inclusive si se establece el valor 1.0 el mismo será automáticamente escalado a 0.72. Otra particularidad es que la tabla puede crecer de tamaño si los factores de carga se encuentran comprometidos, si bien los factores de carga son costosos de mantener aseguran que los elementos se distribuyan de la forma más pareja posible en los buckets.

A continuación y para cerrar el articulo presentaremos un par de funciones muy interesantes:

H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize
 
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize 

key = GetHashCode()
hashsize = cantidad de buckets
k = número de intento

Estas funciones son, como han de imaginarse, las funciones de hash y rehash empleadas por la clase HashTable de .NET. las mismas pueden encontrarlas, junto con más información referente en el artículo:
http://msdn.microsoft.com/en-us/library/aa289149.aspx escrito por Scott Mitchell.


0 comentarios »

Deja un comentario

Buscar