Tabla hash
| ||||||
Tabla Hash. Es una estructura de datos no lineal cuyo propósito final se centra en llevar a cabo las acciones básicas (inserción, eliminación y búsqueda de elementos) en el menor tiempo posible, mejorando las cotas de rendimiento respecto a un gran número de estructuras.
Sumario
Linealidad de estructuras
Las estructuras de dato se clasifican, según la linealidad de sus elementos, en lineales y no lineales. Los Arreglos, Listas, Pilas y Colas son estructuras de datos lineales. Esto significa que los elementos de las mismas se almacenan y/o acceden uno detrás del otro. Por ejemplo, en un arreglo, a la hora de añadir un elemento, el mismo se insertará al final de los elementos ya insertados, o entre dos existentes, pero siempre respetando que los elementos se encuentren y administren uno tras otro; esto es, su linealidad.
Los árboles y grafos son ejemplos de estructuras de datos no lineales. Esto significa que sus elementos no se almacenan uno tras otro, o en su defecto, la forma de administrar los mismos no es lineal. Por ejemplo, en un árbol los elementos se insertan como hijos de otros, creando una jerarquía no lineal.
Las Tablas Hash son estructuras de datos no lineales. En este aspecto, su comprensión puede no ser obvia, puesto que los elementos de una Tabla Hash, como se discute más adelante, se almacenan en un arreglo, que es una estructura lineal, pero la administración de dichos elementos no se realiza de forma lineal. En el apartado 3.1 se ahonda en este particular.
Tiempo de ejecución
Uno de los aspectos críticos a tomar en cuenta a la hora de trabajar con una estructura de datos es el tiempo que demora la ejecución de sus acciones. Una estructura que demore menos que otra en ejecutar cada una de sus acciones, será, en grado general, mejor. Actualmente, en muchos de los más prestigiosos centros de estudios de algoritmos del mundo, se presta especial atención a la reducción del tiempo de rutinas complejas.
El tiempo de un algoritmo se representa mediante la letra Θ seguida, entre paréntesis, de una expresión que lo determina. Por ejemplo, la representación Θ(1) significa que el tiempo que demora una acción es siempre constante e inmediata. Es, por lo general, el tiempo menor que se puede lograr para una rutina determinada. Otro caso se ve dentro de una colección de N elementos donde, igual por ejemplo, puede aparecer la siguiente expresión: Θ(N). Esto significa que el tiempo que demora la rutina depende de la cantidad de elementos de la colección.
En un arreglo lineal común las acciones de insertar, modificar y obtener poseen tiempo directo Θ(1), pues las mismas se realizan de manera inmediata, tan sólo especificando el índice deseado. La acción de hacer una copia del arreglo en otro, sin embargo, posee tiempo Θ(N), pues mientras más elementos posea el arreglo original más demorará en terminarse la rutina.
Uno de los mayores intereses de los desarrolladores actuales de estructuras de datos y algoritmos como tal es minimizar el tiempo que los mismos toman para llevar a cabo diferentes tareas. Las Tablas Hash son una estructura que tiene como fin minimizar el tiempo dedicado a sus principales acciones; entiéndase insertar, eliminar y buscar.
Tablas Hash. Idea general de funcionamiento
Una Tabla Hash es una estructura que puede almacenar una gran cantidad de información y lograr para sus acciones principales tiempos de ejecución Θ(1). Esto supera las cotas comunes de, por ejemplo, las listas enlazadas, cuyos tiempos oscilan aproximadamente por Θ(N).
La idea general de la Tabla Hash es utilizar la capacidad de los arreglos lineales, donde las acciones de inserción y obtención poseen tiempos Θ(1), y asignar ese mismo tiempo a la acción de búsqueda, que en un arreglo sí es de Θ(N).
Si en un arreglo lineal A de longitud L se necesitara buscar un elemento E la rutina a utilizar sería, con toda seguridad la siguiente:
int BuscarElemento(E)
{
for(int i = 0; i < L; i++)
{
if(A[i] == E)
return i;
}
}
Rutina de búsqueda dentro de un arreglo en lenguajes C, C++, Java y similares
Como puede verse, la rutina depende de la cantidad de elementos de A (así como de la cercanía de E a los primeros elementos, pues mientras más cerca esté del primer elemento, más rápido se ejecutará el algoritmo). Una Tabla Hash mejora esta secuencia de búsqueda de la siguiente manera:
Se toma, del dato a almacenar en el arreglo, uno de los atributos principales (preferentemente el que lo identifica y que será único en cada cual) y se diseña entonces una función, conocida como función Hash o función de hasheo, que convierte ese dato en un entero que representa un índice en el arreglo. Con ese índice, es posible insertar, eliminar u obtener el elemento de forma directa.
Visto gráficamente:
En el ejemplo mostrado se desea almacenar un grupo de objetos de tipo Estudiante en la Tabla Hash. Cada uno de los objetos, representados en diferentes colores en la figura (rosa, verde y amarillo, para ser más exactos), posee un dato expediente, que lo identifica. La función Hash convierte ese expediente en un entero entre 0 y N-1, siendo N el tamaño del arreglo, y luego realiza la acción determinada con ese índice.
Imaginemos ahora que tenemos el siguiente par de datos para dos objetos de estudiantes:
- Estudiante1(25411, “López”, “Julio”, 4, “Informática”).
- Estudiante2(30441, “Rodríguez”, “Amelia”, 1, “Industrial”).
Cada vez que se vaya a insertar un elemento en la Tabla Hash, lo primero será pasarle la clave del elemento, en este caso el expediente, a la función Hash. Supóngase que para los dos datos, respectivamente, la función Hash arroja los siguientes resultados: 45 y 7. Eso significa que el objeto Estudiante1 será almacenado en Arreglo[45] y Estudiante2 será almacenado en Arreglo[7]. Luego, a la hora de buscar, si se desease buscar digamos a Estudiante2, se pasaría el expediente (la clave) a la función Hash, que devolvería el 7, índice donde ya se almacenó el dato, y el cual se accede ahora de manera directa.
Las acciones dentro de una Tabla Hash se implementan de la siguiente manera:
- Inserción: Para insertar un dato se toma el atributo que se vaya a utilizar como clave y se la pasa a la función Hash, que determina la posición en que debe ir en el arreglo. Luego el objeto se inserta en la posición devuelta. La función Hash NO PODRÁ devolver un valor igual de índice para dos claves diferentes, pues se incurre en errores de estructuración.
- Acceso (Búsqueda, Eliminación y Modificación): Para buscar un elemento sólo habrá que pasarle a la función Hash la clave del elemento a buscar y ésta determinará la posición en que se encuentra. Como el acceso a un elemento de un arreglo es directo [tiempo Θ(1)], esta acción es automática. La búsqueda se lleva a cabo de forma muy rápida. Luego se llevará a cabo cualquier tarea sobre el dato.
Como el acceso a los elementos dentro de una Tabla Hash es pseudo-aleatorio, la misma es vista como una estructura de datos no lineal, aun cuando los datos son almacenados dentro de un arreglo lineal.
Tablas Hash. Tipos de Implementaciones
Como puede fácilmente deducirse, la parte complicada de una Tabla Hash es la implementación de la función de hasheo. La misma deberá poseer un algoritmo sólido que convierta cualquier valor pasado como clave en un índice para el arreglo de elementos.
Es evidente que no será igual un algoritmo para convertir una tipo de dato String que uno de tipo int. Entonces, las implementaciones cambian en todos los sentidos, según el tipo de información que se maneje, o lo que es lo mismo, la utilidad que se le dará a la estructura. Respecto a este particular existen varias variantes de implementación.
La más común resulta heredar de una clase principal TablaHash, e implementar la función de hasheo como mejor convenga a las necesidades del problema a resolver. El siguiente ejemplo muestra la definición de la clase padre en C++:
Se observan algunos puntos importantes:
- Los datos a almacenar son de tipo void* (apuntador a void), lo que se traduce en genericidad. Se podrá trabajar cualquier tipo de dato. Una variante alternativa a esto último son las plantillas.
- La clave de cada dato también está compuesta por un tipo void*, pues no se conoce su tipo de dato aún.
- La función de hasheo, FuncionHash, es una función virtual pura, lo que significa que la clase también es una clase virual pura y no se podrá generar objetos de ella. Para crear un objeto de clase, primero habrá que heredar de la clase TablaHash y luego implementar la función FuncionHash.
El mismo ejemplo en lenguaje Java:
public class TablaHash
{
protected Object Arreglo[ ];
// El arreglo es de tipo Object, o dato genérico.
protected int longitud;
// El tamaño del arreglo.
public TablaHash(int);
// Se pasa el tamaño del arreglo como entrada
public Object clave); Buscar(Object
// Busca el elemento clave
public void Insertar(Object elemento);
// Inserta elemento
public void Eliminar(Object clave)
// Elimina el elemento clave
public abstract int FuncionHash();
// Función de hasheo
}
Súperclase TablaHash definida en lenguaje C++
Una variante interesante en Java para implementar la Tabla Hash es colocar la función de hasheo fuera de la clase, en una interfaz, e implementarla en cada variante de Tabla Hash necesaria:
public interface Hash
{
int FuncionHash();
}
public class TablaHash implements Hash
{
private Object Arreglo[ ];
// El arreglo es de tipo Object, o dato genérico.
private int longitud;
// El tamaño del arreglo.
public TablaHash(int);
// Se pasa el tamaño del arreglo como entrada
public Object Buscar(Object clave);
// Busca el elemento clave
public void Insertar(Object elemento);
// Inserta elemento
public void Eliminar(Object clave);
// Elimina el elemento clave
}
Variante Java con definición de Interfaz para la implementación de la función Hash
Otra variante de implementación, que no se muestra en este artículo, es el uso de los operadores identificadores de tipo (como typedef en C++), que determinan a qué tipo pertenece un dato como tal, que permiten identificar el tipo de la clave y llamar a la función Hash que se ajusta al mismo. Lo mismo se traduce en la implementación de un gran número de funciones Hash diferentes.
Las Tablas Hash no están limitadas al uso de arreglos unidimensionales; por el contrario es posible encontrarlas para más de una dimensión. El proceso de diseño depende, entonces, enteramente de la función Hash.
El desarrollo de la función Hash constituye la parte más importante en el proceso de creación de una Tabla Hash, y, dada su complejidad, sólo programadores expertos toman la responsabilidad de diseñarla, aunque actualmente existe un enorme número de variantes disponibles para su uso en Internet. Para la correcta implementación de una función Hash, dos atributos deben ser relevantes: el tipo de dato de la clave pasada y el tamaño del arreglo, o sea su cantidad de elementos. Una función Hash correctamente diseñada debería ser capaz de seguir generando índices válidos acorde se expanda o contraiga dinámicamente el arreglo central de la estructura.
Tablas Hash. Aplicaciones más comunes
La principal aplicación que se da a las Tablas Hash es la de confección de diccionarios, pues la facilidad de búsqueda hace que las palabras puedan ser encontradas en lapsos muy cortos. Por ejemplo, véase la siguiente estructura de clase para una palabra de un diccionario (definida en lenguaje Java):
public class TPalabra
{
private String palabra;
private String significado;
private String sinonimos[ ];
// métodos públicos
}
Parte de una clase TPalabra en lenguaje de programación Java.
En la misma se muestra la palabra a buscar, el significado de la misma y una lista de sinónimos que pueden ser utilizados como vínculos a otras palabras. El uso de una Tabla Hash para el diccionario almacenaría en un arreglo decenas de miles de objetos de tipo TPalabra, cada uno representando una palabra diferente. El usuario que desea buscar una palabra la escribe y pide su búsqueda. La propia palabra, por supuesto, es utilizada como clave para que la función Hash la localice dentro del arreglo. Al final son devueltas al usuario la descripción de la palabra y la lista de sinónimos.
De la misma forma se pueden utilizar las Tablas Hash en los compiladores, para la búsqueda rápida de aquellos identificadores declarados y que han pasado a secciones de la memoria que no son directos. Algunas calculadoras científicas también poseen Tablas Hash que almacenan complejas operaciones que pueden ser llamadas luego de forma muy rápida.
En general, cualquier aplicación que necesite de una estructura de datos con cotas de tiempo eficientes puede hacer uso de las Tablas Hash. No existe limitación al respecto, salvo las que pueda ofrecer, en un momento, el mismo diseño del problema a resolver.
Aspectos generales
Las Tablas Hash son estructuras de datos no lineales que utilizan un arreglo lineal para almacenar sus elementos e incorporan una función de hasheo que brinda a la acción de buscar un tiempo de ejecución Θ(1).
La función de hasheo o función Hash de una Tabla Hash convierte un dato del elemento a almacenar, conocido como clave, en un entero entre 0 y N-1 que representa un índice dentro del arreglo de la estructura, que posee N elementos. Para el diseño de la función de hasheo, el tipo de dato de la clave y la cantidad de elementos del arreglo son relevantes.
La principal aplicación de las Tablas Hash es el diseño de diccionarios, pero bien pueden ser utilizadas en un sin fin de tareas donde la velocidad de las búsquedas sea siempre un punto crítico en el proceso de desarrollo.
Fuentes
- Mark Allen Weiss. Estructuras de Datos en JavaTM compatibles con Java 2TM, 2000.
- Heileman. Estructuras de Datos, Algoritmos y Programación Orientada a Objetos, 1994.
