• Author / Uploaded
• Charly Dominguez

Citation preview

Módulo 3 Lectura 3 Unidad 3: Tablas de Hash

Materia: Taller de Algoritmos y estructura de Datos II Profesor: Paula Abruzzini / Nicolas Frontini

Introducción El objetivo de esta unidad es realizar una introducción a una estructura de datos muy utilizada como son las tablas de hashing. En esta unidad se presentaran los conceptos esenciales para comprender su funcionamiento lo que nos permitirá realizar nuestra propia implementación en Java de las mismas. Además, analizaremos distintos ejemplos y evaluaremos los costos de cada una de las operaciones. Finalmente, realizaremos un breve análisis de la implementación de tablas de hashing propia de Java.

3.1 Conceptos básicos Las tablas de hashing son una estructura de datos tipo diccionario que nos permite insertar, eliminar y buscar elementos a partir de una clave. Esta estructura se puede ver como un conjunto de entradas, donde cada una de ellas tiene asociada una clave única. Esto significa que una clave identifica unívocamente a una entrada en la tabla de hash. Las entradas de la tabla contienen 2 componentes: La clave La información que se almacena en esa entrada

¨La tabla de hash se emplea para implementar un diccionario en el que cada operación se ejecuta en tiempo constante¨. (Mark Weiss, 2000, 527) 1

1

Estructura de Datos en Java, Mark Weiss, Addison Wesley, 2000, capítulo 19

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |2

En la Figura 1 y la Figura 2 podemos ver un ejemplo de tabla de hashing donde en cada una de las entradas de la tabla se guarda un elemento “Persona” y la clave para cada elemento esta dado por su DNI.

Figura 1: Mapeo de claves y elementos

Figura 2: Tabla de Hash con sus elementos

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |3

Entre las características que poseen estas estructuras de datos, se pueden destacar las siguientes: Esta estructura soporta las operaciones de un diccionario: ¨Insertar¨, “Borrar” y “Buscar”. Suele implementarse con vectores de una dimensión En el peor caso, las tablas de hashing pueden tener un costo O (n) para realizar una búsqueda, pero el tiempo esperado para esta operación es constante O(1). La teoría de las tablas de hashing se basa en probabilidades.

Algunas definiciones que vamos a utilizar a lo largo del modulo: Capacidad: La capacidad establece el tamaño inicial del vector de elementos. Factor de carga: El factor de carga de una tabla hash es la fracción ocupada. Este valor se encuentra entre 0 y 1, donde 0 indica tabla vacía y el 1 que se encuentra llena. Función de Hash: Una función de hash, nos permite transformar un rango de valores de claves en un rango de índices de un vector. En el ejemplo de la Figura 1, la función de hash transforma un DNI a un índice dentro del vector. Re-hash: Cuando una tabla de hash se encuentra muy cargada podemos expandir el tamaño del vector. Los elementos existentes en el vector original deben ser reubicados en el nuevo vector, dado que al tener un vector de tamaño mayor, los elementos serán ubicados en una distinta posición. Este proceso es conocido como re-hashing. Colisiones: Al insertar un elemento en una tabla de hash calculamos su función de hash para identificar la posición en la que se va a ubicar el elemento. Cuando esta posición se encuentra ocupada decimos que se produjo una “colisión” y necesitamos encontrar una nueva posición donde insertar el elemento que nos permita poder encontrarlo cuando se requiera. Hash Cerrado: Cuando ocurre una colisión, podemos buscar de manera metódica una nueva posición vacía donde insertar el elemento en lugar de usar la posición generada por la función de hashing. Esta técnica es llamada direccionamiento abierto o hash cerrado. Hash Abierto: Otra técnica que se puede aplicar cuando ocurre una colisión, consiste en crear una lista para cada posición del vector. De esta manera cuando se produce una colisión simplemente se agrega el elemento a la lista. Esta técnica es llamada direccionamiento cerrado o hash abierto.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |4

3.2 Análisis de Tablas de Hash ¿Qué tamaño debería tener el vector en el ejemplo de la Figura 1?

Si representamos la tabla de hash con una estructura de acceso directo como un vector, necesitamos definir la cantidad de elementos o capacidad. Es decir, necesitamos crear una estructura para el ejemplo de la Figura 1 que contenga tantos elementos como números de documentos podríamos almacenar. Además, debe existir una función inyectiva que permita mapear para un DNI un índice de la tabla. Si bien, esta implementación es óptima en cuanto a los costos de tiempo para las operaciones de inserción, eliminación y búsqueda; tenemos las siguientes desventajas:

El tamaño del vector puede ser muy grande resultando imposible su implementación. La complejidad de encontrar una función inyectiva para codificar

Según Mark Weiss en su libro Estructura de Datos en Java, para evitar estos problemas se busca una función que transforma estas claves complejas a números manejables. La función que permite realizar este mapeo se conoce como función hash. “Uno función hash convierte un elemento en un entero adecuado para indexar el vector en el que el elemento es almacenado. Si la función hash fuese inyectiva, podríamos acceder al elemento mediante su índice. Como la función hash no es inyectiva, se producirá lo colisión de muchos elementos potenciales en el mismo índice.” (Mark Weiss, 2000, 528)

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |5

Funciones de hash En esta sección vamos a analizar que hace a una buena función de hash y revisar algunas implementaciones. Tenga en cuenta que una buena función de hash es imprescindible para el buen rendimiento de la tabla. Podemos resumir las ideas que plantea el autor Robert Lafore en su libro, Data Structures and Algorithms in Java: Cálculo rápido: Una buena función hash es simple, por lo que se puede calcular rápidamente. La principal ventaja de las tablas de hash es su velocidad. Si la función hash es lenta, esta velocidad será degradada. El propósito de una función hash es tomar una serie de valores y transformarlos en los valores de índice, de tal manera que los valores de clave están distribuidos al azar a través de todos los índices de la tabla hash. Las claves pueden ser totalmente aleatorias o no. Claves aleatorias: Llamamos a una función de hash “perfecta” si se mapea cada clave en una ubicación de tabla diferente. En la mayoría de los casos no existe esta situación, ya que la función de hash va a necesitar comprimir una gama más amplia de claves en un rango menor de números de índice que coincide con el rango del arreglo. Para lograr esto aplicamos el modulo a la función de hash para que de un valor dentro de ese rango: índice =indice% arraySize Se trata de una sola operación matemática, y si las claves son realmente aleatorias, los índices resultantes serán aleatorios, y por lo tanto bien distribuidas. Claves no Aleatorias: En este caso los datos se distribuyen de manera no aleatoria. Imagínese que se usan como clave los números de autopartes. Estos números van a tener un formato particular, por ejemplo: 033-40003-94-05-0-535 donde cada uno de los valores tiene una interpretación y un rango de valores posibles para cada uno. Por ejemplo, el 033 es un valor que representa una categoría cuyo valor posible es de 000 a 050. Estas claves no están distribuidas al azar. Usar un número primo para el modulo: Generalmente, la función de hash implica el uso del operador de módulo (%) con el tamaño de la tabla. Además como veremos en la próxima sección, es importante que el tamaño de la tabla sea un número primo cuando utilizamos resolución de colisiones por exploración lineal o cuadrática. Sin embargo, si las claves no se distribuyen de manera aleatoria, es importante que el tamaño de la tabla de defina con un número primo independientemente del tipo de función de hashing que se utilice. Esto es así dado que si muchas claves comparten como divisor el tamaño del arreglo, puede tender a ubicar los elementos en la misma ubicación, causando la agrupación. Usando un número primo como tamaño de la tabla se elimina esta posibilidad.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |6

3.3 Exploración lineal y Cuadrática Al insertar un elemento en una tabla de hash calculamos su función de hash para identificar la posición en la que se va a ubicar el elemento. Cuando esta posición se encuentra ocupada decimos que se produjo una “colisión” y necesitamos encontrar una nueva posición donde insertar el elemento que nos permita poder encontrarlo cuando se requiera. Las técnicas más utilizadas para la resolución de colisiones son direccionamiento abierto (Hashing cerrado) y direccionamiento cerrado (Hashing abierto).

Direccionamiento cerrado (Hashing abierto) La técnica de direccionamiento cerrado, también conocido como Hashing abierto resuelve las colisiones implementando para cada posición de la tabla una lista de elementos. Cuando se calcula el valor de hashing y se ubica el elemento en una posición vacía se inserta y si la posición está ocupada simplemente se agrega en la lista. En el caso de colisión no necesitamos buscar una celda vacía. Esta técnica es más simple que la de Hashing cerrado dado que no necesita reubicar los elementos que colisionan. La siguiente Figura muestra un ejemplo de Hashing abierto.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |7

Figura 3 - Fuente: Libro “Data Structures and Algorithms in Java” – Robert Lafore, pág. 552.

Direccionamiento abierto (Hashing cerrado) En la lectura anterior vimos que al producirse una colisión se resuelve insertando el elemento en la misma posición en una lista enlazada. En el direccionamiento abierto o Hashing cerrado, al producirse una colisión necesitamos reubicar el elemento en otra posición del arreglo. Analizaremos 2 técnicas de Hashing cerrado para la resolución de colisiones: Exploración lineal Exploración cuadrática

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |8

Representación grafica: Hash Abierto

Representación grafica: Hash Cerrado

Fuen te: Representación grafica de Hashing abierto y cerrado 2

2

Tablas HASH Franco Sánchez Huertas, Víctor Arroyo Apaza. Algoritmos y Estructura de Datos Arequipa – Perú UCSP – 2008

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini |9

Resolución de colisiones: Exploración lineal Esta técnica es la más sencilla para la resolución de colisiones. Consiste en buscar secuencialmente en el vector hasta encontrar una posición vacía. Un ejemplo de esta técnica se muestra en la Figura 4, resultado de la inserción de los siguientes elementos: 1. 2. 3. 4. 5.

hash(89, 10) = 9 hash( 18, 10) = 8 hash(49, 10) = 9 hash( 58, 10 ) = 8 hash( 9, 10) =9

Pasos de ejecución: Paso 1: Elemento a insertar = 89 Función de hash: hash(89, 10) = 9 Se asigna la posición 9, como esta posición está libre se guarda el elemento en esa posición. Paso 2: Elemento a insertar = 18 Función de hash: hash(18, 10) = 8 Se asigna la posición 9, como esta posición está libre se guarda el elemento en esa posición. Paso 3: Elemento a insertar = 49 Función de hash: hash(49, 10) = 9 Se asigna la posición 9, la inserción de este elemento produce una colisión. Al estar ocupada se busca linealmente la próxima posición libre. Finalmente el elemento se ubica en la posición 0. Paso 4: Elemento a insertar = 58 Función de hash: hash(58, 10) = 8 Se asigna la posición 8, al estar ocupada se busca linealmente la próxima posición libre resolviendo la colisión. Finalmente el elemento se ubica en la posición 1. Paso 5: Elemento a insertar = 9 Función de hash: hash(9, 10) = 9 Se asigna la posición 9, al estar ocupada se busca linealmente la próxima posición libre resolviendo la colisión. Finalmente el elemento se ubica en la posición 2.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 10

Figura 4 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley, pag, 531

“Siempre que la tabla sea suficientemente grande, podremos encontrar una casilla vacía. Sin embargo, el tiempo que se emplea en buscarla puede ser bastante elevado. Por ejemplo, si existe una sola casilla vacía en el vector, es posible que tengamos que examinar la tabla entera hasta llegar a ella. En media, podemos esperar tener que buscar en la mitad de la tabla hasta encontrar una casilla vacía. Esto está muy lejos del tiempo constante por acceso que deseamos. En contraposición, si suponemos que la tabla se va a mantener relativamente vacía, entonces las inserciones no serán tan costosas. Todo esto se discutirá en breve. El algoritmo buscar sigue exactamente el mismo camino que el algoritmo insertar. Si llega a una casilla vacía, el elemento que estamos buscando no se encuentra en la tabla; en caso contrario, lo encontraremos. Por ejemplo, para encontrar 58, empezamos en la casilla 8 (tal y como indica la función hash). Aquí encontramos un elemento, pero como no es el buscado, pasamos a examinar la posición 0 y después la l, hasta que lo encontramos. Si realizamos buscar con 19, se examinarían las casillas 9, O, l y 2 antes de encontrar una celda vacía en la posición 3. Concluimos que no hemos encontrado 19. La eliminación estándar no puede aplicarse, ya que al igual que sucede en los árboles binarios de búsqueda, un elemento de la tabla hash no sólo se representa así mismo, sino que conecta otros elementos haciendo de posición ocupada durante la resolución de conflictos. Así, si eliminamos 89 de la tabla hash, prácticamente todas las operaciones buscar posteriores fallarán. Como consecuencia, se implementa la eliminación perezosa, marcando los elementos como borrados de la tabla. Esta información se

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 11

almacena en un atributo adicional. Cada elemento está activo o borrado.” (Mark Weiss, 2000, 532)3

2

Resolución de colisiones: Exploración cuadrática El problema de la técnica anterior es que puede generar aglomeración de datos, es decir los elementos tienden a agruparse alrededor de las claves que no tienen colisión. Una técnica que soluciona este problema es la técnica de exploración cuadrática. Esta consiste en utilizar la siguiente fórmula para la resolución de conflictos. F(i)= i2 Esto significa que si al calcular la función de hash para una clave obtenemos el valor H. Si la posición H se encuentra ocupada intenta resolver la colisión re posicionando el valor en H + 12, luego en H + 22 , luego en H + 32 y asi sucesivamente hasta encontrar una posición vacía. Veamos nuevamente el ejemplo analizado con exploración lineal de la Figura 3 solucionando las colisiones a partir de la exploración cuadrática. Suponemos la inserción de los elementos: 1. 2. 3. 4. 5.

hash(89, 10) = 9 hash( 18, 10) = 8 hash(49, 10) = 9 hash( 58, 10 ) = 8 hash( 9, 10) =9

En la Figura 5 se muestra el estado de la tabla en cada uno de los pasos:

3

Estructura de Datos en Java, Mark Weiss, Addison Wesley, 2000, capítulo 19

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 12

Figura 5 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley, pag, 531

Pasos de ejecución: Paso 1: Elemento a insertar = 89 Función de hash: hash(89, 10) = 9 Se asigna la posición 9, como esta posición está libre se guarda el elemento en esa posición. Paso 2: Elemento a insertar = 18 Función de hash: hash(18, 10) = 8 Se asigna la posición 9, como esta posición está libre se guarda el elemento en esa posición. Paso 3: Elemento a insertar = 49 Función de hash: hash(49, 10) = 9 Se asigna la posición 9, la inserción de este elemento produce una colisión. Al estar ocupada se busca la próxima posición de acuerdo a la función cuadrática dando como resultado 9 + 12 = 10. Como la tabla tiene 10 elementos numerados del 0 al 9, el valor 10 corresponde a la posición 0 del vector que se encuentra vacío. Paso 4: Elemento a insertar = 58 Función de hash: hash(58, 10) = 8 Se asigna la posición 8, al estar ocupada se busca la próxima posición de acuerdo a la función cuadrática dando como resultado 8 + 12= 9. Como la posición 9 se encuentra ocupada se vuelve a calcular el próximo valor 8 + 22 =12. Este elemento corresponde a la posición 2 del vector que se encuentra disponible para su uso. Paso 5: Elemento a insertar = 9 Función de hash: hash(9, 10) = 9 Se asigna la posición 9, al estar ocupada se busca la próxima posición de acuerdo a la función cuadrática dando como resultado 9

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 13

+ 12= 10. Como la posición 0 se encuentra ocupada se vuelve a calcular el próximo valor 9 + 22 =13. Este elemento corresponde a la posición 3 del vector que se encuentra disponible para su uso.

Ventajas y Desventajas Ventajas y Desventajas del uso de tablas de hash: Ventajas: acceso rápido a los datos. Si se cumplen algunas características el acceso a los datos es muy rápido. Estas características están relacionadas con el factor de carga, es decir, si el factor de carga aumenta de un 75% tendremos una mayor cantidad de colisiones. La otra característica depende de la función de hash que genere una distribución uniforme de las claves. Si la función genera muchas colisiones la tabla se vuelve ineficiente. Desventajas: Costo de la función de hash. Si bien las operaciones de búsqueda e inserción tienen un costo constante, el costo de una buena función de hashing puede ser significativo. Desventajas: Costo al de re-hashing. Si la cantidad de elemento crece de tal forma que se necesite extender el tamaño de la tabla, la operación de re-hash tiene un costo alto dado que todos los elementos existentes deben ser reubicados en la nueva tabla. Desventajas: Colisiones. Las tablas se vuelven ineficientes si se producen muchas colisiones.

3.4- Implementaciones Utilizando todos los conceptos analizados en las secciones anteriores realizaremos nuestra implementación de tablas de hashing en Java. Para la implementación de tablas de hash definiremos interfaces y utilizaremos el concepto de herencia definiendo una clase abstracta que será la principal clase para la implementación de las tablas de hash. L uego, extenderemos dicha clase dependiendo la técnica de resolución de conflictos escogida. En este caso realizaremos la implementación codificando un método de resolución de conflictos mediante exploración cuadrática.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 14

Clases e Interfaces Para la implementación de esta estructura de datos crearemos: Interface TablaHash: Nos va a definir los métodos que deben definirse en las implementaciones de las tablas de hash que van a implementar dicha interface. Clase abstracta ExploracionTablaHash: Esta clase contiene la tabla en sí y la implementación de las operaciones. Va a implementar la interface TablaHash. En esta clase definiremos como método abstracto, aquel método asociado a la técnica de resolución de conflictos. Es decir, la clase no conoce como se resuelven los conflictos. Clase TablaExploracionCuadratica: Esta clase extiende la clase abstracta ExploracionTablaHash definiendo el método para resolución de colisiones de acuerdo a la resolución mediante Exploración Cuadrática. Clase TablaExploracionLinear: Esta clase extiende la clase abstracta ExploracionTablaHash definiendo el método para resolución de colisiones de acuerdo a la resolución mediante Exploración Lineal. Interface Hashable: Nos va a definir los métodos que deben implementarse para cada elemento que voy a guardar en la tabla de Hash. Clase EntradaHash: Define una clase donde se guardara el elemento de tipo Hashable y un atributo que indica si se encuentra borrado (dado que vamos a realizar un borrado lógico de los datos de la tabla). En la siguiente figura se muestra las clases, interfaces y sus relaciones mediante un diagrama de clases.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 15

Figura 6 - Diagrama de Clases para la implementación de Tablas de Hash

Representación Para la representación de la tabla guardaremos 2 variables en la clase ExploracionTablaHash: Para simplificar su complejidad no vamos a incluir la función de rehashing. En caso que se quiera implementar deberíamos definir en esta clase la variable factor de carga involucrada en el proceso de re-hash.

Utilizaremos un vector donde guardaremos cada uno de los elementos. Estos elementos serán del tipo Hashable. Una variable entera (int) donde almacenaremos la cantidad de elementos guardados en la tabla.

Interfaces Primero vamos a crear la interface TablaHash dentro de la cual definiremos 4 métodos: void insertar( x ): Inserta un elemento x en la tabla de hash void remover( x ): Remueve un elemento x de la tabla de hash Hashable buscar( x ): Retorna el elemento que coincide con x void vaciar( ): Remueve todos los elementos de la tabla

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 16

Algunas aclaraciones para su implementación: Para las operaciones de búsqueda y remoción si el elemento no se encuentra se mostrara el mensaje “Elemento no encontrado” La operación de inserción sobrescribe el elemento si ya se encuentra en la tabla.

De acuerdo a la definición descripta anteriormente la implementación de la interface TablaHash se muestra a continuación:

Figura 7 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Luego crearemos la interface Hashable. Esta interface solo va a definir el método hash que va a ser calculado de acuerdo al tamaño de la tabla. Todos los objetos que se quieran guardar en la tabla de Hash deberían implementar la interface Hashable y redefinir el método hash(). En la siguiente figura se muestra el código para la interface Hashable.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 17

Figura 8 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Clase Abstracta ExploracionTablaHash Ahora, ya estamos en condiciones de crear la clase abstracta “ExploracionTablaHash”. Es una clase abstracta que debe ser extendida para implementar un algoritmo de exploración concreto, como por ejemplo, exploración cuadrática. El objetivo de esta clase es guardar las variables y definir los métodos necesarios para la operación de la tabla. La tabla de datos será implementada con un vector para permitirnos tener un acceso directo a los datos, como así también guardaremos la cantidad de elementos almacenados en la estructura que será implementado con una variable entera. Finalmente dejaremos abstracto el método que busca las posiciones donde insertar, buscar y eliminar que dependerá del algoritmo seleccionado para resolver colisiones. En la Figura 9 se muestra las variables y constructores de la clase. Note que la clase implementa la interface TablaHash, definida en la Figura 7.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 18

Figura 9 - Fuente: Libro “Ingeniería del Software” – Roger Pressman, pág. 55.

Una vez construida la clase, estamos preparados para la implementación de los métodos de inserción, eliminación y búsqueda. Método insertar: recibe como parámetro un objeto de tipo Hashable para ser insertado en la tabla. La responsabilidad de encontrar la posición a donde insertar el valor se la atribuye al método buscarPos.

Figura 10 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Método eliminar: recibe como parámetro un objeto de tipo Hashable para ser eliminado de la tabla. La responsabilidad de encontrar la posición donde se encuentra el valor se la atribuye al método buscarPos.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 19

Una vez que sabemos dónde buscar el valor, accedemos a posición y borramos lógicamente la entrada estableciendo Activo en false. La llamada al método confirmaBuscar, simplemente llama un método que imprime por pantalla un mensaje confirmando que se va a eliminar el elemento o que no se encontró en la tabla.

Figura 11 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Método buscar: recibe como parámetro una clave y retorna el elemento correspondiente a ese valor. Como en los métodos anteriores, el método buscarPos es el responsable de encontrar la posición donde se encuentra el elemento para luego recuperarlo y ser el valor de retorno de este método.

Figura 12 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Finalmente, vamos a definir el método buscarPos. Este método va a ser definido como abstracto dado que la posición a insertar, eliminar y buscar un elemento dependerá de la manera en que se van a tratar las colisiones. Declaramos el método abstracto para ser implentado mas tarde en la clase correspondiente. Este método recibe una clave y retorna la posición donde se encuentra el elemento con dicha clave guardado en la estructura de datos.

Figura 13 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 20

Clase TablaExploracionCuadratica En esta sección estudiaremos la implementación de la clase TablaExploracionCuadratica que extiende la clase abstracta ExploracionTablaHash. Como se pude observar de la Figura 14, dependiendo de la resolución de conflicto elegida se creara la clase correspondiente extendiendo de la clase ExploracionTablaHash y se redefinirá el método buscarPos.

Figura 14 – Jerarquía para la clase ExploracionTablaHash

Como vemos en la Figura 14, se define la clase TablaExploracionCuadratica que extiende de la clase abstracta que extiende de l la clase ExploracionTablaHash. Esta clase necesita definir el método buscarPos. En la figura podemos observar la implementación de este método. El objetivo es encontrar la posición que corresponde para dicho elemento de acuerdo a su función de hash. Una vez que tenemos el valor, validamos que no se produzcan colisiones, es decir que la posición no se encuentre ocupada por otro elemento. Si la posición está ocupada se buscara una nueva posición de acuerdo a la función cuadrática. Es decir, valor de hash + 12, luego se prueba con valor de hash + 22, valor de hash + 32, valor de hash + i2 y así sucesivamente hasta encontrar una posición vacía.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 21

La segunda sentencia del iterador while, valida si el elemento ya se encuentra en la tabla.

Figura 15 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Clase Entrada de Hash Finalmente, vamos a revisar la clase EntradaHash. Esta clase define el elemento que va a ser guardado en la tabla que es de tipo Hashable y un booleano que establece si el elemento esta activo o no lo que nos permite un borrado lógico de los datos. En la siguiente figura, se muestra el código de esta clase.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 22

Figura 16 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Interface Hashable Para completar la implementación de la estructura de datos vamos a definir la interface Hashable. Esta interface define que debe implementarse el método hash para cada objeto que .la implemente. En la siguiente figura vemos el código de la interface

Figura 17 - Fuente: Libro “Estructura de Datos en Java” - Mark Weiss, Addison Wesley

Una vez creada la interface, estamos listos para crear nuestros objetos y almacenarlos en la tabla de Hash.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 23

Un ejemplo de implementación de la interface Hashable se muestra en la figura. Esta clase Persona implementa el método hash, retornando un valor entero. Podemos definir el método hash como la suma de elementos del DNI.

Figura 18 –Implementación de la clase Persona

Otro ejemplo, puede ser la implementación de la clase MyInteger, haciendo una definición del método hash

Figura 19 –Implementación de la clase MyInteger

Tablas de Hash en el paquete Java.utils Veamos la implementación que nos trae Java de las Tablas de Hash. En el siguiente ejemplo se muestra la utilización de las tablas de hash del paquete java.utils. Supongamos que tenemos una lista de clientes de un negocio con un saldo a favor para gastar en el local. Analicemos que pasa en cada uno de los pasos.

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 24

Figura 20 –Código ejemplo utilizando hashtables del paquete java.utils

Línea 12: creación de la tabla de Hash saldo. Línea 13: creación de la tabla de Hash saldo2. La diferencia con la línea anterior es que la tabla se encuentra parametrizada con los tipos de datos que voy a guardar como Clave y Valor. En este caso la Clave será de tipo String y el Valor de tipo Double. Línea 19-22: inserta en la tabla de hash los valores persona, saldo como clave, valor. (Método put) Línea 26: Obtiene una enumeración con todos los nombres de personal (o claves de la tabla de hash para su recorrido. (Método keys) Línea 27-28: Ciclo para iterar sobre el enumerado obtenido en la línea 26. Línea 29: Obtiene el valor almacenado en la tabla de acuerdo a la clave que se pasa como parámetro, en este caso un nombre. (Método get) Línea 32: Verifica si la clave se encuentra almacenada en la tabla y retorna verdadero o falso. (Método containskey)

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 25

Bibliografía Lectura 3 Capítulo: 19 Mark Weiss (2000), “Estructura de Datos en Java”, Editorial Addison Wesley Iberoamericana. Capítulo: 11

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001), “Introduction to Algorithms, Second Edition”, McGraw-Hill Book Company Capítulo: 11

Robert Lafore (2002), “Data Structures & Algorithms in Java (2nd Edition)”, SAMS. Código Fuente Mark Weiss Home Page: http://users.cis.fiu.edu/~weiss/

Taller de Algoritmos y Estructura de Datos II – Profesor Paula Abruzzini / Nicolas Frontini | 26