Sunday, March 05, 2006

Tablas Hash

Una Tabla Hash es un tipo de colección formado por pares de clave y valor, que se almacenan dentro de una tabla. La clave se utiliza para obtener el índice de ubicación del valor dentro de la tabla, utilizando para ello una función denominada función hash. Así pues, una estructura hash está formada por tres elementos básicos:
1) una tabla o array de tamaño N donde se almacenan los elementos.
2) una función hash que, dada una clave, nos da el índice de la tabla donde se encuentra almacenado el dato asociado a esa clave.
3) una función de resolución de colisiones, que determina qué hacer cuando para dos claves distintas se obtiene el mismo índice en la tabla.

Al rellenar una tabla hash se proporciona una clave para agregar a la tabla y un valor que acompaña a la clave. La clave no tiene por qué ser numérica, se acepta cualquier objeto.
Cuando se agrega a la tabla uno de estos pares de clave y valor, la tabla hash observa la clave y le proporciona un código hash, un número que identifica la clave (cada clave agregada obtiene un código hash). Sin una función hash tendríamos que recorrer toda la tabla para encontrar el valor asociado a una clave. En cambio la función hash nos dice qué entrada de la tabla mirar para cada clave. De este modo se consigue un mecanismo de búsqueda en tablas mucho más rápido.

Tablas hash en Java:
En Java podemos encontrar la clase java.util.Hashtable, que implementa una tabla hash para mapear claves a valores tal y como se ha explicado arriba. La clase Hashtable extiende la clase abstracta Dictionary, e implementa Cloneable y Serializable.
Cualquier objeto distinto de null puede usarse indistintamente como clave o como valor.
Los objetos utilizados como clave deben implementar los métodos hashCode() y equals() con objeto de hacer búsquedas y comparaciones. El método hashCode() devuelve un entero único y distinto para cada clave; si dos claves son iguales según el método equals(), el método devuelve el mismo entero (esto es, el índice de almacenamiento en la tabla será el mismo para las dos claves).

Ejemplo de inserción de datos en una Hashtable:
Hashtable numeros = new Hashtable();
numeros.put("uno",new Integer(1));
numeros.put("dos",new Integer(2));

Ejemplo de obtención de datos de una Hashtable:
Integer n = (Integer)numeros.get("dos");

0 Comments:

Post a Comment

<< Home