Tabla Hash


UNIVERSIDAD TECNICA DEL NORTE
FACULTAD DE INGENIERA EN CIENCIAS APLICADAS
CARRERA DE INGENIERIA EN SISTEMAS COMPUTACIONALES
ESTRUCTURA DE DATOS








Nombre: Jonathan Freddy Gracia Churta
Fecha:01 de Febrero del 2016





Tabla Hash
Definición:
Colisiones:
Exploración Lineal:
Exploración Cuadrática:
Hashing Enlazado:

TABLAS DE DISPERSIÓN
Definición: Las tablas de dispersión sonestructuras de datos que tienen como finalidad realizar las operaciones fundamentales de búsqueda y eliminación de un registro en un tiempo de ejecución constante (complejidad constante O (1) ). Laorganización ideal de una tabla es de tal forma que el campo clave de los elementos se corresponda directamente con el índice de la tabla
Colisiones: La función de dispersión elegida h(x) puede generar la mismaposición al aplicarla a las claves de dos o más registros diferentes; esto es, obtener la misma posición de la tabla en la que ubicar dos registros. Si ocurre, se produce una colisión que es precisoresolver para que los registros ocupen diferentes posiciones. Una función hash ideal, h(x) , debe generar direcciones distintas para dos claves distintas. No siempre es así, no siempre proporcionadirecciones distintas; en ocasiones, ocurre que dadas dos claves diferentes x 1 , x ⇒ 2 h(x 1 ) = h(x 2 ) . Este hecho es conocido como colisión, es evidente que el diseño una tabla dispersa debeproporcionar métodos de resolución de colisiones.
Exploración Lineal: Es la forma más primaria y simple de resolver una colisión entre claves, al aplicar una función de dispersión. Supóngase que se tiene unelemento de clave x , la dirección que devuelve la función h(x) = p , si esta posición ya está ocupada por otro elemento se ha producido una colisión. La forma de resolver está colisión con exploraciónlineal consiste en buscar la primera posición disponible que siga a p . La secuencia de exploración que se genera es lineal: p, p+1, p+2, ... m-1, 0, 1, ... y así consecutivamente hasta encontrar...