NIVEL 14: ESTRUCTURAS DE ACCESO DIRECTO Tablas de Hashing
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
2
Tablas de hashing • Motivación y definiciones • Posibles estructuras de implementación • Área primaria y área de desbordamiento
• Funciones de hashing
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
3
Qué es una tabla de hashing • Estructura (contenedora) de datos de acceso
directo, en la cual cada elemento tiene asociada una llave por medio de la cual se consulta. • Permite el rápido acceso a la información en
O(1). ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
4
Ejemplo simple
Llave de acceso = el número !!! ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
5
Ejemplo simple • Se va a almacenar un conjunto de empleados de una
empresa (máx.10.000) cuyas llaves de acceso son valores entre 0 y 9999 (Ej: el código del empleado). 0
…
387
9999
- Complejidad en :Empleado código = 387 nombre = “pepe” ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
espacio? - Complejidad de una consulta dada la llave?
6
¿Qué pasa si … ? • La llave de acceso es ahora la cédula del
empleado (valores entre 0 y 99.999.999). 0
…
51.974.283
99.999.999
- Complejidad en :Empleado cedula = 51.974.283 nombre = “pepe” ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
espacio? - Complejidad de una consulta dada la llave?
7
¿Qué pasa si … ? • La llave de acceso es ahora la cédula del
empleado (valores entre 0 y 99.999.999). 0
…
51.974.283
:Empleado cedula = 51.974.283 nombre = “pepe” ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
99.999.999
8
Solución • Usar una estructura de acceso DIRECTO • El objetivo es: •
Retomar la idea del vector, definiendo una manera rápida de proyectar el valor de una llave a una posición del vector, de manera que se tenga un acceso MUY EFICIENTE de la información.
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
9
Ésta es la idea 0
:Empleado
cedula = 51.974.283 nombre = “pepe”
23.453.114
51.974.283
. . .
:Empleado cedula = 79.214.890 nombre = “luis”
79.214.890
:Empleado cedula = 23.453.114 nombre = “maría”
9999 ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
Aplicar una función matemática sobre la llave que devuelva directamente el lugar en el que se encuentra dentro del vector. Esto es O(1).
10
Algunas definiciones Area primaria Espacio de llaves
0
tamaño = # Función de hashing
= tabla vacía (tamaño = 0)
llave
dirección Información
M-1
capacidad: M ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
Factor de carga =
tamaño capacidad
11
Algunas definiciones: Llave Espacio de llaves
Área primaria
llave
Información
•Cadena de caracteres alfanuméricos •Tiene un significado especial en el mundo del problema •Es única al interior de la tabla •Único medio para tener acceso a la información asociada ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
12
Algunas definiciones: Función de hashing Área primaria
Espacio de llaves Función de hashing llave
Información
•Función h que proyecta un valor del espacio de llaves a una dirección del área primaria. •Es la base del esquema de acceso a la información •No preserva el orden de las llaves. Si llave1 < llave2 no necesariamente se cumple que h( llave1 ) < h( llave2 ) ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
13
Ejemplo
:Empleado
0
23.453.114
335
51.974.283
. . . 4567
cedula = 51.974.283 nombre = “pepe”
:Empleado cedula = 79.214.890 nombre = “luis”
79.214.890 9997 :Empleado
9999 ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
cedula = 23.453.114 nombre = “maría”
14
¿Cuándo es útil una tabla de hashing ? Area primaria
Espacio de llaves
Cuando el espacio de llaves es MUCHO MAYOR que el área primaria.
Función de hashing
llave
Información
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
Cuando las llaves que se deben almacenar en la estructura tienen una distribución altamente no uniforme.
15
¿Cuándo NO es útil una tabla de hashing ? Area primaria
Espacio de llaves
Bajo desempeño en:
Función de hashing
llave
Información
SOLUCION:
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
Procesamiento secuencial de un rango de llaves Recorridos ordenados por llave Búsquedas con llaves incompletas
Utilizar varias estructuras de datos simultáneas
16
Ejemplo • Se desea almacenar la información de los
estudiantes de la universidad: Hay aproximadamente 3000 estudiantes • Las búsquedas se hacen por código de estudiante: •
•
Inicial nombre + inicial apellido + año de entrada + semestre + consecutivo de 4 dígitos
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
17
Ejemplo P: Cuál es el tamaño del espacio de llaves?
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
18
Ejemplo P: Cuál es el tamaño del espacio de llaves? 27 * 27 * 100 * 2 * 10.000 Inicial nombre + inicial apellido + año de entrada + semestre + consecutivo de 4 dígitos
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
19
Ejemplo ¿Cuál es el tamaño del espacio de llaves? R// 27 * 27 * 100 * 2 * 10.000
¿Cuál debería ser la capacidad del área primaria?
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
20
Ejemplo ¿Cuál es el tamaño del espacio de llaves? R// 27 * 27 * 100 * 2 * 10.000
¿Cuál debería ser la capacidad del área primaria? R// Superior a 3000 ( 20% mas)
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
21
Ejemplo ¿Cuál es el tamaño del espacio de llaves? R// 27 * 27 * 100 * 2 * 10.000
¿Cuál debería ser la capacidad del área primaria? R// Superior a 3000 ( 20% mas) ¿Posible función de hashing ? ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
22
Ejemplo ¿Cuál es el tamaño del espacio de llaves? R// 27 * 27 * 100 * 2 * 10.000 ¿Cuál debería ser la capacidad del área primaria? R// Superior a 3000 ( 20% mas) ¿Posible función de hashing ? R// Sumar todos los dígitos del carnet, multiplicar el resultado por el código ASCII de las iniciales, módulo M (siempre entre 0 y 2999 para M= 3000) ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
24
Colisiones: ¿Cuando se habla de colisión? • Cuando dos llaves distintas
son proyectadas sobre la misma dirección del área primaria. colisión (llv1, llv2) ssi llv1 llv2 h(llv1) = h(llv2) 0
23.453.114
335
51.974.283
. . . 4567
9998
9999 ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
•El desempeño de una tabla de hashing comienza a disminuir a medida que aumenta el factor de carga, puesto que crece el número de colisiones. •Se debe recurrir a estructuras auxiliares de datos sobre las cuales se hace una búsqueda mas lenta
25
Colisiones • Posible implementación y soluciones a
problemas de colisión
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
26
Posible implementación Área primaria
Vector de parejas llave:objeto. • Para insertar un elemento para el cual no existe conflicto, se pone la llave y la información asociada en la posición del vector definida por la función de hashing. •
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
0 1
llave objeto
. . .
M-1
llave objeto
llave objeto
27
Posible implementación Área primaria
Vector de parejas llave:objeto. • Para insertar un elemento para el cual no existe conflicto, se pone la llave y la información asociada en la posición del vector definida por la función de hashing. • ¿Qué pasa si hay colisión? •
0 1
. . .
M-1
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
llave objeto
llave objeto
llave objeto
28
Primera Solución: Inserción Secuencial Área primaria 0
•
La información de la segunda llave (llave:objeto) se pone en la siguiente posición libre del área primaria, recorriéndola secuencialmente posición por posición.
¿Cómo se busca un elemento en la tabla? Cuál es la complejidad? • ¿Cómo se elimina un elemento?
1
llave objeto
. . .
llave objeto
•
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
M-1
llave objeto
29
Segunda Opción: Clases de Equivalencia Área primaria •
Cada posición del área primaria está constituida por un vector de parejas llave:objeto, ordenada ascendentemente por llave, con los elementos que pertenecen a la clase de equivalencia respectiva (aquellos que colisionaron)
¿Cómo se busca un elemento en la tabla? ¿Cuál es la complejidad? • ¿Cómo se elimina un elemento?
0 1
. . .
•
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
llave objeto
M-1
llave objeto
30
Tercera Opción: Bloques de Desbordamiento Área primaria •
•
•
• • •
Cada posición del área primaria tiene un 0 espacio fijo asociado para poner ahí un 1 número limitado de elementos que colisionan. Espacio es insuficiente es: . desbordamiento del bloque. . Solución: utilizar un bloque del mismo tamaño y se encadena con el bloque . original. Al interior de los bloques los elementos no tienen un orden específico. ¿Cómo se busca un elemento en la tabla? ¿Cuál es la complejidad? ¿Cómo se elimina un elemento? M-1
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
llave objeto
llave objeto
31
Funciones de hashing: Tips • No perder demasiado tiempo en estudios
teóricos para escogerla. • Utilizar una función que distribuya razonablemente las llaves y no tratar de encontrar un óptimo. • Importante: hacer un manejo eficiente de las colisiones. ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
32
Definición en 2 etapas Conversión a un espacio intermedio
Conversión a una dirección válida
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co Proyecto CUPI2
33
Definición en 2 etapas Conversión a un espacio intermedio
Objetivos: • Pasar de un espacio alfanumérico a un espacio puramente numérico. • Lograr una mejor distribución de las llaves
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
Conversión a una dirección válida
34
Definición en 2 etapas Conversión a un espacio intermedio
Objetivos: • Pasar de un espacio alfanumérico a un espacio puramente numérico. • Lograr una mejor distribución de las llaves
ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co
Ejemplos sobre el valor 38.998: • La llave es multiplicada por si misma: 1.520.844.004 • Se multiplica cada uno de los dígitos de la llave, incluido el valor ascii de los caracteres no numéricos: 15.552. Conversión a una • Se toma la llave como si se dirección encontrara en otra base y se válida convierte a base 10. • Se suman cada par de dígitos adyacentes módulo 10: 188. • Unir las cifras que representan los caracteres ascii de la llave, si son alfabéticos. Ej: CASA = 67.658.465
35
Definición en 2 etapas Conversión a un espacio intermedio
Función de división: típicamente modulo M
Función de truncamiento: toma un valor numérico y suprime dígitos o bits hasta que queda como una dirección válida ISIS1206 – Estructuras de Datos http://cupi2.uniandes.edu.co