UD1-Tablas Hash Flipbook PDF

UD1-Tablas Hash

---

109 Views
29 Downloads
FLIP PDF 452.7KB

DOWNLOAD FLIP

REPORT DMCA

UAX_Texto(01).dot

Técnicas de programación

DOCUMENTO1

1.

Tablas Hash

ÍNDICE MOTIVACIÓN ................................................................... 3 P ROP ÓS ITOS .................................................................. 4 P REP ARACIÓN P ARA LA UNIDAD ....................................... 5 1. F UNDAMENTOS ........................................................... 7 1.1.MOTIVACIÓN .............................................................................. 7 1.1.1. MODELO DE US O ................................................................................. 8 1.2.TIP O DE DATO .......................................................................... 10

1.3.F UNCION HAS H O DE DIS P ERS IÓN ............................................. 12 1.3.1. F UNCIÓN HAS H P ARA ENTEROS .......................................................... 12 1.3.2. F UNCIÓN HAS H P ARA S TRING ............................................................. 12 1.4.E L P ROBLEMA DE LAS COLIS IONES ............................................ 13

2. TABLA HAS H CERRADA .............................................. 16 2.1.MODELO DE TABLA HAS H CERRADA .......................................... 16 2.2.R ES OLUCIÓN DE COLIS IONES .................................................... 18 2.2.1. R ES OLUCIÓN LINEAL.......................................................................... 18 2.2.2. R ES OLUCIÓN CUADRÁTICA ................................................................. 20 2.2.3. R ES OLUCIÓN P OR DOBLE DIS P ERS IÓN ................................................ 22 2.3.E L P ROBLEMA DEL BORRADO .................................................... 24

2.4.IMP LEMENTACIÓN DEL TIP O TABLA HAS H CERRADA.................... 26 2.4.1. INS ERCIÓN ........................................................................................ 26 2.4.2. BÚS QUEDA ........................................................................................ 27 2.4.3. BORRADO ......................................................................................... 27 2.5.AMP LIANDO LA TABLA ............................................................... 28 2.5.1. IMP LEMENTACIÓN DE REHAS H ............................................................ 29 2.5.2. MODIFICACIÓN DEL MÉTODO DE INS ERCIÓN ......................................... 30

3. TABLA HAS H ABIERTA................................................ 31

1

3.1.MODELO DE TABLA HAS H ABIERTA............................................ 31 3.2.IMPLEMENTACIÓN DEL TIPO TABLA HASH ABIERTA ..................... 32 3.2.1. INSERCIÓN ........................................................................................ 32 3.2.2. BÚSQUEDA ........................................................................................ 33 3.2.3. BORRADO.......................................................................................... 34

3.3.AMPLIANDO LA TABLA ............................................................... 34 3.3.1. IMPLEMENTACIÓN DE REHASH ............................................................ 35

4. LA API DE TABLA HASH DE JAVA ................................ 36 4.1.LA CLASE HASHTABLE .............................................................. 36 4.2.LA CLASE HASHSET ................................................................. 37 4.3.LA CLASE HASHMAP ................................................................ 37

CONCLUSIONES ............................................................ 39 RECAPITULACIÓN .......................................................... 40 AUTOCOMPROBACIÓN ................................................... 41 SOLUCIONARIO ............................................................. 45 PROPUESTAS DE AMPLIACIÓN ........................................ 46 BIBLIOGRAFÍA................................................................ 47

2

MOTIVACIÓN En primer curso has visto estructuras de datos para guardar información y manejarla en un programa. Conoces cómo utilizar arrays, listas, pilas e incluso árboles de datos donde almacenar, buscar y recuperar información. Todos ellos tienen un coste importante de manejo. ¿Y si te dijesen que existe una estructura de datos donde se tarda lo mismo en buscar un dato ya tenga 10 elementos que 1.000 que 1.000.000? En esta unidad verás cómo es esto posible y cómo utilizar esta estructura en un programa. Se llama Tabla Hash.

3

PROPÓSITOS En esta unidad encontrarás:

4



Los principios de funcionamiento de una Tabla Hash.



Qué características tienen que tener los datos para utilizarlos en una Tabla Hash.



Cómo funciona la estructura abstracta de datos Tabla Hash.



Distintas formas de implementación de una Tabla Hash, los problemas que plantea y cómo resolverlos.



Qué implementaciones de Tabla Hash existen en la API de Java y los métodos principales para su uso.

PREPARACIÓN PARA LA UNIDAD Para abordar esta unidad debes tener en cuenta y manejar con claridad los siguientes conceptos: 

Qué es una estructura de datos.



Qué significa implementar un tipo abstracto de datos y las distintas posibilidades con que se puede realizar.



Tener una buena práctica de programación en el manejo de estructuras de datos de información en un programa.

5

1.

FUNDAMENTOS

1.1. MOTIVACIÓN Cuando los programas son cada vez más complejos es importante disponer de estructuras de datos que sean los más completas y potentes posible para poder manejar la información con la mayor eficacia. Ya habrás visto en el primer curso qué significa la complejidad algorítmica y cómo afecta en los recursos y tiempo necesario para la ejecución del mismo cuando crece el tamaño del problema que estemos tratando. Recordando las estructuras de datos básicas, deberías manejar ya las siguientes: 

Array: estructura lineal en la que se puede acceder de forma aleatoria a cualquier elemento del array.



Listas: estructura lineal que permite enlazar la información de forma que a un elemento le sigue otro.



Árboles: estructura jerárquica en la que un elemento puede tener elementos hijos.

Se supone que manejas apropiadamente las estructuras indicadas: array, listas y árboles, además de otras estructuras que ya habrás estudiado como pilas y colas. Si no recuerdas su uso es importante darles un repaso.

Estas estructuras, desde el punto de vista de complejidad algorítmica presentan la siguiente complejidad para las operaciones básicas de inserción, búsqueda y borrado.

7

Inserción Búsqueda Borrado Array

O(1)

O(N)

O(N)

Lista

O(1)

O(N)

O(N)

Árbol

O(log N)

O(log N)

O(log N)

Tabla1: Complejidad de las estructuras de datos básicas

Como puede observarse de la Tabla 1, el tiempo que se tarda en ejecutar una operación depende del tamaño del problema, de forma que cuanto más grande es el problema más se tarda en realizar la operación. Sería muy interesante disponer de una estructura en la que el tiempo que se tardase en realizar cualquiera de las operaciones fuese básicamente siempre el mismo, independiente de cuantos datos se manejasen, ya fuesen 100, 1.000 o 1.000.000.

Una Tabla Hash consigue que todas las operaciones sobre ella, inserción, búsqueda y borrado tengan una complejidad constante, lo que implica que el tiempo que se tarda en realizar no depende de lo grandes que sean los datos.

Esta estructura es la Tabla Hash cuya complejidad para las operaciones anteriores es la siguiente: Inserción Búsqueda Borrado Tabla Hash

O(1)

O(1)

O(1)

Tabla 2: Complejidad de las operaciones para una Tabla Hash.

1.1.1. MODELO DE US O Suponga que se desea guardar en su estructura de datos la información de un conjunto de personas. Estas personas tendrían un nombre, apellidos, DNI, y otra información adicional dependiendo de su uso. La clase Persona podría definirse como: public class Persona { String nombre; String apellidos; String DNI; }

8

Una forma sencilla y muy rápida de guardar las personas en un array podría ser utilizar el valor del número del DNI como índice en la tabla, de forma que si la persona tiene el DNI número 58585858X, podríamos guardar los datos de esa persona en la posición 58585858 del array. Esta estrategia nos obligaría a disponer de un array de 100.000.000 de posiciones. Con un array de este tamaño resultaría muy sencillo realizar las operaciones de inserción, búsqueda y borrado con las características enunciadas en la tabla 2. Para ello las operaciones funcionarían de la siguiente forma: 

Inserción: para insertar una nueva persona en el array, basta obtener en valor del DNI, buscar en el array la posición correspondiente y guardar la persona en dicha posición.



Búsqueda: para buscar una persona, habría que hacerlo por su DNI. Con el valor de su DNI, se comprueba si existe alguna persona en la posición del DNI. Si existe, esa tiene que ser la persona que tiene dicho DNI. Si no existe, no tenemos datos de tal guardada.



Borrado: básicamente la operación es igual que la búsqueda, salvo que si la persona se encuentra guardada en el array, posteriormente se elimina del mismo.

Como puedes observar, el paso de búsqueda obliga a realizar dicha búsqueda por DNI, si se quisiese buscar por otro dato, por ejemplo por apellidos, sería necesario realizar una búsqueda lineal desde el principio hasta que se encontrasen los datos. Así mismo, se está utilizando el DNI como valor que identifica de manera única a los objetos de mi estructura de datos (las personas). Si hubiese más de una persona con el mismo valor de DNI, ello nos generaría un problema pues no se podría diferenciar una de otra. Por ello, para poder utilizar una Tabla Hash los datos que se guarden tienen que cumplir los siguientes requisitos: 

El valor a guardar en la tabla debe tener un elemento que permita identificar a dicho objeto.



Este valor que identifica al objeto debe ser único para cada objeto, de forma que no puedan existir dos objetos diferentes que compartan dicho valor.

Los datos que se guardan en una Tabla Hash deben tener una clave que los identifica. Todos los objetos de una Tabla Hash deben tener claves diferentes.

Con este valor se calcula mediante una función, denominada función hash o función de dispersión la posición en la que se debe de guardar el objeto en la tabla. De esta forma la función hash o función de dispersión se convierte en el elemen-

9

to fundamental para conseguir que todas las operaciones tengan complejidad constante.

La función de Hash es la que nos permite obtener la posición de un objeto en la Tabla Hash a partir de su clave.

Lógicamente para guardar un grupo de personas no vamos a crear un array de tamaño 100.000.000. Si el grupo a guardar es pequeño, por ejemplo de un centenar de personas, con un array de tamaño 1.000 es más que suficiente. Ello implica cómo convertir un valor como el del DNI en un valor que nos dé la posición en un array de tamaño 1.000. La idea es hacer algún tipo de cálculo con el valor que define el objeto, denominado clave del objeto, y una vez realizado el cálculo hacer la operación módulo tamaño de la tabla, para que el valor siempre sea correcto dentro del intervalo de valores del array.

La clave de un objeto permite identificar al objeto. Dicha clave se utilizar para realizar las operaciones en la Tabla Hash.

Lógicamente cuando se haga la operación módulo tamaño de la tabla, es posible que exista más de un elemento que nos devuelva la misma posición de la tabla. De esta forma se genera lo que se denomina una colisión, es decir dos objetos con clave diferente, para los que una vez aplicada la función de hash, el resultado de la misma es la misma posición de la tabla. En las siguientes secciones se verán distintas estrategias para solventar este problema.

1.2. TIP O DE DATO Como tipo abstracto de dato la definición de la estructura de datos y las operaciones se puede realizar de forma independiente de su implementación final. A efectos de describir la implementación la definición de una tabla hash se realizará de la siguiente forma: /** * @author Jesús Sánchez Allende */ public class TablaHash { }

10

Es decir la Tabla Hash se define como una tabla clase genérica que admite dos tipos de objetos, el primero E define los objetos que se guardan en la tabla y el segundo K define el tipo de la clave. Por ejemplo, para declarar una tabla de objetos Persona, cuya clave es el DNI utilizaríamos: TablaHash miTablaHash;

La operación de insertar un elemento, debe recibir un elemento y una clave e insertar dicho elemento en la tabla hash. Pudiera ocurrir que dicho elemento ya estuviese en la tabla, en cuyo caso no se puede añadir. Esto es debido a que si hubiese dos elementos distintos con la misma clave, al buscar uno de ellos por su clave no habría manera de decidir cuál de ellos es el que se desea. En este sentido una Tabla Hash puede verse como un conjunto de datos, pues no tiene repetidos. La operación de insertar un elemento devolverá un booleano indicando si se ha realizado la operación o no. La definición de la operación será por tanto: /** * Insertar un elemento con su clave en la tabla hash. Si ya existe un elemento * con dicha clave no se inserta y devuelve false. Si la tabla supera el * factor de carga límite, se amplía la tabla y se hace un rehash. * @param dato El dato que se quiere guardar * @param clave La clave del dato a guardar. * @return true si se ha insertado correctamente y false en caso contrario. */ public boolean insertar(E dato, K clave){ }

En las operaciones que se definen para el tipo, si una operación no se puede realizar dicha operación devuelve un valor de false o un objeto null.

La operación de buscar un elemento debe recibir una clave y devolver el elemento correspondiente a dicha clave. Si no existe dicho elemento en la tabla devolverá un objeto nulo. La definición de la operación será por tanto: /** * Busca el dato que corresponde con la clave dada * @param clave La clave del dato que se quiere. * @return El elemento de la tabla que tiene la clave buscada. Si no existe * devuelve null. */ public E buscar(K clave){ }

La operación de borrar un elemento debe recibir una clave y devolver un Booleano que indique se realizó la operación de borrado. Si no existe un elemento

11

en la tabla con dicha clave devolverá false. La definición de la operación será por tanto: /** * Elimina de la tabla el dato que corresponde con la clave. * @param clave La clave del dato que se desea eliminar. * @return true si el elemento se encontró y borró y false en caso contrario. */ public boolean borrar(K clave){ }

1.3. FUNCION HASH O DE DISPERSIÓN La función hash es la función que permite dar toda su funcionalidad a las tablas hash. En este sentido es importante el diseño de una función hash apropiada al tipo de dato correspondiente a la clave del objeto. Los tipos más habituales son, un valor entero o un String, aunque también podría ser un objeto cualquiera.

1.3.1. FUNCIÓN HASH PARA ENTEROS En este sentido si la clave es un valor entero la función hash puede ser tan simple como utilizar ese mismo entero para obtener la posición en la tabla, de la siguiente forma: private int fHash(int clave){ return clave % tabla.length; }

Dependiendo de las características del valor entero, puede que sea interesante realizar alguna operación con él, de forma que se genere una cierta aleatoriedad en el patrón de valores posibles, por ejemplo de la siguiente forma: private int fHash(int clave){ return (clave * clave) % tabla.length; }

Sin embargo, el realizar operaciones que son más costosas puede suponer un mayor tiempo de cálculo de la clave.

1.3.2. FUNCIÓN HASH PARA STRING En muchas ocasiones la clave es un String, ya sea un código de registro, una matrícula de un vehículo, un identificador, etc. El cálculo de la función hash para el String implica utilizar los caracteres del String para operar con todos ellos y obtener un valor entero. El modelo de cálculo más sencillo es utilizar todos los caracteres y sumarlos, obteniendo de esta forma un entero que se utiliza para determinar el hash. La siguiente función realiza esta operación: private int fHash(String clave){

12

int hash = 0; for(char c: clave.toCharArray()){ hash += c; } return hash % tabla.length; }

La función anterior tiene el problema de que palabras con las mismas letras, con un orden diferente, tienen el mismo valor de hash, lo que genera colisiones en la resolución de las posiciones para dichas claves. Por ejemplo, al sumar los caracteres de las palabras “amor”, “roma” y “ramo”, todas ellas tienen el mismo valor de hash. Una opción mejor para ello, pero más costosa en cálculo es utilizar una función como: hash = s[0]*31n-1 + s[1]*31n-2 + … + s[n-1] Siendo s un array con los caracteres del String y n el tamaño del String. La función que permite realizar este cálculo es la siguiente: private int fHash(String clave){ int hash = 0; for(char c: clave.toCharArray()){ hash += (31*hash + c) % tabla.length; } return hash; }

La complejidad de la operación de la función Hash puede afectar al rendimiento de la tabla, aunque en general suele ser poco significativo.

El hecho de realizar la operación del módulo dentro del bucle for previene que el valor de hash crezca demasiado y supere el valor que se puede guardar en una variable de tipo entero. Las propiedades de la función módulo permiten realizar la operación de esa forma siendo equivalente a haberla calculado solamente al final.

1.4. EL P ROBLEMA DE LAS COLIS IONES Como ya se ha comentado anteriormente, cuando dos claves diferentes producen el mismo valor de hash, significa que hay dos claves que deben ir en la misma posición. Suponga para el ejemplo que se tienen que insertar los siguientes valores enteros, que se utilizan también como claves, en una tabla de tamaño 11.

13

Valores: 34, 47, 56, 69, 12 Al calcular los valores de hash correspondientes se obtienen los siguientes valores: hash (34) = 34 % 11 = 1 hash (47) = 47 % 11 = 3 hash (56) = 56 % 11 = 1 hash (69) = 69 % 11 = 3 hash (12) = 12 % 11 = 1 Es decir, los valores 34, 56 y 12 deberían ir en la misma posición, la posición 1 de la tabla y los valores 47 y 69 deberían ir en la misma posición, la posición 3 de la tabla.

Cuando dos claves diferentes tienen el mismo valor de hash se produce una colisión.

Como esto no es posible existen dos estrategias básicas: 

Tablas hash abiertas: En una tabla hash abierta en cada posición de la tabla se conecta una lista de objetos que colisionan en dichas posición. En este sentido la tabla hash abierta para la situación anterior se correspondería con la siguiente figura: 0 1

34

56

47

69

2 3 4 5 6 7 8 9 10 Figura 3: Tabla Hash abierta.

14

12



Tabla hash cerrada: Al insertar el segundo elemento que colisiona con una posición hay que buscarle una posición diferente a partir de la posición en que colisiona. En este sentido existen distintas estrategias para buscar un sitio libre a partir del valor de has calculado. En una sección próxima se examinan con detalle distintas estrategias.

Si se conociesen a priori los valores que se van a insertar en la tabla se podría intentar conseguir una función de hash perfecta. Se denomina así a la función hash que consigue que no colisione ninguno de los valores. En general, como no se conocen a priori los valores que se van a insertar no tiene sentido intentar calcular una función de hash perfecta. Por ejemplo para la función anterior, hash(x) = x2 / 19 siendo la división una operación sobre enteros, es una función hash perfecta pues al calcular el valor de hash para todos los valores: hash (34) = 60 % 11 = 5 hash (47) = 116 % 11 = 6 hash (56) = 165 % 11 = 0 hash (69) = 250 % 11 = 8 hash (12) = 7 % 11 = 7 todos los valores de hash resultante son diferentes.

Una función hash perfecta es aquella para la que no colisiona ninguna de las claves de los objetos de una tabla hash.

15

2.

TABLA HAS H CERRADA

2.1. MODELO DE TABLA HAS H CERRADA Como ya se ha tratado anteriormente en una Tabla Hash las posiciones de los elementos se calculan utilizando una función hash o función de dispersión que nos permite calcular directamente la posición en la que se ubican los elementos a guardar. Una estrategia para almacenar la información es utilizar un array donde, directamente en cada una de las posiciones del array se guarda el objeto a almacenar. A esta estrategia se denomina Tabla Hash cerrada.

En una Tabla Hash cerrada todos los elementos se guardan dentro del array de la tabla. Cada elemento de la tabla debe guardar tanto el dato como la clave por la que se almacena.

Para ello en la definición de la clase Tabla Hash necesitamos almacenar, en cada posición de la tabla, el objeto junto con su clave. Para ello definimos una clase CeldaHash que guarda esos dos valores de la siguiente forma: class CeldaHash { private E dato; private K clave; /** * Constructor de un contenedor para el dato y su clave * @param dato El dato a guardar * @param clave La clave del dato */ public CeldaHash(E dato, K clave) {

16

this.dato = dato; this.clave = clave; } /** * Dato de la CeldaHash * @return El dato que contiene */ public E getDato() { return dato; } /** * Clave de la CeldaHash * @return La clave que contiene */ public K getClave() { return clave; } }

La clase CeldaHash es un objeto que permite guardar tanto el objeto dato como su clave.

La clase Celda Hash sencillamente que permite guardar el valor del dato y su clave, así como los métodos para obtener los valores del dato y la clave. Como se puede observar, una vez creada una Celda Hash con dichos valores no permitimos su modificación. La Tabla Hash Cerrada la definimos de la siguiente forma: public class TablaHash { /** * Array donde se guardan los valores en la Tabla Hash. * Se trata de un array de objetos CeldaHash que guardan el dato y la clave */ private CeldaHash[] tabla; /** * Constructor por defecto. Crea una nueva Tabla hash de tamaño 23 */ public TablaHash() { tabla = new CeldaHash[23]; } /** * Constructor, que crea una nueva Tabla hash de tamaño el indicado. * Si el tamaño indicado es menor de 11, crea una tabla de tamaño 11. * @param tamaño Tamaño de la tabla que se desea crear.

17

*/ public TablaHash(int tamaño) { tabla = new CeldaHash[(tamaño FACTOR_CARGA) rehash(); int hash = fHash(clave); int pos = hash; int colisión = 0; while((tabla[pos]!=null) && !tabla[pos].isBorrado()){ if(tabla[pos].getClave().equals(clave)) return false; colisión++; pos = (hash + colisión*colisión) % tabla.length; } tabla[pos] = new CeldaHash(dato, clave); numElementos++; return true; }

30

3.

TABLA HAS H ABIERTA

3.1. MODELO DE TABLA HAS H ABIERTA Como ya se ha tratado anteriormente en una Tabla Hash las posiciones de los elementos se calculan utilizando una función hash o función de dispersión que nos permite calcular directamente la posición en la que se ubican los elementos a guardar. Una estrategia para resolver el problema de las colisiones es lo que se denomina Tabla Hash abierta. Para almacenar la información se utiliza un array donde, en cada una de las posiciones del array se guarda una lista con todos los objetos que tienen el mismo hash para su clave.

En una Tabla Hash abierta todos los elementos que colisionan con el mismo valor de hash se guardan en una lista en la misma posición de la tabla.

Para ello en la definición de la clase Tabla Hash necesitamos almacenar, en cada posición de la tabla, una lista que contenga los objetos junto con su clave. Para ello utilizaremos de nuevo la clase CeldaHash que guarda esos dos valores de dato y clave para guardarlos, por ejemplo en un ArrayList. La declaración de la clase TablaHash es entonces: public class TablaHash { /** * Array donde se guardan los valores en la Tabla Hash. * Se trata de un array de objetos CeldaHash que guardan el dato, la clave * y si dicho elemento ha sido borrado. */ private ArrayList[] tabla;

31

// Elementos que contiene actualmente la tabla. private int numElementos; // Factor de carga límite en % para hacer rehash private final int FACTOR_CARGA = 100; }

Como se puede observar creamos una array de objetos ArrayList para guardar los datos. Así mismo, se mantiene la información del número de objetos insertados en la tabla y el Factor de carga a partir del cual se hace un rehash. Si el número de elementos crece demasiado, existirán cada vez más colisiones y, por tanto, empeorará el rendimiento de las operaciones. En la Figura 7 puede observar cómo queda la tabla después de insertar unos valores del ejemplo que se ha utilizado durante el capítulo. 0 1

34

56

47

69

12

2 3 4 5 6 7 8 9 10

Figura7: Tabla Hash abierta.

3.2. IMPLEMENTACIÓN DEL TIPO TABLA HASH ABIERTA Para la implementación de la tabla hash abierta hay que tener en cuenta en las operaciones principales que en las posiciones del array lo que se guarda es un ArrayList de objetos.

3.2.1. INSERCIÓN El método de insertar un objeto en la tabla será de la siguiente forma:

32

public boolean insertar(E dato, K clave){ // No se admite dato ni clave nulos if(dato == null || clave == null) return false; // solo se inserta si no está ya en la tabla. if(buscar(clave) != null) return false; if((numElementos + 1)*100/tabla.length > FACTOR_CARGA) rehash(); int pos = fHash(clave); if(tabla[pos] == null){ tabla[pos] = new ArrayList(); } tabla[pos].add(new CeldaHash(dato, clave)); numElementos++; return true; }

En este código se puede ver que lo primero que se hace es comprobar que la clave no se encuentra ya en la tabla. En caso contrario no se insertará el dato dado. A continuación se comprueba si ya hay demasiados elementos y resulta conveniente ampliar el tamaño de la tabla. Aunque en este caso el factor de carga no es tan limitante como en el caso de la Tabla Hash cerrada con resolución cuadrática de colisiones, se recomienda que el factor de carga no supere el 100%. Es decir, que en la tabla no haya más elementos que el tamaño de la tabla. Al insertar el elemento se hace añadiéndolo a la lista que ya exista en la posición del array donde le corresponde. Si en dicha posición del array no hay ningún ArrayList hay que crear uno antes.

3.2.2. BÚSQUEDA El método de búsqueda se puede escribir de la siguiente forma: public E buscar(K clave){ if(clave == null) return null; int pos = fHash(clave); if(tabla[pos] == null){ return null; } // se recorre el ArrayList, que será pequeño. for(CeldaHash celda: tabla[pos]){ if(celda.getClave().equals(clave)){ return celda.getDato();

33

} } return null; }

En el método de búsqueda la función hash devuelve la posición de la tabla donde debe encontrarse la clave. Si existe un ArrayList en dicha posición hay que recorrerlo para comprobar si existe. Para ello se utiliza un recorrido lineal. Esto es así porque se espera que el tamaño del ArrayList será muy pequeño. Se puede demostrar que en media el tamaño del ArrayList será de 1 + factorcarga/2 nodos.

3.2.3. BORRADO El método de borrado se puede escribir como: public boolean borrar(K clave){ if(clave == null) return false; int pos = fHash(clave); if(tabla[pos] == null){ return false; } // se busca la celda a borrar recorriendo el ArrayList, que será pequeño. CeldaHash celdaAux = null; for(CeldaHash celda: tabla[pos]){ if(celda.getClave().equals(clave)){ celdaAux = celda; } } if(celdaAux != null){ tabla[pos].remove(celdaAux); return true; } return false; }

El método es casi igual que el de búsqueda. La diferencia es que llama al método remove() del ArrayList una vez sabe qué nodo del ArrayList hay que eliminar.

3.3. AMP LIANDO LA TABLA De la misma forma que ocurría en la TablaHash cerrada, es importante ampliar la tabla si el factor de carga supera un cierto límite de forma que no se degrade el comportamiento de las operaciones de la tabla.

34

3.3.1. IMPLEMENTACIÓN DE REHASH La implementación de rehash para la Tabla Hash abierta se puede escribir como: private void rehash(){ ArrayList tablaAntigua[] = tabla; // Se amplía la tabla al doble + 1. Sería mejor buscar el siguiente primo. tabla=new ArrayList[tabla.length * 2 + 1]; numElementos = 0; for(ArrayList array: tablaAntigua){ if(array !=null){ for(CeldaHash celda : array){ insertar(celda.getDato(), celda.getClave()); } } } }

El método de rehash crea una nueva tabla del doble de tamaño que la antigua más uno. A continuación, recorre todos los ArrayList e inserta todos los elementos en la nueva tabla.

35

4.

LA AP I DE TABLA HAS H DE J AVA

En la API estándar de Java ya existen clases que nos permiten disponer de Tablas hash en una aplicación. Las más importantes son: 

Hashtable, similar a la que hemos definido, que necesita dos objetos uno que actúa como clave (Key), y otro que es el valor guardado (Value).



HashSet, guarda los elementos utilizando la interfaz Set.



HashMap, guarda los elementos utilizando la interfaz Map.

La implementación de todos ellos utilizan una tabla Hash abierta. A continuación se verán los métodos principales de cada una de las clases.

4.1. LA CLAS E HAS HTABLE La clase Hashtable permite asociar claves a valores como las tablas Hash que se han visto en esta unidad. Al igual que hemos visto solo se pueden utilizar claves y valores que no sean nulos. Para guardar y recuperar objetos de estas claves, los objetos que se usen como claves deben implementar el método hashCode() y el método equals(). Recuerde que estos métodos ya están implementados en todos los tipos primitivos y todas las clases del sistema. En general el factor de carga que utiliza es del 75%, aunque se puede modificar. Los principales métodos son:

36



Hashtable(), constructor de una nueva tabla hash con una capacidad inicial de 11 y un factor de carga del 75%.



Hashtable(int initialCapacity), constructor de una nueva tabla hash con la capacidad inicial indicada y un factor de carga del 75%.



Hashtable(int initialCapacity, float loadFactor), constructor de una nueva tabla hash con la capacidad inicial indicada y el factor de carga indicado.



V put(K key, V value), inserta el valor y clave dadas en la tabla. Devuelve el valor anterior de la clave si existía o null si no existía.



V get(Object key), devuelve el valor asociado a la clave indicada o null si no existe.



V remove(Object key), elimina la clave y el valor correspondiente de la tabla devolviéndolo.



void clear(), elimina todos los elementos de la tabla.



int size(), devuelve el número de elementos en la tabla.

4.2. LA CLAS E HAS HS ET La clase HashSet implementa la interfaz Set utilizando una Tabla Hash. Los principales métodos son: 

HashSet(), constructor de un nuevo conjunto con una capacidad inicial de 16 y un factor de carga del 75%.



HashSet(int initialCapacity), constructor de un nuevo conjunto vacío con la capacidad inicial indicada y un factor de carga del 75%.



HashSet(int initialCapacity, float loadFactor), constructor de un nuevo conjunto vacío con la capacidad inicial indicada y el factor de carga indicado.



boolean add(E e) inserta el valor si no estaba ya en el conjunto.



boolean contains(Object o), devuelve true si el conjunto contiene el objeto indicado.



boolean remove(Object o), elimina el objeto del conjunto si existe.



void clear(), elimina todos los elementos del conjunto.



int size(), devuelve el número de elementos en el conjunto.

4.3. LA CLAS E HAS HMAP La clase HashMap es una tabla hash que implementa la interfaz Map. Es prácticamente equivalente a Hashtable, salvo que permite guardar valores nulos. Los principales métodos son: 

HashMap(), constructor de una nueva tabla hash con una capacidad inicial de 16 y un factor de carga del 75%.



HashMap(int initialCapacity), constructor de una nueva tabla hash con la capacidad inicial indicada y un factor de carga del 75%.

37

38



HashMap(int initialCapacity, float loadFactor), constructor de una nueva tabla hash con la capacidad inicial indicada y el factor de carga indicado.



V put(K key, V value), inserta el valor y clave dadas en la tabla. Si ya existía dicha asociación de clave y valor se sustituye el valor por el nuevo. Devuelve el valor antiguo si existía o null.



V get(Object key), devuelve el valor asociado a la clave indicada o null si no existe.



V remove(Object key), elimina la clave y el valor correspondiente de la tabla, devolviéndolo.



void clear(), elimina todos los elementos de la tabla.



int size(), devuelve el número de elementos en la tabla.

CONCLUS IONES En este tema se ha visto cómo funciona la estructura de datos Tabla Hash y lo importante que puede ser para gestionar eficazmente información de gran tamaño. Se han visto dos tipos de alternativas, las Tablas Hash cerradas y las tablas Hash abiertas, y la implementación de ambas, viendo las formas de tratar con los distintos problemas que surgen y cómo utilizarlas de forma apropiada. Así mismo se ha visto cómo utilizar la Tabla Hash que ya viene definida en la API de Java.

39

RECAPITULACIÓN En las Tablas Hash debe tener en cuenta los siguientes puntos principales: 

A qué se denomina función hash y qué papel cumple en las tablas hash.



Las características de una Tabla Hash y la complejidad de las operaciones sobre la tabla.



La función hash y cómo calcularla para tener en cuenta el tipo de dato de la clave.



A qué se denomina una función hash ideal.



Qué es una colisión y los modelos de resolución.



Cómo funciona una Tabla Hash cerrada.  Conocer las estrategias de resolución de colisiones para una Tabla Hash cerrada. 

Qué es el factor de carga y cómo establecerlo dependiendo del tipo de Tabla Hash utilizada.



Cómo afecta el factor de carga a la ejecución de las operaciones sobre la Tabla Hash.



Qué es la operación de rehash.  Conocer las estrategias de resolución de colisiones para una Tabla Hash abierta. 

40

Conocer la API HashTable de Java.

AUTOCOMPROBACIÓN 1.

Si una operación se dice que tiene complejidad constante O(1) significa que a) Siempre tarda lo mismo independientemente del problema b) Siempre tarda un tiempo T cuando el problema está dentro de unos límites c) El tiempo de ejecución está acotado. d) Se sabe lo que tardará antes de empezar a ejecutarse.

2.

Una Tabla Hash tiene una complejidad para su operación de eliminar un elemento de a) O(1) b) O(NlogN) c) O(N) d) O(N2)

3.

¿A qué se denomina función hash? a) A una función que dice la clave del objeto b) A una función que calcula un valor del objeto para obtener su posición en la tabla. c) A una función que indica si el objeto se encuentra en la Tabla. d) A un resumen del objeto para comprobar coincidencias.

4.

¿Qué tipos de objetos se pueden guardar en una Tabla Hash? a) Solo tipos primitivos. b) Solo objetos que no sean valores primitivos. c) Cualquier objeto que implemente la interfaz Hashable. d) Cualquier objeto sin restricciones.

41

5.

En una Tabla Hash abierta: a) Inserta los elementos en un árbol que representa la relación entre objeto y clave. b) Inserta los elementos en un array que representa la relación entre objeto y clave. c) Inserta los elementos en las posiciones del array, un elemento en cada celda del array. d) Inserta los elementos en una lista de elementos para cada celda del array.

6.

Cuando se utiliza una Tabla Hash cerrada, en la resolución lineal de colisiones: a) Se busca la siguiente posición libre empezando desde el principio de la tabla. b) Se busca la siguiente posición libre empezando desde donde se produjo la colisión. c) Se busca la siguiente posición libre empezando desde la última posición de la tabla hacia el comienzo. d) Se rechaza linealmente la inserción del objeto.

7.

En una Tabla Hash cerrada, al borrar un elemento de la Tabla. a) Se elimina el elemento poniendo su celda a null. b) Se elimina el elemento poniendo en su celda un elemento especial sin valor. c) Se elimina el elemento simplemente descontando uno del número de valores de la tabla. d) Se elimina el elemento poniendo un atributo a true para marcar que dicho elemento fue borrado.

8.

Se denomina factor de carga de una Tabla Hash a: a) Un factor que determina lo costoso que es insertar un elemento en la tabla. b) Un factor que es la razón entre la capacidad de la tabla y el número de elementos no nulos de la tabla. c) Un factor que indica la razón entre el número de colisiones producidas durante la inserción de elementos y el número de elementos insertados. d) Un factor que es la razón entre el número de elementos de la tabla y su capacidad.

42

9.

La clase Hashtable, tiene un método V put(K key, V value): a) Utiliza una clave y un valor para asociarlos insertándolos en la tabla. Ninguno de los dos puede ser nulo. Devuelve el valor que tuviese anteriormente dicha clave o null. b) Utiliza una clave y un valor para asociarlos insertándolos en la tabla. Solo el valor puede ser nulo. Devuelve el valor que tuviese anteriormente dicha clave o null. c) Utiliza una clave y un valor para asociarlos insertándolos en la tabla. Cualquiera de los dos puede ser nulo. Devuelve el valor que tuviese anteriormente dicha clave o null. d) Utiliza una clave y un valor para asociarlos insertándolos en la tabla. Ninguno de los dos puede ser nulo. Devuelve null si la clave está repetida.

10. Para obtener un elemento de un HashSet: a) Se recorre el HashSet con un iterador. b) Utilizando la clave del elemento y la función de hash correspondiente. c) Utilizando el hashcode() del objeto y la tabla de hash asociada. d) Recorriendo las claves del HashSet hasta encontrar la buscada.

43

S OLUCIONARIO 1.

c

2.

a

3.

b

4.

d

5.

d

6.

b

7.

d

8.

c

9.

a

10.

a

45

PROPUESTAS DE AMPLIACIÓN Algo muy interesante que puede hacer es ejecutar el código de las tablas hash con ejemplos para ver cómo se van insertando, buscando y borrando elementos de las tablas hash e intentar entender su funcionamiento. Puede consultar los libros de la bibliografía para obtener más detalles sobre las Tablas Hash y algunos aspectos avanzados no contemplados.

46

BIBLIOGRAFÍA 

Mark Allen Weiss. Capítulo 5 de Data Structures and Algorithm Analysis in Java. Tercera edición. Pearson, 2012.



Luis Joyanes Aguilar y Ignacio Zahonero Martínez. Capítulo 12 de Estructuras de datos en Java. McGraw-Hill, 2008

47