La función hash la emplearemos cuando tengamos un conjunto ilimitado de valores de entrada y queramos obtener un conjunto limitado de valores resultado. Normalmente, los valores de entrada serán cadenas de caracteres de longitud variable, que convertiremos en cadenas de longitud fija. Aunque este tipo de funciones admiten todo tipo de datos de entrada. Además, los resultados de la función pueden delimitarse a un conjunto definido de caracteres: enteros y alfanuméricos.

En la imagen siguiente puedes ver el comportamiento de una función hash:

Comportamiento de la función hash

Comportamiento de la función hash

Características de una función hash

Una buena función hash, tendrá las siguientes características:

  • Genera valores únicos para cada entrada: La probabilidad de obtener el mismo resultado para dos entradas distintas es muy baja, idealmente cero. Es decir, para dos posibles entradas distintas: e1 y e2, la probabilidad de h(e1) = h(e2) tiene que ser prácticamente nula.

Aunque la probabilidad de obtener el mismo resultado para dos entradas distintas es muy baja, puede darse dicha situación. En este caso se habrá producido una colisión. Una buena función hash tiene muy pocas colisiones.

  • Los resultados son repetibles: Cada vez que apliquemos la función hash a una misma entrada, obtendremos siempre el mismo resultado.
  • La función no es invertible: En otras palabras, no podemos obtener el valor de entrada a partir del resultado

Usos de las funciones hash

Este tipo de funciones son computables, es decir, se pueden implementar mediante un algoritmo, lo que hace que resulten muy útiles para ciertas aplicaciones. La mayoría de los lenguajes de programación incorporan librerías de funciones que nos permiten implementar distintas funciones hash en nuestros programas.

Entre los usos más habituales de las funciones hash podemos encontrar el almacenamiento de contraseñas de usuarios en una base de datos. En lugar de almacenar las contraseñas en texto, almacenamos el resultado de aplicar una función hash a las contraseñas. De esta forma aumentamos la seguridad de la base de datos, y si esta se viera comprometida, las contraseñas de los usuarios estarían a salvo, ya que no podrían obtenerse a partir de los resultados de la función hash que es lo que guardamos en la base de datos.

También son ampliamente empleadas para comprobar si algún archivo ha sido modificado, cuando por ejemplo lo descargamos desde internet. Aseguramos de esta manera la integridad de los ficheros que enviamos y descargamos por internet, actuando la cadena hash como una especie de firma digital.

Y por supuesto, otra utilidad de estas funciones es la organización de los datos, proporcionando una alternativa al trabajo con tablas de índices.

Empleando el hashing en la organización de los datos en ficheros

La idea es que aplicando la función hash a cada valor del campo que utilicemos como índice, obtendríamos la dirección de un bloque donde almacenaríamos la dirección física en memoria donde encontraríamos el registro asociado al índice. En el caso de que se produzca una colisión, almacenamos el par clave – dirección del registro en el mismo bloque. Y cuando fuéramos a leer un dato, tendríamos que recorrer el bloque. En cualquier caso, las colisiones son muy improbables y los bloques serán siempre muy pequeños y rápidos de recorrer.

Para entender la lógica detrás de esta manera de organizar los datos, voy a poner un ejemplo práctico, empleando el ya famoso fichero de proveedores de SuperGades, el famoso supermercado de Antonio que hemos venido empleando como ejemplo.

Estamos queriendo acceder lo más rápidamente posible a las fichas de los proveedores de Antonio, y para ello queremos organizarlas en grupos que nos faciliten la vida y reduzcan el tiempo de búsqueda. Para ello disponemos de un montón de cajones, cada uno con una letra del abecedario. Colocamos cada ficha de proveedor en el cajón que tenga la letra por la que empieza su nombre. Hemos dividido nuestros datos en varios bloques y cuando queramos recuperar los datos de un proveedor, iremos a buscarlos únicamente en el cajón que tiene la letra por la que empieza su nombre.

Pues bien, ahora imagina que tienes una forma de organizar las fichas de los proveedores en el que tendrías un cajón para cada proveedor. Esto es lo que, en un entorno digital, te permite la función hash. Aunque en las escasas situaciones que tengamos colisiones, podríamos encontrarnos dos fichas de proveedores en un cajón, quizás hasta tres en una situación extrema. Pero en cualquier caso, las búsquedas serían muy rápidas, ya que el número de elementos del conjunto será siempre muy pequeño.

Aplicando esta idea a la organización de nuestros datos, lo que haremos será crear una estructura conocida como tablas hash. Estas se organizan en bloques donde se guarda el par clave – puntero, el valor de la clave y un puntero que apunta a la dirección para recuperar todos los datos del registro asociado a la clave.

Aquí os dejo un ejemplo de lo que podría ser una tabla hash en el caso del fichero de proveedores del supermercado SuperGades, tomando el nombre de proveedor como clave.

Tabla Hash

Ejemplo de tabla hash

Aplicando la función hash al contenido de la clave (en este caso, nombre del proveedor), se obtiene la dirección de un bloque. En dicho bloque se almacena el par clave-puntero. En el ejemplo de arriba puede observarse que para los valores de la clave: “Panadería Fresca” y “Frutas Gutiérrez” se produce una colisión, y ambos pares clave-puntero se guardan en el mismo bloque.

Accediendo a los datos

Para acceder a los datos asociados a una clave, seguiríamos los siguientes pasos:

  • Aplicamos la función hash al valor de la clave de búsqueda, con lo que obtendríamos la dirección del bloque donde buscar
  • En dicho bloque, buscamos el puntero que apunta a los datos del registro asociado a la clave. Si tuviéramos colisiones tendríamos que realizar una búsqueda secuencial, pero como ya he indicado antes el número de elementos en el bloque será muy pequeño, ya que las colisiones son muy improbables.
  • Con el puntero recuperado, nos posicionamos donde este nos indique y leemos los datos.

Insertando datos

Si queremos introducir nuevos datos, procedemos de la siguiente manera:

  • Guardamos los datos en el fichero y nos quedamos con un puntero que apunte a los mismos.
  • Aplicamos la función hash al contenido de la clave que estemos empleando, y con ello obtenemos la dirección de un bloque
  • En ese bloque, guardaremos el valor de la clave y el puntero (el del primer punto) que apunta a donde comienzan los datos asociados en el fichero.

NOTA:

Este post es parte de la colección “Arquitectura de Datos” que reproduce los apuntes de la clase que imparto sobre el tema en ESIC. Puedes ver el índice de esta colección aquí.