Estructura de datos, mapa conceptual tablas hash

Lisää tämän kaltaisia

MEDIDAS DE DISPERSION

luonut Jairo Caliz

Buscar V

luonut marcelino Dìaz

Macros en Word

luonut Katherine Nicole Castañeda Millán

EL FRUTO

luonut RODRIGO ELÍAS ALCALA LOJA

Funcion De dispersion (hashing)

La Función de Dispersión convierte un Objeto en un Entero (valor Hash) adecuado para indexar la Tabla en la que se guardará el Objeto

La eliminación tiene el mismo costo que la búsqueda, ya que con la función hash se encuentra la posición del elemento y posteriormente se elimina.

La insercion en hashing abierto, consiste en aplicar la función hash al dato a insertar. El resultado de esta operación genera la clave que va a indicar la posición del array en la cual se almacenará el dato y en esta posición del arrayse añadirá al inicio de la lista enlazada. (insertar al inicio en una lista enlazada es constante ). Hay que tener en cuenta que al insertar un dato en una lista con tamaño mayor a cero se genera una nueva colisión.

TABLAS HASH

El objetivo será encontrar una función hash que provoque el menor número posible de colisiones (ocurrencias de sinónimos), aunque esto es solo un aspecto del problema, el otro será el de diseñar métodos de resolución de colisiones cuando éstas se produzcan.

Esta aproximación consiste en proceder, no por comparaciones entre valores clave, sino encontrando alguna función h(k), función de dispersión, que nos dé directamente la localización de la clave k en la tabla.

La operación principal en la que se usan son en las busquedas,permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada usando el nombre, número de cuenta o id.

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.

Operaciones basicas a realizar con tablas hash

Eliminar llave

Buscar llave

Insertar llave

Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. Colección de elementos, cada uno de los cuales tiene una clave y una información asociada.