Ayudantia7

Universidad Diego Portales Facultad de Ingenier´ıa ´ tica Escuela de Ingenier´ıa Informa

1

Curso: Estructura de Datos Profesor: Sergio Mujica ´n Ayudante: Jaime Guzma

Hashing Abierto

Consiste en tener una lista de todos los elementos que se dispersan en el mismo valor, es decir, una lista enlazada de registros cuyas llaves(keys) concurran a esa direccion. La cantidad de tiempo requerido para una busqueda dependera de la longitud de las listas y de las posiciones relativas de las llaves en ellas. Si tuvieramos que manejar colisiones ademas de las listas enlazadas, se podria usar cualquier esquema para resolver colisiones, como un arbol binario de busqueda. Diremos que λ es el factor de carga de un tabla de hash, el cual representa : λ=

N umero de keys en la tabla N

,donde N es el tama˜ no de la tabla.

2

Hashing Cerrado • Al contrario con el hashing abierto si ocurre una colision, se intenta buscar celdas alternativas hasta encontrar una vacia. • El problema de encontrar espacios vacios se puede solucionar con el rehashing • Como todos los datos se meten en la tabla, esta tiene que ser mas grande para una dispersion cerrada que para una abierta.

3

Exploracion Lineal

Por lo general la estrategia de resolucion f (x) es una funcion lineal que resuelve las colisiones . Esto equivale a buscar secuencialmente en el vector (con circularidad) hasta que encontremos una posicion vacia. En tanto que la tabla sea suficientemente grande, siempre se puede encontrar una celda vacia, pero ello puede tomar demasiado tiempo y posiblemente produsca agrupamiento primarios. El numero medio de celdas examinadas en una insercion con exploracin lineal es cercano a 1 1 (1 + ) 2 (1 − λ)2 Y el costo de una busqueda con exito es la media de los costes de las inserciones en tablas con factores de carga mas peque˜ nos. 1 1 (1 + ) 2 1−λ

1

4

Exploracion Cuadratica • Su resolucin de colisiones elimina el problema del agrupamiento primario que padece la exploracion lineal. • La funcion que maneja las colisiones es cuadratica. • Si se emplea exploracion cuadratica, el tama˜ no de la tabla es un numero primo, y el factor de carga no excede el 0.5, siempre podemos insertar un nuevo elemento en la tabla, y durante una operacin de insercion no se examina ninguna celda dos veces.

5

Ejercicios 1. Sea T una tabla de hash de tama˜ no 10 y h la siguiente funcion de hash. h(k) = 4 + 3k mod10 Se quieren insertar en T elementos con claves 1, 11, 5, 15, 55, 6, 26, 90, 50, 20 en ese mismo orden usando h. (a) Determine el resultado de insertar las claves en T si las colisiones se resuelven por encadenamiento (suponga que un nuevo elemento se agrega al final de una lista). (b) Determine el resultado de insertar las claves en T si las colisiones se resuelven por examinacion lineal. Soluci´ on

a)Se tiene el siguiente resultado:

b)Se tiene el siguiente resultado:

2

2. Considere una tabla de hash de tamao N , donde todas las llaves se distribuyen de manera uniforme, y las colisiones se resuelven usando encadenamiento (hash abierto). Si la tabla de hash contiene M elementos, y cada lista se mantiene ordenada de manera creciente, cul es el tiempo esperado de una operacin de insercin? Soluci´ on Si la tabla contiene M elementos, y sus llaves se han distribuidos de manera uniforme entre las N posiciones de la tabla, entonces el tamao de cada lista debe ser M/N . Si la lista se mantiene ordenada en cada insercin, una alternativa razonable es insertar cada elemento nuevo en su posicin correspondiente de la lista, lo que en el mejor caso toma tiempo O(1) (si va al principio de la lista), y en el peor caso es O(M/N ) (si va al final de la lista). La insercin en la lista es, en promedio, O(M/N ). La operacin de insercin considera, primero, calcular la funcin de hash, que debe ser O(1), y, segundo, insertar de manera ordenada en la lista, que sera O(M/N ). El tiempo total de insercin es, entonces O(M/N ).

3