Tabla hash

Universidad Nacional De Asunción

Facultad Politécnica

Trabajo Practico Final

Materia: Estructura de datos. Profesor: Derlis Zarate.

Tema: Tabla Hash.

Alumno: Francisco Misael Brusquetti Aquino. CI: 4.912.113

Carrera: Licenciatura en ciencias informáticas. Sección: NB.

1

Contenido

INTRODUCCIÓN        3

Objetivo General        3

Objetivos específicos        3

RESUMEN        3

CONTENIDO        4

TABLA HASH        4

EXPLICACIÓN DEL ALGORITMO DE PRUEBA        9

TABLA DE RESULTADOS        10

CONCLUSIÓN        11

Bibliografia        12

INTRODUCCIÓN:

Las estructuras de datos le permiten a los programadores resolver problemas con ciertas características,dependiendo de el problema que se busca resolver algunas estructuras de datos nos dan facilidades para la resolución del problema,por las propiedades que estos poseen. Con este trabajo se busca conocer una nueva estructura de datos que no se incluyo en los laboratorios desarrollados,llamada Tabla Hash o hash table,que lo que busca es que sus operaciones de inserción,búsqueda y eliminación se acerquen a un costo asintótico constante. Algo sumamente interesante. Pues busca romper la barrera de recorrer la lista en forma lineal,y en cambio busca hacerlo de forma directa.

Al final del trabajo se busca lograr los siguientes objetivos:

Objetivo General:

• Lograr interpretar y entender el funcionamiento e implementación de una estructura de datos nueva por cuenta propia.

Objetivos específicos:

• Conocer las ventajas y características de una tabla hash.
• Conocer la lógica de sus funciones elementales.
• Ser capaz de identificar en que caso conviene el uso de esta estructura de datos.

RESUMEN:

Con este trabajo profundizamos la estructura de datos llamada tabla hash que busca lograr la inserción,búsqueda y eliminación en tiempo constante utilizando la función hash para convertir la clave en una llave que indica la posible posición que ocupara dentro de ella,para acceder directamente cuando se desee,utilizando técnicas de dispersión para evitar colisiones,lo que la hace una estructura de acceso muy rápido si se implementa correctamente.

CONTENIDO

TABLA HASH:

Una tabla hash, matriz asociativa, mapa hash, tabla de dispersión o tabla fragmentada es una estructura de datos que asocia llaves o claves con valores. Es una estructura de datos que busca encontrar,eliminar e insertar elementos en una tabla con un costo asintótico medio de O(1) es decir constante,almacenando las claves en una posición resultante de pasar la misma clave por una función hash(),que transforma la clave en una llave de valor numérico, que indica su posición a ocupar en la tabla,la función hash mas conocida es la del modulo (k%N).Cuando dos o mas claves tienen el mismo valor hash,se genera lo que se llama colisión. Existen varias formas de solucionar este problema,entre ellos esta la implementación de listas enlazadas,en la cual cada posición del vector es una lista enlazada,de manera que si dos o mas claves tienen el mismo valor hash al insertarse simplemente se añaden a la lista de esa posición. Otra técnica utilizada es la llamada dispersión lineal que consiste en ir sumando una unidad al valor hash obtenido hasta que se encuentra una posición vacía. Otra técnica de dispersión es la cuadrática,que suma el cuadrado de una constante al valor hash que lo que indica es el índice de la tabla o vector. Si en cada salto que de la posición no esta vacía la constante ira incrementándose en una unidad. Si aun no se encontró una posición libre y el índice ya es mayor al tamaño de la tabla se vuelve a empezar desde la primera posición hasta la posición donde se empezó a buscar por primera vez -1. Si aun así no se encontró un lugar vacío el elemento ya no se puede insertar. La principal desventaja que posee la dispersión cuadrática frente a la lineal es que si la tabla es pequeña,queda muy fragmentada por lo que se desperdician varias casillas de la tabla. La ventaja es que al saltar cuadrática mente es mas probable que encuentre una posición vacía antes que en forma lineal. La función hash es fundamental para reducir el numero de colisiones en la tabla,si se elige una función que para la mayoría de los elementos devuelva un mismo valor hash las colisiones incrementaran por lo tanto nos alejamos del valor constante que queremos obtener con nuestra tabla. Sabiendo esto se ha de buscar función hash que genere menos colisiones posibles,otro factor importante es que la tabla no debe de llenarse nunca mas del ochenta por ciento,una vez que se llegue a ese tope se realiza loque se conoce como rehashing que redimensiona la tabla y la hace mas grande. Esto genera a su vez otro inconveniente,que el tamaño de la tabla ya no es la misma por lo tanto los cálculos de inserción búsqueda y eliminación se van haciendo mas complejos. También se recomienda que el tamaño de la tabla sea un numero impar pues así al hacer la función hash se reducen las probabilidades de que se generen colisiones. Sabiendo esto podemos empezar con el análisis de las funciones fundamentales de una tabla hash.

Inserción-dispersión lineal:

public int insertar1(int valorAInsertar) { int hashcode = -1;//1

if (hashing(valorAInsertar) <= tamañoTabla) { //2+1 int co = 1;//1

if (tabla[hashing(valorAInsertar)] == -1) {//2+1 tabla[hashing(valorAInsertar)] = valorAInsertar;//2+1 hashcode = hashing(valorAInsertar);//1

} else {

while ((co + hashing(valorAInsertar)) < tamañoTabla) {//N,caso medio 1 if (tabla[hashing(valorAInsertar) + co] == -1) {//2+1

tabla[hashing(valorAInsertar) + co] = valorAInsertar;2+1 hashcode = hashing(valorAInsertar) + co;2+1+1

...