Tablas hash

Indice:

Introducción…………………………………………………………………………………3

Objetivos Generales…………………………………………………………………….4

Objetivos Específicos …………………………………………………………………..4

1. Marco Conceptual

Tablas Hash ……………………………………..………………………………………….5

Operaciones de una tabla hash o de dispersión………………………...6-7

Funciones de Dispersión…………………………………………………………....7-9

Colisiones y resolución decolisiones………………………………………….9-11

Direccionamiento Enlazado………………………………………………………11-13

2. Aplicaciones de Tablas Hash

Ejemplificacion…………………………………………………………………………13-14

Desarrollo…………………………………………………………………………………14-18

Bibliografia………………………………………………………………………………….19

Conclusiones………………………………………………………………………………..20

Introducción

El siguiente trabajo de investigación da a conocer una herramientaimportante en los lenguajes de programación lo cuales son las tablas hash; de estas se describirán sus funciones hash o funciones de dispersión que permiten a través de expresiones matemáticas obtener direcciones según una clave.

Anteriormente hemos trabajado con arrays los cuales son herramientas potentes en el lenguaje c que permiten localizar un elemento de clave X en la posición x, pero con eldesarrollo de este trabajo de investigación se pretende mostrar que además de los arrays podemos contar con las tablas hash cuando no necesariamente queramos o podamos acceder directamente dada la clave a la posición de la tabla esto presentan numerosas ventajas en la aplicación de estructuras.

La potencia de las tablas hash o dispersas radica en la búsqueda de elementos; conociendo el campoclave se puede obtener directamente la posición que ocupa, y por consiguiente, la información asociada a dicha clave.

Un ejemplo clásico de este tipo de estructura, tablas hash es la implementación de cualquier tipo de diccionario ya que su principal característica es la búsqueda de elementos.

OBJETIVOS

1.1 OBJETIVO GENERAL

Conocer una estructura de datos para resolver un problema de lavida cotidiana utilizando la función hash.

1.2 OBJETIVOS ESPECÍFICOS

1.2.1 Determinar las ventajas que tienen la implementación de tablas hash en la búsqueda de elementos.

1.2.2 Definir las funciones matemáticas necesarias para poder obtener a las direcciones según el argumento de la función.

1.2.2 Especificar los diversos métodos de resolución de colisiones.

1.2.3 Identificaruna aplicación en la que se aplique tablas hash.

1- MARCO CONCEPTUAL

Una tabla hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo).Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.

[pic]

Ejemplo de tabla hash.

Las tablas hash se suelen implementar sobre vectores de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante debúsqueda promedio O(1), sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos.

Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información.

Las tablas hash almacenan la información enposiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios auto-balanceables son más rápidos en promedio (tiempo de búsqueda O(log n)) pero la información está ordenada en todo momento.

Las tablas Hash son estructuras de datos que tienen como finalidad realizar la búsqueda o eliminación de un registro con una complejidad...