Programación 3: tablas de dispersión

Universidad de CuencaFacultad de Ingeniería

Escuela de Ingeniería de SistemasProgramación III

Tema: Tablas de Dispersión

Por: Jonnathan Peñaranda

CONTENIDO• Tablas de dispersión.• Funciones de dispersión.• Colisiones y resolución de colisiones.• Problema planteado.• Conclusión.

TABLAS DE DISPERSIÓN (TABLAS HASH)Son estructuras

de datos

Se usan en secuencia de

elementosValor clave

Complejidad constante: O(1)

Su finalidad

Inserción

Búsqueda

Eliminación

• La tabla de dispersión es un vector de tamaño fijo m,• Contiene las claves de los elementos, • Consta de una función hash, que transforma el campo clave elegido,

en un valor entero dentro del rango del vector. pos Elemento

0

1

2

4

.

m-2

m-1

FUNCION_HASH( clave)

Elemento 1

Elemento 2

Elemento 3

clave1

clave2

clave3

Elemento 1

Elemento 2

Elemento 3

IMPLEMENTACIÓN EN JAVA

FUNCIONES DE DISPERSIÓN

Convierte el dato considerado campo clave en un índice dentro

del rango de definición del vector.

Lo ideal es determinar

posición en un almacenamiento

secuencial sin desperdiciar

mucho espacio.

FUNCIONES DE DISPERSIÓN

tamTabla = mHash(x): [0,m-1]

String clave = “a01”;

int clave = ASCII(a) + ASCII(0)+

ASCII(1);

CRITERIOS PARA SELECCIONAR UNA FUNCIÓN. • Fácil de evaluar y complejidad O(1)

• h(x) debe distribuir uniformemente las posiciones de los elementos sobre el conjunto de direcciones de memoria , de modo que minimice el numero de colisiones

• Preparar siempre resolución de colisiones para cuando éstas se produzcan.

TIPOS DE FUNCIONES HASH• Aritmética modular.• Plegamiento.•Mitad del cuadrado.•Método de la multiplicación

ARITMÉTICA MODULAR• La función hash mas simple

utiliza el operador.• Genera valores calculando el

resto de la división entera entre la clave x y el tamaño de la tabla m.

h(x)= x % m

• Implementación en Java

Ejemplo:m= 1000Elm1 = 245643Elm2 = 245221Elm3 = 257135

PLEGAMIENTO• Clave demasiado grande.

• Consiste en partir la clave x en varias partes ()

h(x) = x1 + x2 + x3 + x4 + ……..+ xr;h)x) = valor entero ;



MITAD DEL CUADRADOtamTabla = 51;clave = 45;

clave^2 = 2025;

2 0 2 5

h(x) = 25;



MÉTODO DE LA MULTIPLICACIÓN • La dispersión genera direcciones

en tres pasos:

1. A*clave (0 < A < 1).

2. d = A*x – ParteEntera(A*x).

3. h(x) = ParteEntera(m*d).


Donald E. Knuth sugiere que A ≈ ( √ 5 − 1)/2 = 0.61680339887...


OPERACIONES DE LAS TABLAS DE DISPERSIÓN

Además• Dos claves diferentes, c1 y c2, den la misma dirección, h1(c1) =

h2(c2). Se produce una colisión.

• Direccionamiento hash implica: la elección de la función hash y resolución de colisiones.

COLISIONES Y RESOLUCIÓN DE COLISIONES

pos Elemento

0

1

2

4

.

m-2

m-1

FUNCION_HASH (clave)

Elemento 1

Elemento 2

clave1

clave2

Elemento1 Elemento 2

COLISIÓN

MODELOS PARA RESOLVER COLISIONES.• La exploración de direcciones• Exploración lineal• Exploración cuadrática

• Direccionamiento enlazado.

EXPLORACIÓN DE DIRECCIONES.• Las colisiones se resuelven explorando consecutivamente en una

secuencia de direcciones hasta que se encuentra una posición libre(hueco).

• Importante, inicializar todas las posiciones de la tabla con un valor que indique vacío. Por ejemplo null.

• Al insertar un elemento, si se produce una colisión, la secuencia de exploración termina cuando se encuentra una dirección vacía.

EXPLORACIÓN LINEAL• Forma mas simple y primitiva de resolver una colisión entre claves.• La forma de resolver la colisión consiste en buscar la primera posición

disponible que siga a la posición que retorna la función hash.pos Elemento

0

1 OCUPADO

2 OCUPADO

4

. OCUPADO

m-2

m-1

FUNCION_HASH (Elemento)

Elemento

EXP_LINEAL( pos)

¿Está ocupado?

SI



0

1 OCUPADO

2 OCUPADO

4

. OCUPADO

m-2

m-1


Elemento

EXP_LINEAL( pos)

¿Está ocupado?

SI



0

1 OCUPADO

2 OCUPADO

4

. OCUPADO

m-2

m-1


EXP_LINEAL( pos)

¿Está ocupado?

NO

Elemento

Elemento


EXPLORACIÓN CUADRÁTICA


EXP_CUADRATICA( POS)

¿Está ocupado? SI

ELEMENTO

POS ELEMENTOS

0 OCUPADO

1 OCUPADO

2

3 OCUPADO

4 OCUPADO

5

6 OCUPADO

7

8

9

10 OCUPADO

p

clave




¿Está ocupado? SI

ELEMENTO

POS ELEMENTOS

0 OCUPADO

1 OCUPADO

2

3 OCUPADO

4 OCUPADO

5

6 OCUPADO

7

8

9

10 OCUPADO

clavep+1

p


FUNCION_HASH (clave) EXP_CUADRATICA( POS)

¿Está ocupado? SI

ELEMENTO

POS ELEMENTOS

0 OCUPADO

1 OCUPADO

2

3 OCUPADO

4 OCUPADO

5

6 OCUPADO

7

8

9

10 OCUPADO

p+4

clavep+1

p




¿Está ocupado? NO

ELEMENTO

POS ELEMENTOS

0 OCUPADO

1 OCUPADO

2

3 OCUPADO

4 OCUPADO

5

6 OCUPADO

7

8

9

10 OCUPADOp+9

clave

ELEMENTO

Recorrido

p + i^2

i = 0, 1, 2, …

p+4

p+1p


DIRECCIONAMIENTO ENLAZADO.• Se basa en utilizar listas enlazadas, de tal forma que en cada lista se

colocan los elementos que tienen la misma dirección hash.• Todos los elementos que colisionan: h(x1) = h(x2) = h(x3) … van a

estar ubicados en la misma lista enlazada.pos Elemento *0124 . 11

12


Elemento 1clave

Elemento 2




12

FUNCION_HASH (clave) Elemento 1

clave

clave

null

Elemento 2

Elemento 1




12

FUNCION_HASH (clave) Elemento 1

clave

Elemento 2 nullnull

Elemento 2

TABLAS DE DISPERSIÓN ENLAZADAS EN JAVA

OPERACIONES DE TABLAS DE DISPERSIÓN ENLAZADAS

INSERTAR


INSERTAR


BUSCAR


BUSCAR


ELIMINAR


ELIMINAR

PROBLEMA.

PROBLEMA.

PROBLEMA.

PROBLEMA.

PROBLEMA.

PROBLEMA.

PROBLEMA.

PROBLEMA.

CONCLUSIÓN.

• tamTabla = numero_primo mayor, aunque cercano al numero de elementos que se tiene previsto almacenar en la tabla.• Para resolver una colisión, lo mejor seria que se utilizara el

direccionamiento enlazado, y de este modo el tamaño de la tabla sería irrelevante puesto que la estructura podrá almacenar los elementos de forma dinámica.

REFERENCIA.• Joyanes Aguilar, L., & Zohonero Martínez, I. (2008).

Estructura de datos en Java. McGraw-Hill España.

Engineering

Programación 3: tablas de dispersión