Tablas de Dispersión (Hash), objetivos y funcionamiento

El autor, desde el rincón del programador, nos ofrece una introducción a la utilización de algoritmos hashing para almacenar datos indexados por claves que salen de esos propios datos.

En muchas ocasiones, nuestras aplicaciones requieren acceder a los datos utilizando como clave para el acceso parte de esos mismos datos. Esta necesidad de acceso asociativo es una situación muy común en el mundo real. Vamos a introducir un sencillo ejemplo que nos ayude a comprender las explicaciones venideras:
 
 

Supongamos que una ferretería nos contrata para que les implantemos un sistema de gestión de sus proveedores. Para cada proveedor desean guardar el nombre de proveedor, el nombre de la persona de contacto, el número de teléfono, el correo electrónico y el descuento sobre la tarifa base. Desean poder acceder a toda la información de un proveedor a partir de su NIF.

 
 Como vemos, un programa en principio tan sencillo, implica acceder a los datos utilizando como clave para el acceso parte de los propios datos. Esto no es un problema en absoluto trivial. Pero puestos a pensar, seguro que alguno de nosotros, llegaría rápidamente a una solución genial:
 
 

  1. Defino una clase que permita almacenar toda la información de un proveedor:
     


     public class TProveedor {
     
      /**************
      ** Atributos **
      **************/
     
      // Datos que vamos a guardar de cada proveedor
      private String NIF;
      private String nomEmpresa;
      private String nomContacto;
      private String numTelefono;
      private String email;
      private int dto = 0;
     
      /******************
      ** Constructores **
      ******************/
     
      // Constructor General de la clase Proveedor: inicializa los Strings
      public TProveedor (String NIF,String empresa,String contacto,String email,String Tlf,int dto) {
     
      this.NIF = NIF;
      this.nomEmpresa = empresa;
      this.nomContacto = contacto;
      this.email = email;
      this.numTelefono= Tlf;
      this.dto = dto;
      }
     
      // Constructor compacto
      public TProveedor (String NIF,String empresa) {
     
      this.NIF = NIF;
      this.nomEmpresa = empresa;
      }
     
      /*********************
      ** Metodos publicos **
      *********************/
     
      // gets para obtener los datos de un proveedor
     
      public String getNif() {
     
      return this.NIF;
      }
     
      // **************************************
      public String getEmpresa() {
     
      return this.nomEmpresa;
      }
     
      // **************************************
      public String getContacto() {
     
      return this.nomContacto;
      }
     
      // **************************************
      public String getTlf() {
     
      return this.numTelefono;
      }
     
      // **************************************
      public int getDto() {
     
      return this.dto;
      }
     
      // **************************************
      public String getMail() {
     
      return this.email;
      }
     
      // sets complementarios:
     
      public void setNIF (String N) {
     
      this.NIF = N;
      }
     
      // **************************************
      public void setEmpresa (String N) {
     
      this.nomEmpresa = N;
      }
     
      // **************************************
      public void setContacto (String N) {
     
      this.nomContacto = N;
      }
     
      // **************************************
      public void setTlf (String N) {
     
      this.numTelefono = N;
      }
     
      // **************************************
      public void setDto (int nuevo) {
     
      this.dto = nuevo;
      }
     
      // **************************************
      public void setMail (String nuevo) {
     
      this.email = nuevo;
      }
     }
     

     

  2. Declaro un array de elementos de tipo Proveedor y un entero que mantenga la primera posición libre:
     


      Proveedor [ ] Proveedores;
      int libre;
     

     
     

  3. Con la estructura así definida, las operaciones básicas serían de la siguiente forma:
     

    • Búsquedas: Recorrer secuencialmente el array hasta que el Proveedor sea el buscado
       
    • Altas: Añadir un nuevo objeto al final del array e incrementar libre.
       
    • Bajas: Buscar y marcar como libre.
       
    • Modificaciones: Buscar y modificar.
       

 
 Y lo cierto es que esta solución cuasi trivial funciona. Pero no solo no es óptima, sino que realmente es muy mala. El coste computacional que implica es brutal: para buscar un elemento hay que recorrer todo el array hasta que el elemento aparezca. En el peor de los casos (cuando el elemento no está) es necesario recorrer todo el array. Aún en el caso medio, tendremos que hacer N/2 accesos al array para encontrar un registro. Esto implica una complejidad asintótica O(N)(el tiempo de acceso es proporcional al tamaño del array) lo cual es un precio bastante alto por obtener el acceso asociativo.
 
 Como primer intento, no está del todo mal, pero es muy mejorable. Además, tenemos suerte. Dado que el acceso asociativo a la información es una necesidad común, hace mucho tiempo que existen soluciones mucho mejores para este problema.
 
 

Tablas Hash

 
 Las tablas Hash o tablas de dispersión solucionan satisfactoriamente nuestro problema: nos permiten acceder asociativamente a la información y, además, lo hacen en un tiempo medio constante, es decir, que el tiempo necesario para acceder a un elemento, no va a depender del número de elementos que almacene la estructura. Además, aunque en principio lo parezca, estas estructuras no tienen nada de magia, con lo que cualquier mortal puede manejarlas sin necesidad de saber pilotar una escoba.
 
 Una estructura hash se construye con tres elementos básicos :
 

  • Un vector direccionable mediante número de posición ( un array ) capaz de almacenar N elementos.
     
  • Una función de dispersión que nos permita a partir de la clave obtener el índice donde estará el dato asociado a esa clave.Es frecuente que existan dos claves distintas para las que la función de dispersión produzca el mismo indice.Esto se denomina colisión, y las dos claves distintas que dieron lugar al mismo índice, se dicen sinónimas respecto a la función de dispersión utilizada.
     
  • Una función de resolución de colisiones.

 
 Función de dispersión
 
 Con respecto a la función de dispersión, su elección es clave para el buen funcionamiento de la estructura y la discusión sobre cual utilizar se escapa del objetivo de este artículo. Simplemente reseñar que ha de cumplir las siguientes características:
 
 

  • Ha de ser una función sencilla y por tanto rápida.
     
  • Distribuir uniformemente los elementos en el espacio de almacenamiento
     
  • Evitar en lo posible la aparición de sinónimos
     
  • Para dos claves muy similares, generar posiciones distantes.

 
 Nosotros utilizaremos funciones basadas en la operación módulo. En primer lugar, obtenemos un numero a partir de la clave alfanumérica utilizada y luego hacemos la operación modulo N sobre ese numero. Así obtendremos una posición donde almacenar nuestro elemento. A tener en cuenta que N (el tamaño de la tabla) ha de ser un número primo, pues sino, solo influirían en la determinación de la posición correspondiente a un determinado elemento las últimas cifras del número generado a partir de la clave alfanumérica .
 
 


 private static int Hash1(String Clave) {
 
 int valor = Clave.charAt(0);
 int tam = Clave.length();
 
 for (int i = 1; i < tam ;i++) {
 
 valor += Character.getNumericValue( Clave.charAt(i));
 
 }
 
 return (valor % N);
 
 }
 

 
 
 Función de resolución de Colisiones
 
 Es inevitable que algunas claves distintas lleguen a producir el mismo resultado de la función de dispersión . Esto es un problema. Pero hay estrategias para resolverlo de mejor o peor manera. Profundizar en esto no es el objetivo de este artículo introductorio, pero podemos comentar que existen básicamente dos tipos de estrategias:
 
 

  • Dispersión Abierta: utilizaremos una estructura de datos auxiliar para guardar los elementos cuya posición ya esta ocupada por otros elementos.Se suele utilizar una lista.
     
  • Dispersión cerrada: Evita el uso de una 2ª estructura de datos. En caso de colisión, se busca una posición alternativa hasta que se encuentre una libre.Se pueden llegar a producir colisiones en cadena.
     

 
 En nuestro pequeño applet de ejemplo, en cada posición de la tabla hash, tendremos una lista de proveedores. Esta es una solución que evita las colisiones: aunque tengamos que insertar dos items distintos en el mismo slot de la tabla, no hay problema, pues insertamos cada uno de los items en la lista del mismo modo que si no hubiera sinónimos. Por tanto, el método de inserción no ha de considerar casos particulares, únicamente ha de llamar al método de inserción del objeto lista asociado a cada posición de la tabla. Esta alternativa no es la más eficiente, pero si una de las más fáciles de entender.
 
 


 public void insertar (TProveedor p) {
 int pos = this.Hash1(p.getNif());
 Tabla[pos].insertar(p);
 }
 

 
 Una vez conocidos todos los ingredientes, podemos explicar la receta. Las operaciones básicas en una estructura Hash funcionan de la forma siguiente:
 
 

  • Búsquedas:
     

    1. A partir de la clave, se le aplica la función de dispersión. Esto nos da un índice del array.
       
    2. Si el dato buscado está en ese índice, se devuelve el índice y se va a 6.
       
    3. Sino, se busca en zona de resolución de colisiones.
       
    4. Si está, se devuelve la posición del elemento en la estructura y se va a 6.
       
    5. Sino se indica que no se encuentra y se va a 6.
       
    6. Fin.

     

  • Altas:
     

    1. A partir de la clave, se le aplica la función de dispersión. Esto nos da un índice del array.
       
    2. Si ese índice esta libre o marcado como borrado, se guarda en él el elemento y se va a 6. Sino, ir a 3.
       
    3. Si quedan posiciones libres, ir a 4. Sino indicar que no quedan posiciones e ir a 6
       
    4. Se aplica la función de resolución de colisiones, que nos da un nuevo índice.
       
    5. Si está libre, se guarda el elemento y se va a 6.
       
    6. Sino se vuelve a 3.
       
    7. Fin.
       
  • Modificaciones:
     

    1. Se busca el elemento. Si encontrado, ir a 2. Sino indicar error e ir a 3.
       
    2. Se hacen las modificaciones en la posición devuelta por la búsqueda. Ir a 3.
       
    3. Fin.
       

     

  • Bajas
     

    1. Se Busca el elemento como borrado. Si encontrado, ir a 2. Sino indicar error e ir a 3.
       
    2. Se marca el elemento como borrado.Ir a 3.
       
    3. Fin

 
 Como vemos es bastante sencillo. Realmente solo tienen una mínima complejidad las funciones de Búsqueda y Alta.
 
 
 

Como determinar el tamaño de la tabla(N)

 
 El tamaño N es un parámetro de vital importancia para el correcto funcionamiento de la estructura. Si N es demasiado alto, las operaciones serán muy eficientes, pero desperdiciaremos demasiado espacio. Si por el contrario, N es demasiado bajo, las colisiones se dispararán y la estructura tendrá un rendimiento muy parecido a la solución trivial propuesta al principio del artículo. Por tanto, elegir N no es en absoluto banal. Además, uno de los fundamentales problemas de las tablas Hash es que una vez puesta en funcionamiento, la única forma de hacer crecer N es hacer una estructura nueva y copiar los datos que ya hubiera en la antigua: N no se puede cambiar dinámicamente.
 Además, el N adecuado depende de la estrategia empleada en la resolución de colisiones. En el caso de la dispersión cerrada:
 
 


 Nº de elementos en la tabla/N < 0,5 es decir, si planeamos tratar con un máximo de, por ejemplo 5000 registros, se tiene
 5000 / N < 0,5, de donde N > 5000*2, es decir, tomaríamos como N el primer primo mayor que 10000.
 

 
 
 

Consideraciones respecto al rendimiento

 
 Hemos hablado de que idealmente, esta estructura tiene un comportamiento asintótico O(1). Pero esto en la práctica rara vez es cierto. Tendríamos que tener una tasa mínima de colisiones para que esto fuese así. Pero lo cierto es que con un tamaño N ajustado a nuestro problema, las tablas Hash obtienen un rendimiento más que razonable y nos proveen de un mecanismo para acceder asociativamente a los datos sin por ello tener que asumir unos tiempos desmedidos en la manipulación de la estructura.

Marcos Abel Souto
http://cricava.com/java/detalleArticulos.php?id=131

Leave A Comment?