Tablas Hash en JavaTablas Hash en Java

María González García

EDI Curso 2010-2011

Java HashTable

¿Qué es? Estructura de datos que asocia llaves o claves

con valores. Cada elemento de una tabla hash tiene dos

variables : Capacidad inicial: Es simplemente la capacidad

que tendrá la tabla a la hora de crearla. Factor de carga: Mide la cantidad de elementos que

se pueden insertar en la tabla antes de que su capacidad aumenta automáticamente.

Java HashTable

¿Qué es? Una tabla hash en java es abierta y además

gestionará colisiones. Si el número de entradas de la tabla excede al

resultado del producto de la capacidad actual por el factor de carga, la tabla hash aumentará su capacidad utilizando un método rehash().

Java HashTable

¿Cómo funciona? INSERCIÓN

La clave se transforma con una función hash() en un número que nos indica donde se va a almacenar el elemento.

El elemento se almacena en la posición de la tabla obtenido en el paso anterior.

Si en la posición de la tabla ya había otro elemento, se ha producido una colisión. Se busca el siguiente elemento libre, se asocia una lista a cada posición de la tabla o se aplica otra función.

Java HashTable

¿Cómo funciona? BÚSQUEDA

Para recuperar los datos, es necesario conocer la clave del elemento, a través de ella obtendremos una posición de la tabla hash.

El valor obtenido se mapea al espacio de direcciones de la tabla.

Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.

Java HashTable

Constructores

Hashtable () Construye una tabla vacía con un tamaño inicial

(11) y un factor de carga de 0,75. Hashtable (int initialCapacity)

Construye una tabla vacía con un tamaño específico y un factor de carga de 0,75.

Hashtable (initialCapacity int, float loadFactor) Construye una tabla vacía con un tamaño y un factor de carga específicos.

Java HashTable

Métodos básicos

Object get (Object key)

Devuelve el valor asignado a la clave especificada o null si no encuentra ninguno.

Object put (Object key, Object value)

Asocia la clave especificada con el valor especificado en la tabla hash. Devuelve el valor asociado previamente con la clave especificada, si lo hay. En caso contrario, devuelve el valor nulo.

Java HashTable

Métodos básicos

Object remove (Object key)

Elimina la clave y su valor asociado de la tabla hash.

boolean containsKey(Object key)

Devuelve true si la clave especificada se asigna a un valor en la tabla y false en caso contrario.

Java HashTable

Métodos básicos

boolean containsValue(Object value)

Devuelve true si hay una o más claves asignadas al valor especificado o false en caso contrario.

int size ()

Devuelve el tamaño de la tabla hash. isEmpty boolean ()

Devuelve true si la tabla está vacía y false en caso contrario.